例析排列、组合、概率问题中的递推数列一、an=p·an－1+q型【例1】某种电路开关闭合后，会出现红灯或绿灯闪动，已知开关第一次闭合后，出现红灯和绿灯的概率都是，从开关第二次闭合起，若前次出现红灯的概率是，出现绿灯的概率是；若前次出现绿灯，则下次出现红灯的概率是，出现绿灯的概率是，记开关第n次闭合后出现红灯的概率为Pn。(1)求：P2；(2)求证：Pn<(n≥2)；(3)求。解析：(1)第二次闭合后出现红灯的概率P2的大小决定于两个互斥事件：即第一次红灯后第二次又是红灯；第一次绿灯后第二次才是红灯。于是P2=P1·+(1－P1)·=。(2)受(1)的启发，研究开关第N次闭合后出现红灯的概率Pn，要考虑第n－1次闭合后出现绿灯的情况，有Pn=Pn－1·+(1－Pn－1)·=－Pn－1+，再利用待定系数法：令Pn+x=－(Pn－1+x)整理可得x=－{∴Pn－}为首项为(P1－)、公比为(－)的等比数列Pn－=(P1－)(－)n－1=(－)n－1，Pn=+(－)n－1∴当n≥2时，Pn<+=(3)由(2)得=。【例2】A、B两人拿两颗骰子做抛掷游戏，规则如下:若掷出的点数之和为3的倍数时，则由原掷骰子的人继续掷；若掷出的点数不是3的倍数时，由对方接着掷.第一次由A开始掷.设第n次由A掷的概率为Pn，(1)求Pn；⑵求前4次抛掷中甲恰好掷3次的概率.解析：第n次由A掷有两种情况：①第n－1次由A掷，第n次继续由A掷，此时概率为Pn－1；②第n－1次由B掷，第n次由A掷，此时概率为(1－)(1－Pn－1)。 两种情形是互斥的∴Pn=Pn－1+(1－)(1－Pn－1)(n≥2)，即Pn=－Pn－1+(n≥2)∴Pn－=－(Pn－1－)，(n≥2)，又P1=1{∴Pn－}是以为首项，－为公比的等比数列。∴Pn－=(－)n－1，即Pn=+(－)n－1。⑵。二、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得=－·+，令bk=，则b1=0，bk+1－=－(bk－)，则bk－=－(－)k－1∴ak=+(－1)k当k=5时，a5=60.当人数为n时，分别用n－1，n取代3，4时，可得ak=+(－1)k。【例4】(环形区域染色问题)将一个圆环分成n(n∈N*，n≥3)个区域，用m(m≥3)种颜色给这n个区域染色，要求相邻区域不使用同一种颜色，但同一颜色可重复使用，则不同的染色方案有多少种？分析：设an表示n个区域染色的方案数，则1区有m种染法，2区有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]an－(m－1)n=[a3－(m－1)3](－1)n－3∴an=(m－1)n+(m－1)(－1)n(n≥3)用这个结论解：2003年高考江苏卷：某城市在中心广场建一个花圃，花圃分为6个部分如图，现要栽种4种不同颜色的花且相邻部分不能同色，由不同的栽种方法有种。只需将图变形为圆环形，1区有4种栽法。不同的栽法数为N=4a5=120。三、an+1=an·f(n)型【例5】(结草成环问题)现有n(n∈N*)根草，共有2n个草头，现将2n个草头平均分成n组，每两个草头打结，求打结后所有草能构成一个圆环的打结方法数。分析：将2n个草头平均分成n组，每两个草头打结，要使其恰好构成圆环，不同的连接方法总数m2=an。将草头编号为1，2，3，……，2n－1，2n。草头1可以和新草头3，4，5，……，2n－1，2n共2n－2个新草头相连，如右图所示。假设1和3相连，则与余下共n－1条相连能成圆环的方法数为an－1。∴an=(2n－2)an－1，(n≥2，n∈N*)，a1=1，得=2n－2an=··……··a1=(2n－2)(2n－4)……2×1=2n－1(n－1)!变式游戏：某人手中握有2n(n∈N*)根草，只露出两端的各自2n个草头，现将两端的2n个草头...
