组合专题：组合递推模型建立

组合专题：组合递推模型的建立 梁久阳 前言： 递推模型是组合数学中一个独特的分支，它让人感觉既漂亮又神奇，将前一项与后一项之间难以言说的关系用一个简单的式子就能表现出来，可以说是十分奇妙。一什么是递推递推关系的定义是：给定一个数的序列H(0),H(1), H(n),若存在正整数n0，使得当nn0时，可以用等号(或小于，大于号)把H(n)和前面某些项H(i)，0 i n，联系起来，这样的式子叫做递推关系。 递推关系也称递归关系，递归方程。从本质上讲，递推关系是研究整变量函数的或者说是研究数列的，与此对应的是连续论域中的微分方程。因此，我们可以类似的方法对它们进行研究。利用递推关系和初值在某些情况下可以求出序列的通项表示式H(n) 。 但是对于大多数递推关系，目前还解不出H(n)的显式来， 即使这样，对于给定的n也可以从初值开始，一步一步地计算出H(n)的值或者范围，而H(n)一般代表了某个组合计数问题的解，因此递推关系是组合计数的重要工具，同时也是算法分析的重要手段。 我们需要研究的，只限于高中课本和竞赛书上的内容，其他的大学再说。二经典例题分析（按类型划分）（1）an=pan1+q型【例1】某种电路开关闭合后，会出现红灯或绿灯闪动，已知开关第一次闭合后，出现红灯和绿灯的概率都是，从开关第二次闭合起，若前次出现红灯的概率是，出现绿灯的概率是；若前次出现绿灯，则下次出现红灯的概率是，出现绿灯的概率是，记开关第n次闭合后出现红灯的概率为Pn.(1)求：P2；(2)求证：Pn(n2)；(3)求.解：(1)第二次闭合后出现红灯的概率P2的大小决定于两个互斥事件：即第一次红灯后第二次又是红灯；第一次绿灯后第二次才是红灯.于是P2=P1+(1P1)=.(2)受(1)的启发，研究开关第N次闭合后出现红灯的概率Pn，要考虑第n1次闭合后出现绿灯的情况，有Pn=Pn1+(1Pn1)=Pn1+，再利用待定系数法：令Pn+x=(Pn1+x)整理可得x=Pn为首项为(P1)、公比为()的等比数列Pn=(P1)()n1=()n1，Pn=+()n1当n2时，Pn+=(3)由(2)得=.【例2】A、B两人拿两颗骰子做抛掷游戏，规则如下:若掷出的点数之和为3的倍数时，则由原掷骰子的人继续掷；若掷出的点数不是3的倍数时，由对方接着掷.第一次由A开始掷.设第n次由A掷的概率为Pn，(1)求Pn；求前4次抛掷中甲恰好掷3次的概率.解：第n次由A掷有两种情况： 第n1次由A掷，第n次继续由A掷，此时概率为Pn1； 第n1次由B掷，第n次由A掷，此时概率为(1)(1Pn1).两种情形是互斥的Pn=Pn1+(1)(1Pn1)(n2)，即Pn=Pn1+(n2)Pn=(Pn1)，(n2)，又P1=1Pn是以为首项，为公比的等比数列.Pn=()n1，即Pn=+()n1.（2）an+1=pan+f(n)型【例3】(传球问题)A、B、C、D4人互相传球，由A开始发球，并作为第一次传球，经过5次传球后，球仍回到A手中，则不同的传球方式有多少种？若有n个人相互传球k次后又回到发球人A手中的不同传球方式有多少种？分析：这类问题人数、次数较少时常用树形图法求解，直观形象，但若人数、次数较多时树形图法则力不从心，而建立递推数列模型则可深入问题本质.解：4人传球时，传球k次共有3k种传法.设第k次将球传给A的方法数共有ak(kN*)种传法，则不传给A的有3kak种，故a1=0，且不传给A的下次均可传给A，即ak+1=3kak。两边同除以3k+1得=+，令bk=，则b1=0，bk+1=(bk)，则bk=()k1ak=+(1)k当k=5时，a5=60.当人数为n时，分别用n1，n取代3，4时，可得ak= + (1)k.123nn-1【例4】(环形区域染色问题)将一个圆环分成n(nN*，n3)个区域，用m(m3)种颜色给这n个区域染色，要求相邻区域不使用同一种颜色，但同一颜色可重复使用，则不同的染色方案有多少种？解：设an表示n个区域染色的方案数，则1区有m种染法，2区有m1种染法，3，n1，n区各有m1种染色方法，依乘法原理共有m(m1)n1种染法，但是，这些染中包含了n区可能和1区染上相同的颜色.而n区与1区相同时，就是n1个区域涂上m种颜色合乎条件的方法.an=m(m1)n1an1，且a3=m(m1)(m2)an(m1)n=an1(m1)n1123456123456an(m1)n=a3(m1)3(1)n3an=(m1)n+(m1)(1)n(n3)用这个结论解2003年高考江苏卷中的一道试题：某城市在中心广场建一个花圃，花圃分为6个部分如图，现要栽种4种不同颜色的花且相邻部分不能同色，由不同的栽种方法有 种.只需将图变形为圆环形，1区有4种栽法.不同的栽法数为N=4a5=120.三、an+1=anf(n)型【例5】(结草成环问题)现有n(nN*)根草，共有2n个草头，现将2n个草头平均分成n组，每两个草头打结，求打结后所有草能构成一个圆环的打结方法数.3412562n-12n解：将2n个草头平均分成n组，每两个草头打结，要使其恰好构成圆环，不同的连接方法总数m2=an.将草头编号为1，2，3，2n1，2n.草头1可以和新草头3，4，5，2n1，2n共2n2个新草头相连，如右图所示.假设1和3相连，则与余下共n1条相连能成圆环的方法数为an1.an=(2n2)an1，(n2，nN*)，a1=1，得=2n2an=a1=(2n2)(2n4)21=2n1(n1)!【例6】（上题变式）某人手中握有2n(nN*)根草，只露出两端的各自2n个草头，现将两端的2n个草头各自随机平均分成n组，并将每组的两个草头连接起来，最后松手，求这时所有的草恰好构成一个圆环的概率.解：两端的2n个草头随机两个相连不同的方法数为N=()2能够构成圆环的连接方法分两步：第一步，先将一端的2n个草头平均分成n组，每两根连接起来，得到n组草，认为得到n根“新草”，连接方法数m1=.信号源第二步，将另一端的2n个草头平均分成n组连接起来，要使其恰好构成圆环，不同的连接方法总数m2=2n1(n1)!.所求的概率Pn=.【例7】又一变式：( 江苏) 右图中有一个信号源和五个接收器。接收器与信号源在同一个串联线路中时，就能接收到信号，否则就不能接收到信号.若将图中左端的六个接线点随机地平均分成三组，将右端的六个接线点也随机地平均分成三组，再把所有六组中每组的两个接线点用导线连接，则这五个接收器能同时接收到信号的概率是(D)（A）（B） （C）（D）（4）an+1=pan+qan1型【例8】某人玩硬币走跳棋的游戏.已知硬币出现正反面的概率都是，棋盘上标有第0站、第1站、第2站、第100站.一枚棋子开始在第0站，棋手每掷一次硬币，棋子向前跳动一次，若掷出正面，棋子向前跳一站(从k到k+1)；若掷出反面，棋子向前跳两站(从k到k+2)，直到棋子跳到第99站(胜利大本营)或跳到第100站(失败集中营)时，该游戏结束.设棋子跳到第n站的概率为Pn.(1)求P0、P1、P2的值；(2)求证：PnPn1=(Pn1Pn2)，其中nN，2n99；(3)求玩该游戏获胜的概率及失败的概率.(1)解：棋子开始在第0站为必然事件，P0=1.第一次掷硬币出现正面，棋子跳到第1站，其概率为，P1=.棋子跳到第2站应从如下两方面考虑：前两次掷硬币都出现正面，其概率为；第一次掷硬币出现反面，其概率为.P2=+=.(2)证明：棋子跳到第n(2n99)站的情况是下列两种，而且也只有两种：棋子先到第n2站，又掷出反面，其概率为Pn2；棋子先到第n1站，又掷出正面，其概率为Pn1.Pn=Pn2+Pn1.PnPn1=(Pn1Pn2).(3)解：由(2)知当1n99时，数列PnPn1是首项为P1P0=，公比为的等比数列.P11=，P2P1=()2，P3P2=()3，PnPn1=()n.以上各式相加，得Pn1=()+()2+()n，Pn=1+()+()2+()n=1()n+1(n=0，1，2，99).获胜的概率为P99=1()100，失败的概率P100=P98=1()99=1+()99.【例9】 (上楼梯问题)从教学楼一楼到二楼共有15级楼梯，学生A一步能上1级或2级，那么A从一楼上到二楼的不同方法数共有多少种？设上到第n级楼梯的方法数为an(nN)，则a1=1，a2=2，an=an1+an2(n3)，由此可得,an斐波那契数列：1，2，3，5，8，得a13=377，a14=610，a15=987。【例10】从原点出发的某质点M，按向量=(0，1)移动的概率为，按向量=(0，2)移动的概率为，设M可到达点(0，n)的概率为Pn(1)求P1和P2的值；(2)求证：Pn+2Pn+1=(Pn+1Pn)；(3)求Pn的表达式.解：(1)P1=，P2=()2+=(2)证明：M到达点(0，n+2)有两种情况：从点(0，n+1)按向量=(0，1)移动，即(0，n+1)(0，n+2)从点(0，n)按向量=(0，2)移动，即(0，n)(0，n+2).Pn+2=Pn+1+PnPn+2Pn+1=(Pn+1Pn)(3)数列Pn+1Pn是以P2P1为首项，为公比的等比数列.Pn+1Pn=(P2P1)()n-1=()n-1=()n+1，PnPn1=()n,又PnP1=(PnPn1)+(Pn1Pn2)+(P2P1)=()n+()n-1+()2=()1()n-1 Pn=P1+()1()n-1=+()n.三古老的递推问题（1）Fibonacci数列问题是一个古老的数学问题，是于1202年提出的，问题表述如下: 把一对兔子（雌、雄各一只）在某年的开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。由第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只。问一年后围栏中有多少对兔子？（这是一个数学模型的形象表示，不能真正用来表示兔子的繁殖规律。）解：对于n=1,2,令f(n)表示第n个月开始时围栏中的兔子对数，显然有f(1)=1,f(2)=2。在第n个月的开始，那些第n-1个月初已经在围栏中的兔子仍然存在，而且每对在第n-2个月初就存在的兔子将在第n-1个月开始将要生出一对新兔来，所以有： f(n)=f(n-1)+f(n-2) (n3, n为整数) f(1)=1,f(2)=2这是一个带有初值的递推关系。如果规定f(0)=1,则上式变成： f(n)=f(n-1)+f(n-2) (n2, n为整数) f(0)=1,f(1)=1称满足这个式子的数列就成为Fibonacci数列，数列中的项叫做Fibonacci数.（2）（汉诺塔问题）现有A，B，C三根立柱以及n个大小不等的中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如图6.1.1所示，要把n个圆盘从A柱上搬到C柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上，问至少要搬多少次 ？解：记f(n)为n个圆盘从A柱搬到C柱所需的最小次数.整个搬运过程可分成三个阶段；（1）将套在A柱上面的n-1个圆盘从A柱按要求搬到B柱，搬动 次数为f(n-1);（2）把A柱上最下面的那个圆盘搬到C柱上，搬动次数为1;（3）把B柱上的n-1个圆盘按要求搬到C柱上，搬动次数为f(n-1);由加法原则知， f(n)=2f(n-1)+1又显然f(1)=1，所以有如下带有初值的递推关系: f(n)=2f(n-1)+1 f(1)=1（3）（信号串问题）在信道上传输由a ,b, c三个字母组成的长为n的字符串，若字符串有两个a连续出现，则信道就不能传输，令f(n)表示信道可以传输的长为n的字符串的字数，求f(n)满足的递推关系。解：信道上能够传输的长度为n的字符串可分成四类： （1）最左字符为b； （2）最左字符为c； （3）最左两个字符为ab； （4）最左两个字符为ac。前两类字符串分别有f(n-1)个，后两类字符串分别有f(n-2)个，容易求出f(