枚举法在有关计数原理问题中的应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇枚举法在有关计数原理问题中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
数学中有一类问题，从整体是找不到统一的解决方法，似乎无从下手．但是，如果题目所述的情况或满足题目要求的对象能够被一一列举，或分类列举出来，那么问题就可以获得解决．这种为了解题的方便把问题分为不重不漏的有限情况，一一列举出来加以分析、解决的方法叫做枚举法，也叫列举法或穷举法．按照枚举情形或类别的多少我们可将枚举法分为直接枚举与分类枚举．枚举法在归纳推理、数列、概率、计数问题中都起到了一定作用．下面我们来谈谈枚举法在计数问题中的应用．
一、 直接枚举
计数问题中，当可能的结果很少时，可以直接枚举，即将所有结果一一列举出来．
例1 运输队有30辆汽车，按1～30的编号顺序横排停在院子里．第一次陆续开走的全部是单号车，以后几次都由余下的第一辆车开始隔一辆开走一辆．到第几次时汽车全部开走？最后开走的是第几号车？
分析与解
按题意画出下表：
汽车编号
开走前1， 2， 3， …， 29， 30第一次开走后剩下的2， 4， 6， 8， 10， 12， 14， 16， 18， 20， 22， 24， 26， 28， 30
第二次开走后剩下的4， 8， 12， 16， 20， 24， 28
第三次开走后剩下的8， 16， 24第四次开走后剩下的16
从上表看出，第三次开走后剩下的是第8号、16号、24号车．按题意，第四次8号、24号车开走．到第五次时汽车全部开走，最后开走的是第16号车．
例2 小明的暑假作业有语文、算术、外语三门，他准备每天做一门，且相邻两天不做同一门．如果小明第一天做语文，第五天也做语文，那么，这五天作业他共有多少种不同的安排？
分析与解
本题是分步进行一项工作，每步有若干种选择，求不同安排的种数（有一步差异即为不同的安排）．这类问题中简单一些的可用乘法原理与加法原理来计算，而本题中由于限定条件较多，很难列出算式计算．但是，我们可以根据实际的安排，对每一步可能的选择画出一个树状图，非常直观地得到结果．这样的图不妨称为“枚举树”．
由上图可知，共有6种不同的安排．
二、 分类枚举
计数应用题中，当可能的结果较多且问题繁杂时，我们就抓住对象的特征，选择恰当的标准，把问题分为不重复、不遗漏的有限种情形，通过一一列举或计数，最终达到解决的目的，我们把这种枚举称为分类枚举，分类枚举又可分为两大类：按逻辑顺序一一分类枚举和部分分类枚举．
1 按逻辑顺序一一分类枚举
例3 将数字1， 2， 3， 4填入标号为1， 2， 3， 4的四个方格里，每格填一个数字，则每个方格的标号与所填的数字均不相同的填法有 种．
分析与解
当问题结果数目不大，解决办法也不一般，采用枚举法有时能取得意想不到的效果．显然这个问题难用两个原理列式计算，但可以把各种方法一一列举出来，本题我们可按1号格子中的数字进行分类：数字2填在标号为1的格子中的不同填法有：2143， 2341， 2413共3种；数字3填在标号为1的格子中的不同填法有：3142， 3412， 3421共3种；数字4填在标号为1的格子中的不同填法有：4123， 4312， 4321共3种.故共有9种不同的填法．
【变式1】 将1， 2， 3， 4变为1， 2， 3， 4， 5，如何解决？
【变式2】 将1， 2， 3， 4变为1， 2， …， n呢？
分析
变式1仍可用枚举法，但结果已经很烦琐；对于变式2，我们可将这类问题进行推广：集合
{1, 2, …, n}的一个排列{a1, a2, …, an}中，如果ai≠i (i=1, 2, …, n)，则称这种排列为一个错位排列（也称更列），则错位排列的个数为Dn=Ann－An－1n+…+(－1)nA0n，有兴趣的同学可以自己研究一下．
通过此例我们可体会出枚举法的优点和缺点及其适用范围．
例4 （2010届湖南）在某种信息传输过程中，用4个数字的一个排列（数字允许重复）表示一个信息，不同排列表示不同信息．若所用数字只有0和1，则与信息0110至多有两个对应位置上的数字相同的信息个数为 .
分析与解
本题要求至多有两个对应位置上的数字相同，应按照0个相同、1个相同、2个相同进行讨论，本题易错点是易漏掉0个相同的情况．
(1) 若0个相同，则信息为：1001，共1个；
(2) 若1个相同，则信息为：0001，1101，1011，1000，共4个；
(3) 若2个相同，又分为以下情况：
② 若位置一与二相同，则信息为：0101；
③ 若位置一与三相同，则信息为：0011；
④ 若位置一与四相同，则信息为：0000；
⑤ 若位置二与三相同，则信息为：1111；
⑥ 若位置二与四相同，则信息为：1100；
⑦ 若位置三与四相同，则信息为：1010．
共6个．
故与信息0110至多有两个对应位置上的数字相同的信息个数为11个．
说明
本题考查的是分类计数原理，难度不大，故可用枚举法，近年高考所考此类问题的方法数都不是很多，大多可采用这种方法．当然本题还有另一种解法：若0个相同，共有1个；若1个相同，共有C14=4个；若2个相同，共有C24=6个，所以共有11个．
2 部分分类枚举
有些计数应用题结果比较多，先分类，但每类之间又有一定的规律，故我们只须枚举出其中一类中的结果，通过规律求出所有的结果．
例5 正五棱柱中，不同在任何侧面且不同在任何底面的两顶点的连线称为它的对角线，那么一个正五棱柱对角线共有多少条？
分析与解
本题中，结果不必一一列举，从中能发现一定的规律．在正五棱柱ABCDEA1B1C1D1E1中，从顶点A出发的对角线有两条：AC1， AD1，同理从B， C， D， E点出发的对角线也有两条，根据计数原理，正五棱柱共有10条对角线．
例6 在如图2的矩形长条中涂上红、黄、蓝三种颜色，每种颜色限涂两格，且相邻两格颜色不同，则不同的涂色方法共有 种．
分析与解
对于元素个数不多，运用公式又不好解决的问题，进行具体的排列组合，也是很好的方法．
以左边第一格涂红色，第二格涂黄色为例，可涂“红黄红蓝黄蓝；红黄蓝红黄蓝；红黄蓝红蓝黄；红黄蓝黄红蓝；红黄蓝黄蓝红”.
总结规律知，不同的涂色方法共有30种．
使用枚举法计数时，要注意以下几点：初步估计，总的数目不太多，又没有更简捷的办法；为了使枚举的结果不重复又不遗漏，我们要抓住对象的特征，选择适当的标准分类，有次序、有规律地列举．
枚举法尽管解决的是方法数不是很多的问题，但是通过列举，能够探求出规律，列出解决问题的式子，这种思想在归纳推理、数列有关问题中体现得淋漓尽致．两个计数原理的推导实例是用了枚举法得以求解，进而总结出来两个原理的计数公式，它是一种解决问题的基本方法．