排列组合与数列递推关系
张咸宁-
例析排列、组合、概率问题中的递推数列
一、
a
n
=
p
·
a
n
－
1
+
q
型
【例
1
】
<
/p>
某种电路开关闭合后，会出现红灯或绿灯闪动，已知开关第一次闭合后，出
现红灯和绿灯的概率都是
1
1
2
，从开关第二次闭合起，若前次出现红灯的概率是
3
，出现绿灯
的概率是
2
3
2
3
；若前次出现绿灯，则下次出现
红灯的概率是
5
，出现绿灯的概率是
5
，记开关
第
n
次闭合后出现红灯的概率为
P
n
。
(1)
求：
P<
/p>
1
2
；
(2)<
/p>
求证：
P
n
<<
/p>
2
(
n
≥2
)
；
(3)
求
lim
n
P<
/p>
n
。
解析：<
/p>
(1)
第二次闭合后出现红灯的概率
P<
/p>
2
的大小决定于两个互斥事件：即第一次红
灯后第二次又是红灯；第一次绿灯后第二次才是红灯。于是
P
1
3
7
2
=<
/p>
P
1
·
3
+(1
－
P
1
)·
5
=
15
。
(2)
受
(1)
的启发，
研究开关第
< br>N
次闭合后出现红灯的概率
P
n
，
要考虑第
n
－
1
次闭合后
出现绿灯的情况，有
P
1
3
4
3
n
=
P
n
－
1
< br>·
3
+(1
－
< br>P
n
－
1
)·
5
=
－
15
P
n
－
1
+
5
，
再利用待定系数法：令
P
－
4
9
n
+
x
=
15
(
P
n
－
1
+
x
)
整理可得
x
=
－
19
∴
{
P
－
9
19
}
为首项为
(
P
9
4
n
1
－
19
)
、公比为
(
－
15
)
的等比数列
P
9
=(
P<
/p>
9
4
－
1
=
1
(
－
4
)
n
－
1
，
P
9
1
4
－
n
－
1
－
)(
－
)
n
n
=
+
(
－
)
n
1
19
19
15
38
15
19
38
15
∴
当
n
≥2
时，
P
9
1
1
n
<
19
+
38
=
2
(3)
由
(2)
得
lim
9
n
P
n
=
19
。
【例
2
】
<
/p>
A
、
B
两人拿两
颗骰子做抛掷游戏，规则如下
:
若掷出的点数之和为
3
的倍数
时，则由原掷骰子的人继续掷；若掷出的
点数不是
3
的倍数时，由对方接着掷
.
第一次由
A
开始掷
.
设第
n
次由
A
掷的概率为
P
n
，
(1)
求
P
n
；⑵
求前
4
次抛掷中甲恰好掷
3
次的概
率
.
解析：第
n
次由
A
掷有两种情况：
①
第
n
－
1
次由
A
掷，第
n
次继续由
A
掷，此时概率为
12
36
P
n
－
1
< br>；
②
第
n
－
1
次
由
B
掷，第
n
次由
A
掷，此时概率为
(1
－
12
36
)(1
－
P
n
－
1
)
。
∵
两种情形是互斥的
∴
P
12
12
1
2
n
=
36
P
n
－
1
+(1
－
36
)(1
－
P
n
－
1
)(
n
≥2
)
，即
P
n
=
－
3
P
n
－
1
+
3
(
n
≥2
)
∴
P
－
1
2
=
－
1
3
(
P
< br>1
n
n
－
1
－
2
)
，
(
n
≥2
)<
/p>
，又
P
1
=1
∴
{
P
1
1
1
n
－
2
}
是以
2
为首项，－
3
为公比的等比数列。
∴
P
1
1
1
－
1
1
1
－
n
－<
/p>
2
=
2
(
－
3
)
n
1
，即
P
n
=
2
+
2
< br>(
－
3
)
n
1
。
⑵
28
81
。
二、
a
n
+1
=
p
·
a
n
+
f
(
n
)
型
【例
3
】
<
/p>
(
传球问题
)
A
、
B
、
C
、
D
4
人互相传球
，由
A
开始发球，并作为第一次传球，
经过
5
次传球后，球仍回到
A
手中，则不同的传球方式有多少种？若有
n
个人
相互传球
k
次后又回到发球人
A
手中的不同传球方式有多少种？
分析：这类
问题人数、次数较少时常用树形图法求解，直观形象，但若人数、次数较
多时树形图法则
力不从心，而建立递推数列模型则可深入问题本质。
4
人传球时，传球
k
次共有
3
k
种传法。设第
k
次将球传给
A
的方法数共有
a
k
(
k
∈<
/p>
N
*)
种
传法，
则不传给
A
的有
3
k
－
a
k
种，故
a
1
=0
，且不传给
A
的下次均可传给
A
，即
a
a
a
k
。两边同除以
3
k
+1
得
k<
/p>
+1
1
a
k
+1
=3
k
－
k
1
3
k
+1
=
－
3
·
3
k
+
3
，
令
b
a
k
=
k
k
，则
b
1
1
1
1
1
1
－
1
=0
，
b
k
+1
－
=
－
(
b
k
－
)
< br>，则
b
k
－
=
－
(
－
)
k
1
3
k<
/p>
4
3
4
4
4
3
∴
a
=
3
+
3
k
(
－
1)
k
4
4
当
k
=5
时，
a
5
=60.
< br>n
时，分别用
n
－
1
，
n
取代
3
，
4
时，可得
a
(
n
－
< br>1)
k
当人数为
n
－
1
k
=
< br>n
+
n
(
－
1)
k
。
【例
4
】
<
/p>
(
环形区域染色问题
)
< br>将一个圆环分成
n
(
n
∈
N
*
，
n
≥
3)
个区
域，用
m
(
m
≥
3)
种颜色给这
n
个区域染色，要求相邻区域不使用同一种
n
1
颜色，但同一颜色可重复使用，则不同的染色方案有多少种？
n
-1
2
分析：设
a
n
表示
n
个
区域染色的方案数，则
1
区有
m
种染法，
2
区
有
m
－
1
种染法，<
/p>
3
，„„，
n
－
1
，
n
区各有
m
－
1
种染色
方法，依乘法
3
„„
原理共有
m
(
m
－
1)
n
－
1
种染法，但是，这些染中包含了<
/p>
n
区可能和
1
区
染
上相同的颜色。而
n
区与
1
区相同时，就是
n
－<
/p>
1
个区域涂上
m
种颜色合乎条件的方法。
∴
a
(
m
－
1)
n
－
n
=
m
1
－
a
< br>n
－
1
，且
a
3
=
m
(
m
－
1)(
m
－
2)
a
1)
n
=
－
[
a
－
n
－
(
m
－
n
－
1
－
(
m
－
1)
n
1
]
a
－
< br>(
m
－
1)
n
=[
a
－
n
3
－
(
m
－
1)
3
](
－
1)
n
3
∴
a
n
=(<
/p>
m
－
1)
n
+(
m
－
1)(<
/p>
－
1)
n
(
n
≥3)
用这个
结论解：
2003
年高考江苏卷：
某城
市在中心广场建一个
5
花圃，花圃分
为
6
个部分如图，现要栽种
4
种不同颜色的花且相邻
6
1
4
部分不能同色，由不同的栽种方法有
种。
2
3
只需将图变形为圆环形，
1
区有
4
种栽法。不同
的栽法数为
N
=4
< br>a
5
=120
。
三、
a
=
< br>a
(
n
)
型
6
2
n
+1<
/p>
n
·
f
【例
5
】
(
结草成环问题
)
现有
n
(
n
∈
N
*)
根草，共有
2
n
个草头，
1
3
现将
2<
/p>
n
个草头平均分成
n
组，每两个草头打结，求打结后所有草
5
能构成一个圆环的打结方法数。
4
分析：将
2
n
个草头平均分成
n
组，每两个草头打结，要
使其恰好构成圆环，不同的连接方法总数
m
2
=
a
< br>n
。
1
2
将草头编号为
1
，
2
，
3
，
……
，
2
n
－
1
，
2
n
。
3
4
草头
1<
/p>
可以和新草头
3
，
4
，
5
，
…
…
，
2
n
－<
/p>
1
，
2
n
共
2
n
5
6
－
2
个新草头相连，如右图所示。
„„
2
n
-1
2
n
假设<
/p>
1
和
3
相连，<
/p>
则与余下共
n
－
1
条相连能成圆环的方
法数为
a
n
－
1
。
∴
a
n
－
2)
a
≥
< br>2
，
n
∈
N
*)
，
a
a
n
=(2
n
1
=1
，得
n
－
1
，
(
n<
/p>
a
n
－
1
=2
n
－
2