排列组合递推思想的应用.c

传承数列思想解答排列组合四题型我知道数列中有一类问题就是通过递推关系式求出数列的通项公式或数列中的某一项。这类问题需要对题设中所给出的递推关系式进行分析、推理、变形等处理，发现规律才能达到所要解决问题的目的。同样，在排列组合问题中也存在类似的解决问题的方法。所谓的递推法就是按照某种标准找出递推关系式，并求出n取第一个值(或前几个值)时的各项，然后代入递推关系式，得出所要求的结果。用递推法，无论是解答数列问题还是解答排列组合问题，它们有一个相同之处就是寻找----递推关系式。题型一.走楼梯问题例1：欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有()（A）34种（B）55种（C）89种（D）144种解法1：分类法：第一类：没有一步两级，则只有一种走法；第二类：恰有一步是一步两级，则走完10级要走9步，9步中选一步是一步两级的，有919C种可能走法；第三类：恰有两步是一步两级，则走完10级要走8步，8步中选两步是一步两级的，有2828C种可能走法；依此类推，共有55463728191CCCCC=89，故选(C)。解法2：递推法：设走n级有na种走法，这些走法可按第一步来分类，第一类：第一步是一步一级，则余下的1n级有1na种走法；第二类：第一步是一步两级，则余下的2n级有2na种走法，于是可得递推关系式21nnnaaa，又易得2,121aa，由递推可得8910a，故选(C)。解答该题也可以由找出的递推关系21nnnaaa，求出通项na，但对于选择填空题，我们不必大动干戈的去求通项，因为这样太浪费时间与精力。题型二.更列问题例2：五个人排成一列，重新站队时，各人都不站在原来的位置上，那么不同的站队方式共有多少种？解析：首先我们把人数推广到n个人，即n个人排成一列，重新站队时，各人都不站在原来的位置上。设满足这样的站队方式有na种，现在我们来通过合理分步，恰当分类找出递推关系：第一步：第一个人不站在原来的第一个位置，有1n种站法。第二步：假设第一个人站在第2个位置，则第二个人的站法又可以分为两类：第一类，第二个人恰好站在第一个位置，则余下的2n个人有2na种站队方式；第二类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第三个位置，第四个人不站在第四个位置，……，第n个人不站在第n个位置，所以有1na种站队方式。由分步计数原理和分类计数原理，我们便得到了数列}{na的递推关系式：))(1(12nnnaana，显然，1,021aa，再由递推关系有9,243aa，445a，故共有44种.题型三.染色问题例3：用4种不同颜色涂四边形的4个顶点，要求每点染一种颜色，相邻的顶点染不同的颜色，求不同的染色方法种数。解析：我们先把这个题目推广：用m种不同颜色给n边形nAAA21的n个顶点染色(其中3,3nm，且m为常数)，每点染一种颜色，相邻的顶点染不同的颜色，不同的染色方法有多少种？设不同的染色方法有na种，现在我们来通过合理分布，恰当分类找出递推关系：第一步：染1A，有m种染法；第二步：染2A，有1m种染法；同理，染13,,nAA均有1m种染法，最后染nA，如果仅考虑nA与1nA不同色，则仍有1m种染法，相乘得1)1(nmm种染法，但要去掉nA与1A同色的染法数，此时可将nA与1A合并看成一个点，得出需要排除的染法数为1na，所以有11)1(nnnamma，显然，33mAa。又本题中，颜色数4m，所以递推关系为：1134nnnaa，又24343Aa，所以8434334aa（种），故不同的染色方法种数有84种。题型四.传球问题例4：甲、乙、丙、丁四人相互传球，第一次甲传给乙、丙、丁中的任一人，第二次由拿球者再传给其他人中任一人，这样共传了四次，求第四次球仍传回到甲的方法种数。解析：先把这个题目进行推广：)(Nmm个人相互进行)(Nnn次传球，由甲先传，第一次甲传给其他1m个人中的任一人，第二次由拿球者再传给其他人中任一人，这样经过n次传球，最后球仍回到甲手中的传球方法有多少种？(这里m为常数)设不同的传球方法共有na种，现在我们来通过合理分步，恰当分类找出递推关系：第一步进行第一次传球：甲传给其他人，有1m种传球方法；第二步进行第二次传球：拿球者把球传给其他人，仍有1m种传球方法；同理，第三次、第四次、……、第1n次传球都有1m种传球方法，最后进行第n次传球，由于只能传给甲，故只有一次传球方法，相乘得1)1(nm种传球方法，但要注意第1n次传球不能传给甲，否则就不存在第n次传球，因此要去掉第1n次传球，球恰好传给甲的传球方法数，这就是由甲先传，经过1n次传球后球又回到甲手中的传球方法，显然，这里有1na种传球方法，所以有递推关系：11)1(nnnama，又易得01a。而在本题中，4m，所以113nnnaa，所以由递推可得，3312aa，213,63334223aaaa，故第四次球仍传回到甲的方法种数共有21种。从上面的解答与分析我们可以看到，用递推法解答排列组合问题的关键所在就是得到递推关系式。