五年级奥数春季实验班第10讲 计数综合之归纳递推映射计数二

1、第10讲 计数综合之归纳递推映射计数二模块一、图形计数中的对应法图例1在88的黑白相间染色的国际象棋棋盘中，以网格线为边的、恰包括两个白色小格与一个黑色小格的长方形共有 个。解：由条件知，在四条边上不是角的黑色方格都可以画出一个符合条件的长方形，这样的长方形有34=12个。对于中间的黑色方格，每个方格都可以画出两个符合要求的长方形，这样的长方形有362=36个，于是这样的长方形有12+36=48个。例2图中可数出的三角形的个数为 。解：这个图不像我们以前数三角形那样的规则，我们发现图形由8条线段组成， 从这8条线段中任意选出3条，都可以组成一个三角形， 于是三角形的个数是（个）。模块二、数字问

2、题中的对应法例3有 个多位数（至少两位），这个数所有数位上的数字从左到右依次递增。解：先看两位数：12、13、19；23、24、，29；34、35、39；89，这样的数有8+7+6+5+4+3+2+1=36（个）；也可以看做是9个数字中选2个的组合数，即（个）；所以三位数：有（个）；依次类推共有=29=51210=502（个）。例4请问至少出现一个数码3，并且是3的倍数的五位数共有 个。解：五位数共有999999999=90000（个）；其中3的倍数有30000个；除了数字3以外，其余的9个数码分为3组：(1、4、7)；(2、5、8)；(0、6、9)，在五位数的前四位中任意取不含3的数字有89

3、99种方式，对于前面的每一个数，这四个数字的和确定以后，一定可从以上三组数中选择一组（且只有一组），使得该数是3的倍数，所以五位数中是3的倍数且不含有3的个数是89993=17496（个）于是五位数中是3的倍数且至少含有1个3的个数是3000017496=12504（个）；模块3、阶梯型标数法的对应问题例5一个正在行走的8人队列，每人身高各不相同，按从低到高的次序排列，现在他们要变成并列的2列纵队，每列仍然是按从低到高排列，且同时要求并排的每两人中左边的人比右边的人要矮，那么，2列纵队有 种不同的排法。解：由于8人的高低都不同，我们把他们按身高编号为1、2、3、4、5、6、7、8，现在相当于要

4、把这8个数填到一个24的方格中去。要求每一行的数由小到大，同时每一列上面的数比下面的数小。我们发现像上图那样填的过程中，会出现错误，即首先要使得上面行中优先填数，这正好是“阶梯型标数”的特征。于是把原题转化为如图的阶梯型标数问题。 在这个阶梯型方格中，横格代表第一行的四个，竖格代表第二行的四个，那么此题的标数结果就是从A到B的最短路线的条数。如图的走法表示为。于是一共有14种排法。模块四、对应法求数量差例6圆周上有12个点，其中一个点涂红，还有一个点涂了蓝色，其余10个点没有涂色，以这些点为顶点的凸多边形中，其顶点包含了红点及蓝点的多边形称为双色多边形，只包含红点（蓝点）的多边形称为红色（蓝色

5、）多边形，不包含红点及蓝点的称无色多边形。试问，以这12个点为顶点的凸多边形（边数可以从三角形到12边形）中，双色多边形的个数与无色多边形的个数， 较多；多 个。解：对于任何一个双色n（n5）边形，显然去掉红、蓝顶点后，得到一个无色n2边形，不同的双色n边形去掉红蓝顶点后，得到的是不同的无色n2边形反过来，对任一无色多边形，添上红蓝顶点后，总可以得到一个双色多边形，由此可知，无色多边形（从三角形到十边形）的个数与双色多边形（从五边形到十二边形）的个数相等因此，双色多边形的个数多，多出来的数目恰是双色三角形和双色四边形的数目双色三角形有10个双色四边形有（个）。双色多边形比无色多边形多55个模块

6、五、经典映射计数难题例78个女孩和25个男孩围成一圈，任意两个女孩之间至少站两个男孩，问共有 种不同的排列方法（只要把圆旋转一下就重合的排法认为是同一种）。解：先排女孩，这是一个圆排列问题，易知共有种不同的排列。8个女孩的圆排列共留出8个空挡。再排男孩，设这8个空挡中的男孩数分别为x1、x2、x8， 于是x1+x2+x3+x8=25，由于任意两个女孩之间至少站两个男孩，即求不定方程在x12，x22，x82下的正整数解的组数，所以不定方程可化(x11)+(x21)+(x31)+(x81)=17的解，令x11=y1，x21=y2，x81=y8，于是方程转化为y1+y2+y3+y8=17的正整数解。

7、正整数解的个数是在这17个1排成的一列（共16个空）中插入7个分隔符，=11440，再对男孩全排列为，所以最后答案是种不同的排列方法。例8设abcd，且(x，y，z，t)是(a，b，c，d)的任意排列，问表达式：n=(xy)2+(yz)2+(zt)2+(tx)2可以取 3 种不同的值。解：如果只有两个数a，b，那么类似问题只有一种结果；如果有三个数a，b，c，三个数之间的差的平方只有三种结果，(ab)2，(bc)2，(ac)2，对于每一种排列，结果都一样，所以也是只有一种结果；现在是四个数(a，b，c，d)，每两个数之间的差有=6种可能，即(ab)2，(bc)2，(cd)2，(ac)2，(bd

8、)2，(ad)2，它们之间组合当选定了(ab)2之后，后面只能选(ac)2，(ad)2当中的一种，有2个选项；如果下面再选(ac)2，那么后两个必然是(bd)2和(cd)2；同样如果第二个选的是(ad)2，那么后两个必然是(bc)2和(cd)2；所以有(ab)2，则一定有(cd)2，同样如果有(bc)2，也一定有(ad)2，如果有(ac)2，也一定有(bd)2，即每次只能从这3组中选取2组，得到四个差的平方。所以可以取3种不同的值。随 堂 练 习1在1010的方格棋盘中，取出一个由四个小方格组成的“T”形（如图所示），一共有 种不同的方法。解：由图形知道对于四条边上的（不在角上）的每一个小方格

9、为中心，可以做出1个“T字形”，这样有48=32个；对于中间的每一个小方格，以它为中心可以做出4个“T字形”，可以有644=256（个）。所以一共有256+32=288个“T字形”。2在一个圆周上不均匀的分布着8个点，这些点之间所连成的线段会在圆的内部（不包括边）产生交点，那么最多可以产生 个交点。解：圆上任意四个点之间的连线能够在圆内部产生一共交点，且只有一个交点。于是8个点中任意选四个点的组合有，所以最多产生70个点。3有 个不超过10000的多位数（至少两位），这个数所有数位上的数字从左到右依次递增。解：按例3的方法，且0一定不能取，两位数中有（个），三位数有（个），四位数有，所以不超过

10、10000的符合条件的数有36+84+126=246（个）。4至少出现一个数码9，并且是9的倍数的五位数共有 个。解：五位数中从10000到99999中，是9的倍数的有10000个，不含数码9，其他9个数码组成的四位数有8999=5832（个），对于其中的任何一个数，它被9除的余数分别是0、1、2、3、8，在它的后面相应添上0、8、7、6、1，就是一个不含数码9的且能被9整除的五位数。所以五位数中不含数码9的且能被9整除的五位数有5832个，于是至少出现一个数码9，并且是9的倍数的五位数共有100005832=4168（个）。5将112这12个数填入到2行6列的方格表中，使得每行右边的数比左边

11、的数大，每一列上面的数比下面的数大，共有 种填法。解： 一共有132种填法。6有一类各位数字各不相同的五位数M，它的千位数字比左右两个数字大，十位数字也比左右两位数字大，另有一类各位数字各不相同的五位数W，它的千位数字比左右两个数字小，十位数字也比左右两位数字小，请问符合要求的数字M与W， 个数多，多 个。解：M与W都是五位数，且都是千位数字和十位数字与两边其他数字的大小关系，一般情况下给出一个符合条件的M，比如M=13264，就可以在每个数位上用9减去原来数位上的数得到86735，它是W中的数。所以M与W在大多数情况下是一一对应的，似乎应该个数是相等的。但是M类数中万位数字不能为0，而W类数

12、中没有这个限制，所以W类数比较多，多的就是首位为9的W类数，假设该数为9abcd，要求a、b、c、d是0、1、2、3、8中各不相同的四个数，有种不同的取法，设这四个数为n1n2n3n4，要求a与c比较小，可以取a=n1，c=n2或a=n2，c=n1，而b、d可以任取n3、n4，这样的数有4个，若取a=n3，c=n1，则只能是d=n2，b=n4，即9n3n4n1n2。综上所述得到每组(a、b、c、d)，组成4+1=5个W类数，这样的W类数有1265=630（个）。即W类数比M类数多630个。7整数1、2、8的排列满足：每个数或者大于它前面的所有数，或者小于它前面的所有数，那么共有 个这样的排列。

13、解：先排1和2，有2种方法；即12、21，有2种排法；然后摆3，3如果放在最后面，则123、213都可以，3如果放在第二个位置上，则有231，如果3放在最前一个位置，则有321，这样有4种排法；然后摆4，如果4放在最后面，则上面4种排法依次放上4都可以，即3214、1234、2134、2314，如果4放在第二位，则后面只能放1（如果不是1，例如是2，则2的前面有1和4，这是矛盾的），此时它的前面的2个数，有2种排法，即2341、3241；如果4放在第三位，那么它的后面只能放12，于是有3421，如果4放在第四位，只有4321这1种，得到8种排法。记所有的排列的个数为an，显然a1=1，a2=2

14、，a3=4，a4=8，对于n2，考虑最大的数n，如果n排在第i位，则它之后的ni个数排序完全确定；而它之前的i1个数有ai1个排法。考虑到所有不同的位置，由分类计数原理知：an=1+a1+a2+an1，于是an1=1+a1+a2+an2，所以an=2n1。即a8=27=128.解2：若有2个数，则有a2=2种排法，对于8个数字的问题，考虑个位数字，若个位数字为8，那么它前面的7个数字能排出a7种形式；若个位数字为1，前面的8个数字（2、3、4、9）也有a7种排法，若个位数字不是1或8，那么这种排法一定是错误的，（因为它的前面有1和8，它不可能大于前面所有的数字，也不会小于前面所有的数字）；所以a8=2a7=22a6=23a5=27a1=27=128。8在圆周上给出了一个由点A1，