搜索
第10讲计数综合之归纳递推映射计数二模块一、图形计数中的对应法图例1．在8×8的黑白相间染色的国际象棋棋盘中，以网格线为边的、恰包括两个白色小格与一个黑色小格的长方形共有个。解：由条件知，在四条边上不是角的黑色方格都可以画出一个符合条件的长方形，这样的长方形有3×4=12个。对于中间的黑色方格，每个方格都可以画出两个符合要求的长方形，这样的长方形有3×6×2=36个，于是这样的长方形有12+36=48个。例2．图中可数出的三角形的个数为。解：这个图不像我们以前数三角形那样的规则，我们发现图形由8条线段组成，从这8条线段中任意选出3条，都可以组成一个三角形，于是三角形的个数是3856C（个）。模块二、数字问题中的对应法例3．有个多位数（至少两位），这个数所有数位上的数字从左到右依次递增。解：先看两位数：12、13、……、19；23、24、……，29；34、35、……39；……；89，这样的数有8+7+6+5+4+3+2+1=36（个）；也可以看做是9个数字中选2个的组合数，即2936C（个）；所以三位数：有3984C（个）；依次类推共有23499999CCCC=290199CC=512−10=502（个）。例4．请问至少出现一个数码3，并且是3的倍数的五位数共有个。解：五位数共有99999−9999=90000（个）；其中3的倍数有30000个；除了数字3以外，其余的9个数码分为3组：(1、4、7)；(2、5、8)；(0、6、9)，在五位数的前四位中任意取不含3的数字有8×9×9×9种方式，对于前面的每一个数，这四个数字的和确定以后，一定可从以上三组数中选择一组（且只有一组），使得该数是3的倍数，所以五位数中是3的倍数且不含有3的个数是8×9×9×9×3=17496（个）．于是五位数中是3的倍数且至少含有1个3的个数是30000−17496=12504（个）；模块3、阶梯型标数法的对应问题例5．一个正在行走的8人队列，每人身高各不相同，按从低到高的次序排列，现在他们要变成并列的2列纵队，每列仍然是按从低到高排列，且同时要求并排的每两人中左边的人比右边的人要矮，那么，2列纵队有种不同的排法。解：由于8人的高低都不同，我们把他们按身高编号为1、2、3、4、5、6、7、8，现在相当于要把这8个数填到一个2×4的方格中去。要求每一行的数由小到大，同时每一列上面的数比下面的数小。我们发现像上图那样填的过程中，会出现错误，即首先要使得上面行中优先填数，这正好是“阶梯型标数”的特征。于是把原题转化为如图的阶梯型标数问题。在这个阶梯型方格中，横格代表第一行的四个，竖格代表第二行的四个，那么此题的标数结果就是从A到B的最短路线的条数。如图的走法表示为。于是一共有14种排法。模块四、对应法求数量差例6．圆周上有12个点，其中一个点涂红，还有一个点涂了蓝色，其余10个点没有涂色，以这些点为顶点的凸多边形中，其顶点包含了红点及蓝点的多边形称为双色多边形，只包含红点（蓝点）的多边形称为红色（蓝色）多边形，不包含红点及蓝点的称无色多边形。试问，以这12个点为顶点的凸多边形（边数可以从三角形到12边形）中，双色多边形的个数与无色多边形的个数，较多；多个。解：对于任何一个双色n（n≥5）边形，显然去掉红、蓝顶点后，得到一个无色n−2边形，不同的双色n边形去掉红蓝顶点后，得到的是不同的无色n−2边形．反过来，对任一无色多边形，添上红蓝顶点后，总可以得到一个双色多边形，由此可知，无色多边形（从三角形到十边形）的个数与双色多边形（从五边形到十二边形）的个数相等．因此，双色多边形的个数多，多出来的数目恰是双色三角形和双色四边形的数目．双色三角形有10个．双色四边形有21045C（个）。54321BA14149511121BA12345BA1234567887654321∴双色多边形比无色多边形多55个．模块五、经典映射计数难题例7．8个女孩和25个男孩围成一圈，任意两个女孩之间至少站两个男孩，问共有种不同的排列方法（只要把圆旋转一下就重合的排法认为是同一种）。解：先排女孩，这是一个圆排列问题，易知共有8!7!8种不同的排列。8个女孩的圆排列共留出8个空挡。再排男孩，设这8个空挡中的男孩数分别为x1、x2、……、x8，于是x1+x2+x3+……+x8=25，由于任意两个女孩之间至少站两个男孩，即求不定方程在x1≥2，x2≥2，……x8≥2下的正整数解的组数，所以不定方程可化(x1−1)+(x2−1)+(x3−1)+……+(x8−1)=17的解，令x1−1=y1，x2−1=y2，……，x8−1=y8，于是方程转化为y1+y2+y3+……+y8=17的正整数解。正整数解的个数是在这17个1排成的一列（共16个空）中插入7个分隔符，716C=11440，再对男孩全排列为252525!A，所以最后答案是7167!25!C种不同的排列方法。例8．设abcd，且(x，y，z，t)是(a，b，c，d)的任意排列，问表达式：n=(x−y)2+(y−z)2+(z−t)2+(t−x)2可以取3种不同的值。解：如果只有两个数a，b，那么类似问题只有一种结果；如果有三个数a，b，c，三个数之间的差的平方只有三种结果，(a−b)2，(b−c)2，(a−c)2，对于每一种排列，结果都一样，所以也是只有一种结果；现在是四个数(a，b，c，d)，每两个数之间的差有24C=6种可能，即(a−b)2，(b−c)2，(c−d)2，(a−c)2，(b−d)2，(a−d)2，它们之间组合当选定了(a−b)2之后，后面只能选(a−c)2，(a−d)2当中的一种，有2个选项；如果下面再选(a−c)2，那么后两个必然是(b−d)2和(c−d)2；同样如果第二个选的是(a−d)2，那么后两个必然是(b−c)2和(c−d)2；所以有(a−b)2，则一定有(c−d)2，同样如果有(b−c)2，也一定有(a−d)2，如果有(a−c)2，也一定有(b−d)2，即每次只能从这3组中选取2组，得到四个差的平方。所以可以取3种不同的值。随堂练习1．在10×10的方格棋盘中，取出一个由四个小方格组成的“T”形（如图所示），一共有种不同的方法。解：由图形知道对于四条边上的（不在角上）的每一个小方格为中心，可以做出1个“T字形”，这样有4×8=32个；对于中间的每一个小方格，以它为中心可以做出4个“T字形”，可以有64×4=256（个）。所以一共有256+32=288个“T字形”。2．在一个圆周上不均匀的分布着8个点，这些点之间所连成的线段会在圆的内部（不包括边）产生交点，那么最多可以产生个交点。解：圆上任意四个点之间的连线能够在圆内部产生一共交点，且只有一个交点。于是8个点中任意选四个点的组合有488765704321C，所以最多产生70个点。3．有个不超过10000的多位数（至少两位），这个数所有数位上的数字从左到右依次递增。解：按例3的方法，且0一定不能取，两位数中有2936C（个），三位数有3998784321C（个），四位数有4998761264321C，所以不超过10000的符合条件的数有36+84+126=246（个）。4．至少出现一个数码9，并且是9的倍数的五位数共有个。解：五位数中从10000到99999中，是9的倍数的有10000个，不含数码9，其他9个数码组成的四位数有8×9×9×9=5832（个），对于其中的任何一个数，它被9除的余数分别是0、1、2、3、……、8，在它的后面相应添上0、8、7、6、……、1，就是一个不含数码9的且能被9整除的五位数。所以五位数中不含数码9的且能被9整除的五位数有5832个，于是至少出现一个数码9，并且是9的倍数的五位数共有10000−5832=4168（个）。5．将1~12这12个数填入到2行6列的方格表中，使得每行右边的数比左边的数大，每一列上面的数比下面的数大，共有种填法。解：一共有132种填法。6．有一类各位数字各不相同的五位数M，它的千位数字比左右两个数字大，十位数字也比左右两位数字大，另有一类各位数字各不相同的五位数W，它的千位数字比左右两个数字小，十位数字也比左右两位数字小，请问符合要求的数字M与W，个数多，多个。解：M与W都是五位数，且都是千位数字和十位数字与两边其他数字的大小关系，一般情况下给出一个符合条件的M，13213242904248282014651154321AB12111591414比如M=13264，就可以在每个数位上用9减去原来数位上的数得到86735，它是W中的数。所以M与W在大多数情况下是一一对应的，似乎应该个数是相等的。但是M类数中万位数字不能为0，而W类数中没有这个限制，所以W类数比较多，多的就是首位为9的W类数，假设该数为9abcd，要求a、b、c、d是0、1、2、3、……、8中各不相同的四个数，有49126C种不同的取法，设这四个数为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类数有126×5=630（个）。即W类数比M类数多630个。7．整数1、2、……、8的排列满足：每个数或者大于它前面的所有数，或者小于它前面的所有数，那么共有个这样的排列。解：先排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，a3=4，a4=8，对于n≥2，考虑最大的数n，如果n排在第i位，则它之后的n−i个数排序完全确定；而它之前的i−1个数有ai−1个排法。考虑到所有不同的位置，由分类计数原理知：an=1+a1+a2+……+an−1，于是an−1=1+a1+a2+……+an−2，所以an=2n−1。即a8=27=128.解2：若有2个数，则有a2=2种排法，对于8个数字的问题，考虑个位数字，若个位数字为8，那么它前面的7个数字能排出a7种形式；若个位数字为1，前面的8个数字（2、3、4、……、9）也有a7种排法，若个位数字不是1或8，那么这种排法一定是错误的，（因为它的前面有1和8，它不可能大于前面所有的数字，也不会小于前面所有的数字）；所以a8=2×a7=22×a6=23×a5=……=27×a1=27=128。8．在圆周上给出了一个由点A1，A2，……，An所组成的点集，考察所有以该点集中的点作为顶点的各种不同的凸多边形，并把这些多边形分为两组：第1组中的多边形都以A1为一个顶点，第2组的多边形则都不以A1作为顶点，那么第组中的多边形个数更多。解：第一组中的多边形个数更多一些，对于第二组中的每一个多边形，在填上A1点，就可以得到一个第一组中的多边形，第二组中不同的多边形都对应一个不同的第一组中的多边形；而第一组中的多边形A1A2A3，就不是第二组中的多边形，所以第一组中的多边形更多。