tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 数学 >>

排列组合与数列递推关系


例析排列、组合、概率问题中的递推数列
一、an=p·n-1+q 型 a 【例1】 某种电路开关闭合后,会出现红灯或绿灯闪动,已知开关第一次闭合后,出 1 1 现红灯和绿灯的概率都是 ,从开关第二次闭合起,若前次出现红灯的概率是 ,出现绿灯 2 3 2 3 2 的概率是 ;若前次出现绿灯,则下次出现红灯的概率是 ,出现绿灯的概率是 ,记开关 3 5 5 第 n 次闭合后出

现红灯的概率为 Pn。 1 (1)求:P2;(2)求证:Pn< (n≥2);(3)求 lim Pn 。 2 n ?? 解析:(1)第二次闭合后出现红灯的概率 P2 的大小决定于两个互斥事件:即第一次红 1 3 7 灯后第二次又是红灯;第一次绿灯后第二次才是红灯。于是 P2=P1·+(1-P1)·= 。 3 5 15 (2)受(1)的启发,研究开关第 N 次闭合后出现红灯的概率 Pn,要考虑第 n-1 次闭合后 出现绿灯的情况,有 1 3 4 3 Pn=Pn-1·+(1-Pn-1)·=- Pn-1+ , 3 5 15 5 4 9 再利用待定系数法:令 Pn+x=- (Pn-1+x)整理可得 x=- 15 19 9 9 4 ∴ n- }为首项为(P1- )、公比为(- )的等比数列 {P 19 19 15 9 9 4 - 1 4 - 9 1 4 - Pn- =(P1- )(- )n 1= (- )n 1,Pn= + (- )n 1 19 19 15 38 15 19 38 15 9 1 1 ∴ n≥2 时,Pn< + = 当 19 38 2 9 (3)由(2)得 lim Pn = 。 19 n ?? 【例2】 A、B 两人拿两颗骰子做抛掷游戏,规则如下:若掷出的点数之和为 3 的倍数 时,则由原掷骰子的人继续掷;若掷出的点数不是 3 的倍数时,由对方接着掷.第一次由 A 开始掷.设第 n 次由 A 掷的概率为 Pn, (1)求 Pn;⑵ 求前 4 次抛掷中甲恰好掷 3 次的概率. 解析:第 n 次由 A 掷有两种情况: 12 ① 第 n-1 次由 A 掷,第 n 次继续由 A 掷,此时概率为 Pn-1; 36 12 ② 第 n-1 次由 B 掷,第 n 次由 A 掷,此时概率为(1- )(1-Pn-1)。 36 ∵ 两种情形是互斥的 12 12 1 2 ∴ n= Pn-1+(1- )(1-Pn-1)(n≥2),即 Pn=- Pn-1+ (n≥2) P 36 36 3 3 1 1 1 ∴ n- =- (Pn-1- ),(n≥2),又 P1=1 P 2 3 2 1 1 1 ∴ n- }是以 为首项,- 为公比的等比数列。 {P 2 2 3 1 1 1 n-1 1 1 1 n-1 ∴ n- = (- ) ,即 Pn= + (- ) 。 P 2 2 3 2 2 3 28 ⑵ 。 81

二、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 1 ak 1 ak+1=3k-ak。两边同除以 3k+1 得 k+1=- · k+ , 3 3 3 3 ak 1 1 1 1 1 1 - 令 bk= k,则 b1=0,bk+1- =- (bk- ),则 bk- =- (- )k 1 3 4 3 4 4 4 3 3k 3 ∴ak= + (-1)k 4 4 当 k=5 时,a5=60. (n-1)k n-1 当人数为 n 时,分别用 n-1,n 取代 3,4 时,可得 ak= + (-1)k。 n n 【例4】 (环形区域染色问题)将一个圆环分成 n(n∈N*,n≥3)个区 n 1 域,用 m(m≥3)种颜色给这 n 个区域染色,要求相邻区域不使用同一种 2 n-1 颜色,但同一颜色可重复使用,则不同的染色方案有多少种? 分析:设 an 表示 n 个区域染色的方案数,则 1 区有 m 种染法,2 区 3 ?? 有 m-1 种染法,3,??,n-1,n 区各有 m-1 种染色方法,依乘法 - 原理共有 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)n 1] - n 3 an-(m-1) =[a3-(m-1) ](-1)n 3 ∴an=(m-1)n+(m-1)(-1)n(n≥3) 5 用这个结论解: 2003 年高考江苏卷: 某城市在中心广场建一个 1 6 4 花圃,花圃分为 6 个部分如图,现要栽种 4 种不同颜色的花且相邻 3 2 部分不能同色,由不同的栽种方法有 种。 只需将图变形为圆环形,1 区有 4 种栽法。不同的栽法数为 N=4a5=120。 2 6 三、an+1=an·f(n)型 1 【例5】 (结草成环问题)现有 n(n∈N*)根草,共有 2n 个草头, 3 5 现将 2n 个草头平均分成 n 组,每两个草头打结,求打结后所有草 4 能构成一个圆环的打结方法数。 分析:将 2n 个草头平均分成 n 组,每两个草头打结,要 1 2 使其恰好构成圆环,不同的连接方法总数 m2=an。 3 4 将草头编号为 1,2,3,……,2n-1,2n。 5 6 草头 1 可以和新草头 3,4,5,……,2n-1,2n 共 2n ?? 2n -2 个新草头相连,如右图所示。 2n-1 假设 1 和 3 相连, 则与余下共 n-1 条相连能成圆环的方 法数为 an-1。 an ∴an=(2n-2)an-1,(n≥2,n∈N*),a1=1,得 =2n-2 an-1

an an-1 a2 - an= · ·??· ·a1=(2n-2)(2n-4)??2×1=2n 1(n-1)! a1 an-1 an-2 变式游戏:某人手中握有 2n(n∈N*)根草,只露出两端的各自 2n 个草头,现将两端的 2n 个草头各自随机平均分成 n 组,并将每组的两个草头连接起来,最后松手,求这时所有 的草恰好构成一个圆环的概率。 2 2 C2nC2n-2??C2 2 2 分析:两端的 2n 个草头随机两个相连不同的方法数为 N=( ) n! 能够构成圆环的连接方法分两步: 第一步,先将一端的 2n 个草头平均分成 n 组,每两根连接起来,得到 n 组草,认为 2 2 2 C2nC2n-2??C2 得到 n 根“新草” ,连接方法数 m1= 。 n! 第二步,将另一端的 2n 个草头平均分成 n 组连接起来,要使其恰好构成圆环,不同 - 的连接方法总数 m2=2n 1(n-1)!。 2n-1 m1m2 (n-1)!n!2 ∴所求的概率 Pn= = N (2n)! 信号源 变式:(06 江苏) 右图中有一个信号源和五个接收 器。接收器与信号源在同一个串联线路中时,就能接收 到信号,否则就不能接收到信号。若将图中左端的六个 接线点随机地平均分成三组,将右端的六个接线点也随 机地平均分成三组,再把所有六组中每组的两个接线点 用导线连接,则这五个接收器能同时接收到信号的概率 是(D) 4 1 4 8 (A) (B) (C) (D) 45 36 15 15 四、an+1=p·n+q·n-1 型 a a 1 【例6】 某人玩硬币走跳棋的游戏。已知硬币出现正反面的概率都是 ,棋盘上标有 2 第 0 站、第 1 站、第 2 站、……、第 100 站.一枚棋子开始在第 0 站,棋手每掷一次硬币, 棋子向前跳动一次,若掷出正面,棋子向前跳一站(从 k 到 k+1);若掷出反面,棋子向前跳 两站(从 k 到 k+2),直到棋子跳到第 99 站(胜利大本营)或跳到第 100 站(失败集中营)时,该 游戏结束.设棋子跳到第 n 站的概率为 Pn. (1)求 P0、P1、P2 的值; 1 (2)求证:Pn-Pn-1=- (Pn-1-Pn-2),其中 n∈ N,2≤n≤99; 2 (3)求玩该游戏获胜的概率及失败的概率。 (1)解:棋子开始在第 0 站为必然事件,P0=1. 1 1 第一次掷硬币出现正面,棋子跳到第 1 站,其概率为 ,P1= . 2 2 棋子跳到第 2 站应从如下两方面考虑: 1 1 ① 前两次掷硬币都出现正面,其概率为 ;② 第一次掷硬币出现反面,其概率为 . 4 2 1 1 3 ∴ 2= + = . P 4 2 4 (2)证明:棋子跳到第 n(2≤n≤99)站的情况是下列两种,而且也只有两种: 1 ① 棋子先到第 n-2 站,又掷出反面,其概率为 Pn-2; 2

1 ② 棋子先到第 n-1 站,又掷出正面,其概率为 Pn-1. 2 1 1 ∴ n= Pn-2+ Pn-1. P 2 2 1 ∴ n-Pn-1=- (Pn-1-Pn-2). P 2 1 1 (3)解:由(2)知当 1≤n≤99 时,数列{Pn-Pn-1}是首项为 P1-P0=- ,公比为- 的等比 2 2 数列。 1 1 1 1 ∴ 1-1=- ,P2-P1=(- )2,P3-P2=(- )3,…,Pn-Pn-1=(- )n. P 2 2 2 2 1 12 1n 以上各式相加,得 Pn-1=(- )+(- ) +…+(- ) , 2 2 2 1 12 1n 2 1 n+1 ∴ n=1+(- )+(- ) +…+(- ) = [1-(- ) ](n=0,1,2,…,99). P 2 2 2 3 2 2 1 100 ∴ 获胜的概率为 P99= [1-( ) ], 3 2 1 12 1 1 1 失败的概率 P100= P98= ·[1-(- )99]= [1+( )99] 2 23 2 3 2 【例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。 ? ? 2 【例8】 从原点出发的某质点 M,按向量 a =(0,1)移动的概率为 ,按向量 b =(0,2) 3 1 移动的概率为 ,设 M 可到达点(0,n)的概率为 Pn 3 1 (1)求 P1 和 P2 的值;(2)求证:Pn+2-Pn+1=- (Pn+1-Pn);(3)求 Pn 的表达式。 3 2 22 1 7 解析:(1)P1= ,P2=( ) + = 3 3 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)。 2 1 ∴ n+2= Pn+1+ Pn P 3 3 1 ∴ n+2-Pn+1=- (Pn+1-Pn) P 3 1 (3)数列{Pn+1-Pn}是以 P2-P1 为首项,- 为公比的等比数列。 3 1 n-1 1 1 n-1 1 n+1 Pn+1-Pn=(P2-P1)(- ) = (- ) =(- ) , 3 9 3 3 1n ∴ n-Pn-1=(- ) P 3 1 1 1 1 1 又∵ n-P1=(Pn-Pn-1)+(Pn-1-Pn-2)+…+(P2-P1)=(- )n+(- )n-1+…+(- )2=( )[1-(- )n-1] P 3 3 3 12 3 1 1 n-1 3 1 1 n ∴ n=P1+( )[1-(- ) ]= + × ) 。 P (12 3 4 4 3


推荐相关:

排列组合与数列递推关系

例析排列组合、概率问题中的递推数列一、an=p·n-1+q 型 a 【例1】 某种电路开关闭合后,会出现红灯或绿灯闪动,已知开关第一次闭合后,出 1 1 现红灯...


递推法解排列组合问题

递推法解排列组合问题_理学_高等教育_教育专区。递推法解排列组合问题递...由分步计数原理和分类计数原理,我们便得到了数列 { a n } 的递推关系式: a...


2014精品系列 排列组合二项式递推数列求通项常见

排列组合的常见题型及其解法 排列、组合的概念具有广泛的实际意义,解决排列、组合问题,关键要搞清楚是否与元素的顺序有 关。复杂的排列、组合问题往往是对元素或位置...


排列组合二项式递推数列求通项常见

因此可以用近似计算公式: (1 + x) n ≈ 1 + nx , 排列组合二项式递推数列求通项 递推数列求通项常见题型解法自用资料集 递推数列求通项在使用这个公式时...


组合数学讲义 3章 递推关系

组合数学第六章递推关系 45页 免费 组合数学讲义 1章 排列组合... 67页 2...a0、1、 、 就是指根据式 或求 an-1 无关的解析表达式或数列 n}的母函数...


组合数学-第十节:递推关系

组合数学讲义 1章 排列组合... 67页 2财富值 用生成函数求线性递推数列... 3页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点...


递推法解排列、组合及概率问题

递推法解排列、 递推法解排列组合及概率问题刘东林 (广东省普宁市第二中学...由分步计数原理和分类计数原理,我们便得到了数列 {a n } 的递推关系式: a ...


数列、排列组合、二项式定理、概率统计知识点总结

数列排列组合二项式定理知识点总结 1. 等比数列的定义与性质 定义: a n +1...(4)等比型递推公式 a n = ca n 1 + d c、d为常数,c ≠ 0,c ≠ ...


第六讲 数列与递推方法

有界性与数列不等式的证明、构建递推公式实现运算...Z }中所有的数从小到大排列成的数列,即 a1 ? 3...(单位: mm )七、基于组合思考的数列题 例 39(...


数列、排列组合的精讲与习题讲解

数列排列组合的精讲与习题讲解 数列排列组合的精讲与习题讲解数列归纳法 递归数列 满足递推公式数列称为递归数列。 特征方程 1. 设 a 0 = 1,a1 ,a ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com