递推关系在组合计数中的若干应用.doc

递推关系在组合计数中的若干应用我们思考一个数学问题，有时可以跳出它的范围去思考一个比它更为一般的问题，而一般的问题有时比特殊的问题更容易解决，或是解决了一般的问题就能够得到一系列类似问题的结果，这就是“特殊问题一般化”的数学思想联系到组合计数问题，通过构造数列将问题一般化并建立递推关系进行求解，这便是上述数学思想的典型应用本文试结合实例，探讨递推关系在组合计数中的若干应用，以供参考例1 身高两两不等的10个人排成一列，每个人比前面的人都高或比前面的人都矮，则符合条件的排法共有多少种？分析：若直接计算，该问题的分类情况比较复杂不妨将10个人的情形一般化，改为研究个人的情形，引入数列，并结合题设条件建立相邻项之间的递推关系，最终达到求解原问题的目的解：不妨先考虑个人的情形依题意，排在最后一位的人必是最高或最矮的若不然，前个人中既有比第位高的人，又有比第位矮的人，这与已知条件矛盾所以，第位上的人只有两种可能若设符合题意的个人情形下的排法有种，则，又，所以于是，即为所求注：例1所构造的是一个典型的等比型递推关系，但是在大多数情况下我们将问题一般化后所得到的数列可能既不是等差型的，也不是等比型的，这时可以考虑对原来的递推关系进行适当的变型，使之转化为我们所熟悉的等差型或等比型数列下面的例2便是这样的一个例子例2 数码中有奇数个9的2007位十进制数的个数为（ ） （2006年全国高中数学联赛一试第6题）解：我们先看一般情况，设数码中有奇数个9的位十进制数的个数为考察位十进制数的前位数可知：为使中有奇数个9，若中有奇数个9，则可以是9以外的其余9个数码；若中有偶数个9，则必须是9由分类计数原理知，又整理得 即 所以，数列是以为首项，以为公比的等比数列于是， 即知 所以 ， 故选B注：通过例1和例2的分析，我们可以发现，建立递推关系求解组合计数问题，解决的不仅仅是一个具体的问题，而是一系列类似的问题因此，这种方法更能揭示问题的数学本质下面，再结合例3的分析、引申、应用，进一步地阐释递推关系在求解组合计数问题方面的重要价值EFDCBA例3 如图所示，在一个正六边形的六个区域栽种观赏植物要求同一区域中种同一种植物，相邻的两个区域种不同的植物现有4种不同的植物可供选择，则共有 种不同的栽种方案（2001年全国高中数学联赛一试第12题）解：为方便起见，将六个区域按顺时针方向依次标为（1）若栽种同一种植物，则有种方法；（2）若栽种两种植物，则有种方法；（3）若栽种三种植物，则有种方法所以，根据分类计数原理，总共有108+432+192732种不同的栽种方案分析：对于区域数较大的情况，上述解法不易推广，因而不具有普遍性为此，我们把例3的问题一般化，并建立递推关系运用两种不同的方法给出其一般解引申：将圆分为个扇形，依顺时针方向依次标记为每个扇形用种不同颜色之一进行染色，要求相邻扇形所染的颜色不同试问，有多少种不同的染色方法？解法1：设将圆分为个扇形时有种符合要求的染色方法现在从开始依次染色，使得除和外相邻两扇形皆不同色，共有种方法其中，与异色时，有种；与同色时，可考虑将与合并为一个区域，则有种染法因此，且易知，于是 所以，数列是以为首项，以为公比的等比数列，则 即 解法2：数列的定义同解法1考察与的关系，可将个扇形下的符合要求的染色方法分为如下两种情形：（1）若与同色，可考虑将与连通为一个区域，则有种染法，到有种染法，由分步计数原理知，此种情形下有种染法；（2）若与异色，则有种染法，到有种染法，由分步计数原理知，此种情形下有种染法因此， 其特征根方程为 解得两个特征根为 故可设 又易知 ，由待定系数法求得，于是 注：事实上，例3即时的特殊情形，故只要解决了一般性的问题，特殊性的问题也就迎刃而解了下面的例4，也是上述一般情形下的一个特例例4 一副纸牌共52张，其中黑红梅方各13张，标号依次为2，3，10，J，Q，K，A，其中相同花色，相邻标号的两张纸牌称为“同花顺牌”，并且同花色的A与2也算是同花顺牌（即A可以当成1使用）试确定，从这副牌中取出13张纸牌，使每种标号的牌都出现，并且不含同花顺牌的取牌方法数（2006年第三届东南地区数学奥林匹克第一天第3题）略解：此题即例3的引申在时的特殊情形，故所求方法数为在运用递推关系解决计数问题时，有时仅仅引入一个数列还不能够方便地解决问题，此时可以考虑同时引入两个或两个以上的相关数列，联合求解请看下面的例5例5 称子集是“好”的，如果它具有如下性质：如果，则（空集和都是“好”的）问：有多少个“好”子集？（2001年西班牙高中数学竞赛题5） 解：我们考虑一般情形,设表示集合中“好”子集的个数，则表示集合中包含元素的“好”子集的个数易知：；由于故可以将集合的“好”子集分为两类：一类不含元素，则元素可有可无，有个；另一类含元素，则必含元素，有个于是，另一方面，集合中包含元素的“好”子集亦可分为两类：一类包含元素，则必含元素，有个；另一类不含元素，有个于是由知，代入可得于是，即知，有233个“好”子集注