【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《排列组合与数列递推关系》,欢迎阅读!
例析排列、组合、概率问题中的递推数列
一、an=p·an-1+q型
【例1】 某种电路开关闭合后,会出现红灯或绿灯闪动,已知开关第一次闭合后,出
现红灯和绿灯的概率都是12,从开关第二次闭合起,若前次出现红灯的概率是1
3
,出现绿灯
的概率是233;若前次出现绿灯,则下次出现红灯的概率是2
5,出现绿灯的概率是5
,记开关
第n次闭合后出现红灯的概率为Pn。
(1)求:P2;(2)求证:Pn<1
2(n≥2);(3)求limn
Pn。
解析:(1)第二次闭合后出现红灯的概率P2的大小决定于两个互斥事件:即第一次红
灯后第二次又是红灯;第一次绿灯后第二次才是红灯。于是P2=P1·13+(1-P1)·37
5=15
。
(2)受(1)的启发,研究开关第N次闭合后出现红灯的概率Pn,要考虑第n-1次闭合后出现绿灯的情况,有
Pn=Pn1343
-1·3+(1-Pn-1)·5=-15Pn-1+5
,
再利用待定系数法:令Pn+x=-49
15(Pn-1+x)整理可得x=-19
∴{Pn-919}为首项为(P1-94
19)、公比为(-15)的等比数列
Pn-919=(P1-919)(-415)n-1=14-914-
38(-15)n1,Pn=19+38(-15
)n1
∴当n≥2时,Pn<911
19+38=2
(3)由(2)得lim9
n
Pn=19。
【例2】 A、B两人拿两颗骰子做抛掷游戏,规则如下:若掷出的点数之和为3的倍数时,则由原掷骰子的人继续掷;若掷出的点数不是3的倍数时,由对方接着掷.第一次由A开始掷.设第n次由A掷的概率为Pn,
(1)求Pn;⑵求前4次抛掷中甲恰好掷3次的概率. 解析:第n次由A掷有两种情况:
① 第n-1次由A掷,第n次继续由A掷,此时概率为12
36Pn-1;
② 第n-1次由B掷,第n次由A掷,此时概率为(1-12
36
)(1-Pn-1)。
∵两种情形是互斥的
∴Pn=1212136Pn2
-1+(1-36)(1-Pn-1)(n≥2),即Pn=-3Pn-1+3(n≥2)
∴Pn-12=-13(Pn1
-1-2),(n≥2),又P1=1
∴{Pn-12}是以11
2为首项,-3为公比的等比数列。
∴Pn-111-111-
2=2(-3)n1,即Pn=2+2(-3)n1。
⑵2881
。 二、an+1=p·an+f(n)型
【例3】 (传球问题)A、B、C、D4人互相传球,由A开始发球,并作为第一次传球,经过5次传球后,球仍回到A手中,则不同的传球方式有多少种?若有n个人相互传球k次后又回到发球人A手中的不同传球方式有多少种?
分析:这类问题人数、次数较少时常用树形图法求解,直观形象,但若人数、次数较多时树形图法则力不从心,而建立递推数列模型则可深入问题本质。
4人传球时,传球k次共有3k种传法。设第k次将球传给A的方法数共有ak(k∈N*)种传法,则不传给A的有3k-ak种,故a1=0,且不传给A的下次均可传给A,即
ak+1=3k-ak。两边同除以3k+1得ak+11ak1
3k+1=-3·3k+3
,
令bk=ak3-14=-13(bk-14),则bk-14=-14(-13)k-
k,则b1=0,bk+11
∴ak=3k4+3
4
(-1)k
当k=5时,a5=60.
当人数为n时,分别用n-1,n取代3,4时,可得a(n-1)kn-1
k=n +n
(-1)k。
【例4】 (环形区域染色问题)将一个圆环分成n(n∈N*,n≥3)个区
域,用m(m≥3)种颜色给这n个区域染色,要求相邻区域不使用同一种
n 1
颜色,但同一颜色可重复使用,则不同的染色方案有多少种?
n-1 2
分析:设an表示n个区域染色的方案数,则1区有m种染法,2区有m-1种染法,3,……,n-1,n区各有m-1种染色方法,依乘法
3
…… 原理共有m(m-1)n-
1种染法,但是,这些染中包含了n区可能和1区染
上相同的颜色。而n区与1区相同时,就是n-1个区域涂上m种颜色合乎条件的方法。
∴an=m(m-1)n-
1-an-1,且a3=m(m-1)(m-2)
an-(m-1)n=-[an-
-1-(m-1)n1]
an-(m-1)n=[a3-(m-1)3](-1)n-
3 ∴an=(m-1)n+(m-1)(-1)n(n≥3) 用这个结论解:2003年高考江苏卷:某城市在中心广场建一5 个花圃,花圃分为6个部分如图,现要栽种4种不同颜色的花且相
6 1
4
邻部分不能同色,由不同的栽种方法有 种。
2
3 只需将图变形为圆环形,1区有4种栽法。不同的栽法数为 N=4a5=120。
三、a=a(n)型
6
2 n+1n·f【例5】 (结草成环问题)现有n(n∈N*)根草,共有2n个草头,1
3现将2n个草头平均分成n组,每两个草头打结,求打结后所有草5
能构成一个圆环的打结方法数。
4 分析:将2n个草头平均分成n组,每两个草头打结,要
使其恰好构成圆环,不同的连接方法总数m2=an。
1 2
将草头编号为1,2,3,……,2n-1,2n。 3 4
草头1可以和新草头3,4,5,……,2n-1,2n共2n
5 6 -2个新草头相连,如右图所示。 ……
2n-1
2n 假设1和3相连,则与余下共n-1条相连能成圆环的方法数为an-1。
∴an=(2n-2)ann≥2,n∈N*),a1=1,得an
-1,(an-1
=2n-2
an=ana·an-1·……·a2·an-1an-2
a11=(2n-2)(2n-4)……2×1=2n-
1(n-1)!
变式游戏:某人手中握有2n(n∈N*)根草,只露出两端的各自2n个草头,现将两端的2n个草头各自随机平均分成n组,并将每组的两个草头连接起来,最后松手,求这时所有的草恰好构成一个圆环的概率。
分析:两端的2n个草头随机两个相连不同的方法数为N=( C22……C2
2nC2n-22 n!
)2
能够构成圆环的连接方法分两步:
第一步,先将一端的2n个草头平均分成n组,每两根连接起来,得到n组草,认为
得到n根“新草”,连接方法数m C22C2
2nC2n-2……2
1= n!
。
第二步,将另一端的2n个草头平均分成n组连接起来,要使其恰好构成圆环,不同
的连接方法总数m2=2n-
1(n-1)!。
m(n-1)!n!22n-
1m21
∴所求的概率Pn=N=(2n)!
变式:(06 江苏) 右图中有一个信号源和五个接收信号源
器。接收器与信号源在同一个串联线路中时,就能接收到信号,否则就不能接收到信号。若将图中左端的六个接线点随机地平均分成三组,将右端的六个接线点也随机地平均分成三组,再把所有六组中每组的两个接线点用导线连接,则这五个接收器能同时接收到信号的概率是(D)
(A)445 (B)136 (C)415 (D)815
四、an+1=p·an+q·an-1型
【例6】 某人玩硬币走跳棋的游戏。已知硬币出现正反面的概率都是1
2
,棋盘上标有
第0站、第1站、第2站、……、第100站.一枚棋子开始在第0站,棋手每掷一次硬币,棋子向前跳动一次,若掷出正面,棋子向前跳一站(从k到k+1);若掷出反面,棋子向前跳两站(从k到k+2),直到棋子跳到第99站(胜利大本营)或跳到第100站(失败集中营)时,该游戏结束.设棋子跳到第n站的概率为Pn.
(1)求P0、P1、P2的值;
(2)求证:Pn-Pn1
-1=-2
(Pn-1-Pn-2),其中n∈N,2≤n≤99;
(3)求玩该游戏获胜的概率及失败的概率。 (1)解:棋子开始在第0站为必然事件,P0=1.
第一次掷硬币出现正面,棋子跳到第1站,其概率为12,P1=1
2
.
棋子跳到第2站应从如下两方面考虑:
①前两次掷硬币都出现正面,其概率为14;②第一次掷硬币出现反面,其概率为1
2
.
∴P2=14+12=34
.
(2)证明:棋子跳到第n(2≤n≤99)站的情况是下列两种,而且也只有两种:
①棋子先到第n-2站,又掷出反面,其概率为1
2
Pn-2;
②棋子先到第n-1站,又掷出正面,其概率为1
2
Pn-1.
∴Pn=12Pn1
-2+2
Pn-1.
∴Pn-Pn1
-1=-2
(Pn-1-Pn-2).
(3)解:由(2)知当1≤n≤99时,数列{Pn-Pn11
-1}是首项为P1-P0=-2,公比为-2
的等比
数列。
∴P1-1=-12,P2-P1=(-12)2,P3-P2=(-12)3,…,Pn-Pn1
-1=(-2
)n.
以上各式相加,得Pn-1=(-111
2)+(-2)2+…+(-2
)n,
∴Pn=1+(-11121
2)+(-2)2+…+(-2)n=3[1-(-2
)n+1](n=0,1,2,…,99).
∴获胜的概率为P99=21
3[1-(2)100],
失败的概率P100=112111
2P98=2·3[1-(-2)99]=3[1+(2
)99]
【例7】 (上楼梯问题)从教学楼一楼到二楼共有15级楼梯,学生A一步能上1级或2级,那么A从一楼上到二楼的不同方法数共有多少种?
设上到第n级楼梯的方法数为an(n∈N),则a1=1,a2=2,an=an-1+an-2(n≥3),
由此可得,\{an}斐波那契数列:1,2,3,5,8,……得a13=377,a14=610,a15=987。
【例8】 从原点出发的某质点M,按向量a=(0,1)移动的概率为2
3
,按向量b=(0,2)
移动的概率为1
3
,设M可到达点(0,n)的概率为Pn
(1)求P1和P2的值;(2)求证:Pn+2-Pn+1=-1
3
(Pn+1-Pn);(3)求Pn的表达式。
解析:(1)P1=23,P2=(217
3)2+3=9
(2)证明:M到达点(0,n+2)有两种情况:
①从点(0,n+1)按向量a=(0,1)移动,即(0,n+1)→(0,n+2) ②从点(0,n)按向量b=(0,2)移动,即(0,n)→(0,n+2)。
∴Pn+2=21
3Pn+1+3
Pn
∴Pn+2-Pn+1=-1
3
(Pn+1-Pn)
(3)数列{Pn+1-Pn}是以P2-P1为首项,-1
3
为公比的等比数列。
Pn+1-Pn=(P2-P1)(-1111
3)n-1=9(-3)n-1=(-3)n+1,
∴Pn-Pn1
-1=(-3
)n
又∵Pn-P1=(Pn-Pn1-Pn11111
-1)+(Pn--2)+…+(P2-P1)=(-3)n+(-3)n-1+…+(-3)2=(12)[1-(-3
)n-1]
∴Pn=P1+(1131112)[1-(-3)n-1]=4+4×(-3
)n
。
本文来源:https://www.wddqxz.cn/b8bb0e04650e52ea54189813.html