排列组合与数列递推关系

2022-05-20 11:04:18 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《排列组合与数列递推关系》，欢迎阅读！
数列,排列,组合,关系

例析排列、组合、概率问题中的递推数列

一、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.dywdw.cn/b8bb0e04650e52ea54189813.html