(六) 计数与综合.doc

专题：计数综合主讲教师：齐明鑫计数问题 计数问题是竞赛中的一大类问题，是小学数学竞赛的重点和难点。本讲主要讲授几种典型的计数问题，主要用到的知识点如下：1、分类计数和分步计数原理。这是两种非常常见的计数原理，而且在枚举法和排列组合中有着极为重要的应用。2、排列、组合的基本原理，及其它们的综合应用。3、递推法及其应用。例1在所有的三位自然数中，组成数字的三个数码既有大于5的数码，又有小于5的数码的自然数共有多少个？ 解答：三个数码都不大于5的三位数有 566=180个，三个数码都不小于5的三位数有 555=125个，其中，中都包括了三位数 555所求自然数共有 900-（180+125-1）= 596个所求自然数共有 596个评注：从反面考虑，排除不合要求的情况。例2甲、乙、丙、丁4位优秀学生坐在一张方桌的4边，等待老师向他们发奖奖品共有5种，每种奖品都有多份如果只给每人发一种奖品中的一份，而且要求坐在邻位上的两人所得的奖品不同，问共有多少种不同的发奖方法？发给甲的奖品可以是5种奖品中的任一种，因而有5种不同取法。甲的奖品每选定一种，乙和丁只能从剩下的4种奖品中各任选一种。解答：先让甲、乙、丙、丁在方桌4边坐定，不妨设四人的座位如图所示。由于乙、丁的奖品对丙取何种奖品会有影响，因此需分乙、丁奖品相同或不同两种情况加以讨论。（1）如果乙、丁所得的奖品相同，则乙只能从除甲有的奖品外剩下的4种奖品中任选一种，有4种选法。当乙选定后，丁也就相应地选定了奖品。丙与乙和丁都邻座，因此不能选与他们相同的奖品，但可与甲的奖品相同。因此丙可以从乙、丁所有的那种奖品以外的4种奖品中任选一种。从而知在这种情况下共有544=80（种）发奖方法。（2）如果乙、丁所得奖品不同，则乙的奖品有4种不同的选法（除去甲已选的一种），而丁的奖品只能从甲、乙已选定后剩下的3种奖品中去选，有3种选法，这时丙可选乙、丁选后剩下的3种奖品之一，也有3种选法。所以在这种情况下共有54332=180（种）发奖方法。合起来，全部不同的发奖方法共有80+180=260（种）。例3将图中的分别涂成红色、黄色或绿色，要求有线段相连的两个相邻涂不同的颜色。共有多少种不同涂法？分析：如下图，当A、B、C、D的颜色确定后，大正方形四个角上的的颜色就确定了，所以只需求A、B、C、D有多少种不同涂法。按先A，再B、C，后D的顺序涂色。解答：按ABCD的顺序涂颜色。A有3种颜色可选；当B、C取相同的颜色时，有2种颜色可选，此时D也有2种颜色可选，不同的涂法有322=12（种）；当B，C取不同的颜色时，B有2种颜色可选，C剩仅1种颜色可选，此时D也只有1种颜色可选（与A相同）。不同的涂法有 3211=6（种）。所以共有12+6=18种不同的涂法。评注：此题的巧妙之处在于并不需要拿出所有的来进行分步，当某些特定的确定后，剩下的随之确定。故减小了分步的次数，降低了复杂度。例4学校合唱团要从五年级6个班中补充8名同学，每个班至少1名，共有多少种不同的抽调方法？分析：每班至少有一个名额，那么我们只需考虑剩下的2个名额如何分配就行了。这2人都从一个班抽，有C61种方法；分别从两个班中抽，有C62种方法。解答：还剩8-6=2个名额需要分配抽调方法共有：C62+ C61=15+6=21（种）共有21种不同的抽调方法。评注：本题是一个枚举法的应用例子，每一种类型的列举都是一个组合，最后将它们加在一起。例5有9张同样大小的圆形纸片，其中标有数码“1”的有1张；标有数码“2”的有2张；标有数码“3”的有3张；标有数码“4”的也有3张。把这9张圆形纸片如下图所示放置在一起，但标有相同数码的纸片不许靠在一起，问：（1）如果M位上放置标有数码“3”的纸片，一共有_种不同的放置方法。（2）如果M位上放置标有数码“2”的纸片，一共有_种不同的放置方法。对于每一种情况，标有数码“1”的纸片均有A、B、C三个位置可以放置，所以总共有32=6（种）不同的放置方法。解答：（1）由于M位上放置标有数码“3”的纸片，为了使标有相同数码的纸片不靠在一起，另外两个标有数码“3”的纸片必须放置在右下角和左下角；标有数码“4”的纸片必须放置在与M相邻的六个位置上，并且相间放置，这样有两种可能（如图）。（2）由于M位上放置标有数码“2”的纸片，另一个标有数码“2”的纸片只能放置在左下角或右下角（如图）对于每一种可能性，标有数码“1”、“3”、“4”的纸片放置在A、B、C三个位置，只有六种方法（如图）。当A、B、C放置好后，其他地方的放法也就随之确定了。所以总共有6+6=12（种）不同的放置方法。例6 152个球，放入若干个同样的箱子中，一个箱子最少放10个，最多放20个，且各个箱子的球数各不相同，问有多少种放法？（不计箱子的排列，即两种方法，经过箱子的重新排列后，是一样的，就算一种放法）解答：设箱子的个数为m，因为每只箱子的球数均不相同，最少放10个，最多放20个，所以m20-10+1=11如果m=11，那么球的总数1011+(0+1+2+10)=110+55=165152所以m10。如果m10，那么球的总数109+(10+9+8+2)=94+54=144152 所以m10这样得到m=10。当m=10时，有球的总数=1010+(10+9+8+2+1)=152=165-13所以，只有唯一一种排法：10, 11, 12, 14, 15, 16, 17, 18, 19, 20。例7将下图所示的图形（中心的小方格挖去，共有22个小方格）延格线剪成形状、大小完全相同的两块。凡经旋转或翻转可以重合的剪法视为同一种，那么不同的剪法有多少种？解答：事实上剪法是要关于图形中心对称的，从而不妨假设最开始落剪是在中心阴影小方格的左上角和右下角，两处同时剪，并且一直保持中心对称关系，容易看出恰好有9种方案。例8 一只蜘蛛有8条腿，每条腿上有一只袜子和一只鞋子。先穿袜子，后穿鞋子，蜘蛛有多少种不同的穿袜以及穿鞋的方式？假设袜子和鞋都是一模一样的。解答：我们用数字1，2，8代表蜘蛛的8条腿，将蜘蛛穿鞋袜的顺序用一个数列表示，比如1213344556677882，就是说第一步是给编号1的腿操作，第二步是编号2的腿，第三步又是编号1的腿，如此等等。注意每条腿都操作了两次，即穿袜子和穿鞋，并且在该数列中同一个数字先出现的必然是穿袜子，后出现的必然是穿鞋。因此每一种穿戴方案对应这样一个数列。这种数列共有16！/256个。（两个1的位置共有1615/2种取法；接下来，两个2的位置共有1413/2种取法，等等。）AB作业题1：如下图，从A到B，要求每一步都是向右、向上或向斜上方，共有多少种不同的走法？不同的走法共有22种。AB226211114616解答：如下图，每个顶点上所标的数字是从A走到该顶点的走法数，它等于下方、左下方及左侧相邻顶点的走法数之和。评注：这种图形，每一个点可能有三种到达方法，但并不影响标号法的适用。CBA作业题2：在下图的街道示意图中，C处因施工不能通行，从A到B的最短路线有多少条？分析：因为B在A的右上方，由标号法可知，从A到B的最短路径上，到达任何一点的走法数都等于到它左侧点的走法数与到它下侧点的走法数之和。而C是一个