《组合数学》第二版(姜建国著)-课后习题答案全

组合数学（第二版）第1页（共93页）习一（排列与组合）1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的数；（1）选1个，即构成1位数，共有15P个；（2）选2个，即构成两位数，共有25P个；（3）选3个，即构成3位数，共有35P个；（4）选4个，即构成4位数，共有45P个；由加法法则可知，所求的整数共有：12345555205PPPP个。2．比5400小并具有下列性质的正整数有多少个？（1）每位的数字全不同；（2）每位数字不同且不出现数字2与7；解：（1）比5400小且每位数字全不同的正整数；按正整数的位数可分为以下几种情况：①一位数，可从1～9中任取一个，共有9个；②两位数。十位上的数可从1～9中选取，个位数上的数可从其余9个数字中选取，根据乘法法则，共有9981个；③三位数。百位上的数可从1～9中选取，剩下的两位数可从其余9个数中选2个进行排列，根据乘法法则，共有299648P个；④四位数。又可分三种情况：千位上的数从1～4中选取，剩下的三位数从剩下的9个数字中选3个进行排列，根据乘法法则，共有3942016P个；千位上的数取5，百位上的数从1～3中选取，剩下的两位数从剩下的8个数字中选2个进行排列，共有283168P个；千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数字中选2个进行排列，共有2856P个；根据加法法则，满足条件的正整数共有：9816482016168562978个；（2）比5400小且每位数字不同且不出现数字2与7的正整数；按正整数的位数可分为以下几种情况：设{0,1,3,4,5,6,8,9}A①一位数，可从{0}A中任取一个，共有7个；组合数学（第二版）第2页（共93页）②两位数。十位上的数可从{0}A中选取，个位数上的数可从A中其余7个数字中选取，根据乘法法则，共有7749个；③三位数。百位上的数可从{0}A中选取，剩下的两位数可从A其余7个数中选2个进行排列，根据乘法法则，共有277294P个；④四位数。又可分三种情况：千位上的数从1，3，4中选取，剩下的三位数从A中剩下的7个数字中选3个进行排列，根据乘法法则，共有373630P个；千位上的数取5，百位上的数从0，1，3中选取，剩下的两位数从A中剩下的6个数字中选2个进行排列，共有26390P个；根据加法法则，满足条件的正整数共有：749294630901070个；3．一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？（1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定；（2）要求前排至少坐5人，后排至少坐4人。解：（1）因为就坐是有次序的，所有是排列问题。5人坐前排，其坐法数为(8,5)P，4人坐后排，其坐法数为(8,4)P，剩下的5个人在其余座位的就坐方式有(7,5)P种，根据乘法原理，就座方式总共有：(8,5)(8,4)(7,5)28449792000PPP��（种）（2）因前排至少需坐6人，最多坐8人，后排也是如此。可分成三种情况分别讨论：①前排恰好坐6人，入座方式有(14,6)(8,6)(8,8)CPP；②前排恰好坐7人，入座方式有(14,7)(8,7)(8,7)CPP；③前排恰好坐8人，入座方式有(14,8)(8,8)(8,6)CPP；各类入座方式互相不同，由加法法则，总的入座方式总数为：(14,6)(8,6)(8,8)(14,7)(8,7)(8,7)(14,8)(8,8)(8,6)10461394944000CPPCPPCPP典型错误：先选6人坐前排，再选4人坐后排，剩下的4人坐入余下的6个座位。故总的入坐方式共有：(14,6)8,6(8,4)8,46,4CPCPP种。但这样计算无疑是有重复的，例如恰好选6人坐前排，其余8人全坐后排，那么上式中的(8,4)8,4CP就有重复。组合数学（第二版）第3页（共93页）4．一位学者要在一周内安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？解：用ix表示第i天的工作时间，1,2,,7i，则问题转化为求不定方程123456750xxxxxxx的整数解的组数，且5ix，于是又可以转化为求不定方程123456715yyyyyyy的整数解的组数。该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。故安排方案共有：(,15)(1571,15)54264RCC（种）另解：因为允许0iy，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋”号，每个空放置的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数。从而不定方程的整数解共有：212019181716(,6)(1661,6)54264654321RCC（组）即共有54264种安排方案。5．若某两人拒绝相邻而坐，问12个人围圆周就坐有多少种方式？解：12个人围圆周就坐的方式有：(12,12)11!CP种，设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为1人，则这样的就坐方式有：(11,11)10!CP种；由于甲乙相邻而坐，可能是“甲乙”也可能是“乙甲”；所以则满足条件的就坐方式有：11!210!32659200种。6．有15名选手，其中5名只能打后卫，8名只能打前锋，2名只能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？解：用A、B、C分别代表5名打后卫、8名打前锋、2名可打前锋或后卫的集合，则可分为以下几种情况：（1）7个前锋从B中选取，有78C种选法，4个后卫从A中选取，有45C种，根据乘法法则，这种选取方案有：7485CC�种；（2）7个前锋从B中选取，从A中选取3名后卫，从C中选1名后卫，根据乘法法则，这种选取方案有：731852CCC��种；（3）7个前锋从B中选取，从A中选取2名后卫，C中2名当后卫，根据乘法法则，这种选取方案有：7285CC�种；组合数学（第二版）第4页（共93页）（4）从B中选6个前锋，从C中选1个前锋，从A中选4个后卫，根据乘法法则，这种选取方案有：614825CCC��种；（5）从B中选6个前锋，从C中选1个前锋，从A中选3个后卫，C中剩下的一个当后卫，选取方案有：613825CCC��种；（6）从B中选5个前锋，C中2个当前锋，从A中选4个后卫，选取方案有：5485CC�种；根据加法法则，总的方案数为：7473172614613548585285825825851400CCCCCCCCCCCCCCC���������7．求8(2)xyzw展开式中2222xyzw项的系数。解：令,,2,axbyczdw，则8()abcd中2222abcz项的系数为88!7!22222!2!2!2!2，即8(2)xyzw中，2222()(2)xyzw的系数，因此，2222xyzw的系数为：227!2(1)(2)10080��。8．求4()xyz的展开式。解：4,3nt，展开式共有(,4)(431,4)15RCC（项），所以，444433222223322344444()400040004310301444220202211444413010311212144013031xyzxyzxyxzxyxzxyzxyxzxyzxyzyz3224443333332222222224022444444666121212yzyzxyzxyxzxyxzyzyzxyxzyzxyzxyzxyz9．求1012345()xxxxx展开式中36234xxx的系数。解：36234xxx的系数为：1010!840031603!1!6!��10．试证任一整数n可唯一表示成如下形式：1!,0,1,2,iiinaiaii组合数学（第二版）第5页（共93页）证明：（1）可表示性。令1221{(,,,,)|0,1,2,,1}mmiMaaaaaiim，显然!Mm，{0,1,2,,!1}Nm，显然!Nm，定义函数:fMN，12211221(,,,,)(1)!(2)!2!1!mmmmfaaaaamamaa��，显然，122100(1)!0(2)!02!01!(1)!(2)!2!1!(1)(1)!(2)(2)!22!11!!(1)!(1)!(2)!3!2!2!1!!1mmmmamamaammmmmmmmm��������即12210(,,,,)!1mmfaaaam，由于f是用普通乘法和普通加法所定义的，故f无歧义，肯定是一个函数。从而必有一确定的数(0!1)KKm，使得1221(,,,,)mmKfaaaa，为了证明N中的任一数n均可表示成1!iinai的形式，只需证明f是满射函数即可。又因为f是定义在两个有限且基数相等的函数上，因此如果能证明f单射，则f必是满射。假设f不是单射，则存在12211221(,,,,),(,,,,)mmmmaaaabbbbM，12211221(,,,,)(,,,,)mmmmaaaabbbb，且有0KN，使得012211221(,,,,)(,,,,)mmmmKfaaaafbbbb由于12211221(,,,,)(,,,,)mmmmaaaabbbb，故必存在1jm，使得jjab。不妨设这个j是第一个使之不相等的，即(1,,1)iiabimj，jjab且jjab，因为12211221(1)!(2)!2!1!(1)!(2)!2!1!mmmmamamaabmbmbb����所以，122112211122111122110(1)!(2)!2!1!(1)!(2)!2!1!()!()(1)!()2!()1!!(1)!2!1!!(1)(1)!22!11!!mmmmjjjjjjbmbmbbamamaabajbajbabajbajbabajjjj������������(!1)1j产生矛盾，所以f必是单射函数。因为!MNm，所以f必然也是满射函数，故对任意的nN，都存在1221(,,,,)mmaaaaM，使得1221(1)!(2)!2!1!mmnamamaa��组合数学（第二版）第6页（共93页）这说明对任意的整数，都可以表示成1!iinai的形式。（2）唯一性。由于函数:fMN是一个单射，也是满射，即f是双射函数，故，对任意的nN，都存在唯一的1221(,,,,)mmaaaaM，使得1221(1)!(2)!2!1!mmnamamaa��。否则，若存在另一个1221(,,,,)mmbbbbM，使得1221(1)!(2)!2!1!mmnbmbmbb��将与f是单射函数矛盾。证毕。11．证明(1,)(1)(,1)nCnrrCnr，并给出组合意义。证明：因为(,)(,)(,)(,)CnkCklCnlCnlkl，现令1kr，1l，则可得(,1)(1,1)(,1)(1,)CnrCrCnCnr，即(1,)(1)(,1)nCnrrCnr组合意义：将n个元素分为3堆，1堆1个元素，1堆r个元素，1堆1nr个元素。可以有下面两种不同的分法：（1）先从n个元素中选出1r个元素，剩下的1nr个作为1堆；再将选出的1r个元素分为两堆，1堆1个，1堆r个。（2）先从n个元素中选出1人作为1堆，再从剩下的1n个中选出r个作为1堆，剩下的1nr作为1堆。显然，两种分法是等价的，所以等式成立。12．证明11(,)2nnkkCnkn。证明：采用殊途同归法。组合意义一：考虑从n个人中选出1名正式代表和若干名列席代表的选法（列席代表人数不限，可以为0）。可以有以下两种不同的选法：（1）先选定正式代表，有1nCn种选法；然后从1n人中选列席代表，这1n个人都有选和不选的两种状态，共有12n种选法；根据乘法法则，共有12nn种选法；（2）可以先选出1(0,1,2,,1)kkn人，然后再从中选出1名正式代表，其余k人作为列席代表，对于每个k，这样的选法有：111knkCC，从而总选法有：1011(,1)(1,1)(,)(,1)(,)nnnkkkCnkCkCnkCkkCnk显然，两种选法是等价的，所以等式成立。组合数学（第二版）第7页（共93页）组合意义二：将n个不同的球放入标号为A、B、C的3个盒子，其中要求A盒只放1个球，其余两盒的球数不限。那么，有两种不同的放法：（1）先从n个不同的球中选出1个，放入A盒，再将其余1n个球放入另外两盒，有11122nnnCn�种放法；（2）先从n个球中选出k个(1,2,,)kn，再从所选的k个球中选出1个放入A盒，将其余的1k个球放入B盒，剩下的nk个球放入C盒，根据乘法法则，对于不同的k，有1knkknknknCCCkC��种放法。当1,2,,kn时，各种情况互不重复，且包含了所有放法，根据加法法则，总的放法有：1(,)nkkCnk。显然两种放法是等价的，故等式成立。另法：根据二项式定理：21(1)1(,1)(,2)(,1)(,)nnnxCnxCnxCnnxCnnx，两边求导，得：121(1)(,1)2(,2)(1)(,1)(,)nnnnxCnCnxnCnnxnCnnx，令1x，即得11(,)2nnkkCnkn13．有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组的最大数，问有多少种方案？解：设这n个不同的数为12naaa，若假定第一组取1k个数，第二组取2k个数，并且令12(2)mkkm，则要求第一组数里的最小数大于第二组里的最大数，我们可以这样来选：先从n个数中任选m个数出来，有(,)Cnm种选法；再从这m个数中从大到小取1k个数作为第一组数，11,2,,1km，有1m种取法；再将其余的2k个数作为第二组数。故总方案数有：22211(1)(,)(,)(,)2(21)(2)21nnnmmmnnnmCnmmCnmCnmnnnn14．六个引擎分列两排，要求引擎的点火次序两排交错开来，试求从某一特定引擎开始点火有多少种方案？组合数学（第二版）第8页（共93页）解：第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种,……。所以方案数为：13221112（种）如果只指定从第一排先开始点火，不指定某一个，则方案数为33221136（种）如果第一个引擎任意选，只要求点火过程是交错的，则方案数为63221172（种）15．试求从1到1000000的整数中，0出现了几次？解：分别计算0出现在各个位上的次数。（1）0出现在个位，此时符合条件的2位数有9个；3位数有910个；4位数有2910个；5位数有3910个；6位数有4910个；（2）0出现在十位，此时符合条件的3位数有910个；4位数有2910个；5位数有3910个；6位数有4910个；（3）0出现在百位，此时符合条件的4位数有2910个；5位数有3910个；6位数有4910个；（4）0出现在千位，此时符合条件的5位数有3910个；6位数有4910个；（5）0出现在万位，此时符合条件的6位数有4910个；另外1000000中有6个0。所以，从1到1000000的整数中，0出现的次数总共有：234929103910491059106488895（次）另法：先不考虑1000000本身，那么任一个000000～999999之间的数都可以表示成如下形式：123456dddddd，其中每个id是0到9的数字。因为每位数字可以有10种选择，根据乘法法则，共有610个“6位数”，又每个“6位数”由6个数字组成（包括无效0），所以共有6106个数字，又每个数字出现的概率相等，所以0出现的次数应是5106，但习惯上在计算0的个数时，不包括无效0（即高位的0），因而要从中去掉无效0，其中：（1）1位数有9个（不包括0），其无效0共有95个（即00000id）；（2）2位数有90个，其无效0共904个。依次类推，无效0的总数为59490390029000190000111105因为123456dddddd全为0时的6个0和1000000本身的6个0相互抵消，所以1到1000000之间的自然数中0出现的次数为5610111105488895（次）组合数学（第二版）第9页（共93页）注意：1出现的次数为11065（要考虑1000000这个数的首位1），2，3，…，9各自出现的次数为5106。16．n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？解：排成男女相间的队伍：先将n个男的排成1行，共有nnP种排法；再将n个女的往n个空里插，有nnP种排法；由于可以先男后女，也可以先女后男，因此共有2nnP种排法；根据乘法法则，男女相间的队伍共有：22!!nnnnPPnn�种方案。若围成一圆周坐下，同理先将n个男的围成一圆周，共有(,)CPnn种排法，再将n个女的往n个空中插，有nnP种排法，根据乘法法则，围成圆周坐下，总的方案数有：(,)!(1)!nnCPnnPnn�种。17．n个完全一样的球，放到r个有标志的盒子，nr，要求无一空盒，试证其方案数为11nr。证明：因为没有空盒，可先每盒放入一个球，再将剩余的nr球放入r个盒子中，即将nr个无区别的球，放入r个不同的盒子中，每盒的球数不受限制，因此方案数有：(1,)(1,)(1,1)CrnrnrCnnrCnr。另法：插空法。问题可看为：n个球排成1行，球与球之间形成1n个空，再在这1n个空中，插入1r个隔板，这样就可形成r个盒子，每盒球不空的方案，其方案数为(1,1)Cnr。18．设1212kknppp，12,,,kppp是k个素数，试求能整除尽数n的正整数数目。解：能整除数n的正整数即n的正约数，其个数为：12(1)(1)(1)k。19．试求n个完全一样的骰子能掷出多少种不同的方案？解：每个骰子有六个面，每个面的点数可以是1,2,,6中的一种。由于n个骰子完全一样，故这样相当于将n个完全一样的球放到6个不同的组合数学（第二版）第10页（共93页）盒子中，每盒球数不限。故方案数有)1)(2)(3)(4)(5(!51)5,5(),16(nnnnnnCnnC（种）20．凸十边形的任意三个对角线不共点，试求这凸十边形的对角线交于多少个点？又把所有的对角线分割成多少段？解：（1）从一个顶点可引出7条对角线，这7条对角线和其他顶点引出的对角线的交点情况如下：从右到左，和第一条对角线的交点有：17�个，和第二条的交点有26�，和第三条的交点有35�条，…，故和一个顶点引出的7条线相交的点为：1726354453627184�������，故和从10点引出的对角线交的点有8410840个，但每个点重复了四次（因为每个点在两条线上，而每条线又有两个端点），故凸十边形对角线交于8404210个点。也可以直接这样看：因为一个交点需要两条对角线相交，而两条对角线又需要多边形的四个点构成一四边形。反之，从n个顶点中任取四个顶点，连成一四边形，而四边形的两条对角线必须确定唯一的一个交点，故凸十边形的对角线的交点共有：410210C（个）（前提：任三个对角线不共点，否则，一个交点不能对应n边形的唯一四个顶点）（2）由（1）知，一个点引出的7条对角线中，第一条线上有7个点，故将该线段分成8段；第二条线上有12个点，故将该线段分成13段，…，故从一个点出发的7条线上的段数为：81316171613891。现有10个点。故总的段数为：9110910。但每段重复计算了2次（因为每条线有2个端点）故总的段数应为：9102455。另法：一个交点给相交的两条对角线各增加1段，所以对角线总的段数为：对角线数＋2倍交点数＝10(103)22104552（段）21．试证一整数n是另一整数的平方的充要条件是除尽n的正整数的数目为奇数。证明：必要性：整数n可表示为1212kaaaknppp，ipn，且ip为素数，1i，则除尽n的正整数个数为：12(1)(1)(1)kaaa，组合数学（第二版）第11页（共93页）若12(1)(1)(1)kaaa为偶数，则必存在i为奇数，则n不可能写成令一个数的平方。所以n是另一整数的平方的必要条件是除尽n的正整数数目为奇数。充分性：若除尽n的正整数的数目为奇数，则(1,2,,)iik均为偶数，则1212122222222222121212kkkaaaaaaaaakkknppppppppp���可写成另一整数的平方。证毕。22．统计力学需要计算r个质点放到n个盒子里去，并分别服从下列假定之一，问有多少种不同的图像？假设盒子始终是不同的。（1）Maxwell-Boltzmann假定：r个质点是不同的，任何盒子可以放任意个；（2）Bose-Einstein假定：r个质点完全相同，每一个盒子可以放任意个。（3）Fermi-Dirac假定：r个质点都完全相同，每盒不得超过一个。解：（1）问题即：将r个不同的质点放到n个不同的盒子，每个盒子放的质点数不受限制，即相异元素允许重复排列，其方案数有：(,)rRPrn（2）问题即：将r个没有区别的质点放到n个不同的盒子，每个盒子方的质点数不受限制，即相异元素允许重复组合，其方案数有：(1)!(,)(1,)!(1)!nrRCrCnrrrn（3）问题即：将r个没有区别的质点放到n个不同的盒子，每盒不超过一个，即相异元素不允许重复的组合，其方案数有：!(,)!()!nCnrrnr23．从26个英文字母中取出6个字母组成一字，若其中有2或3个母音，问分别可构成多少个字（不允许重复）？解：母音指元音，即a，e，i，o，u（1）有2个元音。先从5个元音中取出2个，再从剩下的21个字母中选出4个，再将6个字母进行全排列，则可构成的字总共有：246521643092000CCP（个）（2）有3个元音。先从5个元音中取出3个，再从剩下的21个字母中选出4个，再将6个字母进行全排列，则可构成的字总共有：组合数学（第二版）第12页（共93页）33652169567000CCP（个）24．给出11221011220nrnrnrnmrmnrmmmmm的组合意义。证明：组合意义一：从(1)nr个元素{1,2,,1}nr中取出(1)nrm个元素的组合数为：(1,1)(1,)CnrnrmCnrm，且1211rrnrmiiiii，其中第1r位置上的元素1ri可取1,2,,1rrrm，当1ri取(1)rk时（0,1,,km），前边的r个数12,,,riii可在{1,2,,1(1)}rk这rk个数中取，故有kkrrkr种取法；后边的[(1)(1)]nrmrnm个数231,,,rrnrmiii可在{11,,1}rknr这[(1)(1)]nrrknk个数中取，故有kmknmnkn种取法。根据乘法法则，当11rirk时，这样的组合数为：kkrkmknkkrkmkn1再根据加法法则，对0,1,,km进行求和，就有mrnmmrmnrmnrmnrmn10222211110。组合意义二：（格路方法）等式左端：从点(1,0)Ar到点(1,)Ck（0,1,,km），直接经过点(0,)Dk再到点(,)Bnmm的路径数。从A到C的路径数为：1(1)00rkrkkk，从D到B的路径数为：0nmmknkmkmk，组合数学（第二版）第13页（共93页）根据乘法法则和加法法则，从A到B的路径数有：0mkrknkkmk。等式右端：从点(1,0)Ar到点(,)Bnmm的路径数为：(1)010nmrmnrmm25．给出1211rrrnnrrrrr的组合意义。证明：（1）等式右端：从1n个元素121,,,,nnaaaa中，任选1r个元素的组合方案数为：11nr。（2）等式左端：从1n不同元素121,,,,nnaaaa中选取1r个元素，一定选元素1(0,1,2,,)rkaknr，但不选元素21,,,rknnaaa的方案数。根据乘法法则，当k值取定时，这样的方案数为从其余的rk个元素中任取r个的方案数，即rkr，再根据加法法则，总的方案数有：0nrkrkr26．证明120110nmmmmmmnmnnnn。证明：考虑从m双互不相同的鞋中取出n只，nm，要求其中没有任何两只是成对的，求方案数。一方面，先从m双鞋中选取n双，共有mn种选法，再从此n双中每双抽掉一只，有2n种取法，由乘法原理，总的方案数为：2nmn。另一方面，先取出(0,1,,)kkn只左脚的鞋，再在其余的mk双中取出nk只右脚的鞋，则总的方案数为：10110mmmmmmnnnn组合数学（第二版）第14页（共93页）所以，120110nmmmmmmnmnnnn。另法：根据rnnmrnrmrm（nr）（0,1,2,,rn）从而有：1011001012nmmmmmmnnnnmnmnmnnnnnmnnnnnmn27．对于给定的正整数n，证明在所有(,)(1,2,,)Cnrrn中，当11,,222nnnknn为奇数，为偶数时，(,)Cnr取得最大值。证明：取(,)Cnk与(,1)Cnk进行比较。(,)1(,1)CnknkCnkk，当2nk时，11nkk，即(,)(,1)CnkCnk，当2nk时，11nkk，即(,)(,1)CnkCnk，因此，只有当2nk或最接近2n时，(,)Cnk取得最大值。28．（1）用组合方法证明(2)!2nn和(3)!23nnn�都是整数。（2）证明21()!(!)nnn是整数。证明：（1）考虑2n个有区别的球放入n个不同的盒子里，每盒两个，盒中球不组合数学（第二版）第15页（共93页）计顺序，则方案数为：(2)!(2)!2!2!2!2nnnn��个，方案数是整数，所以(2)!2nn是整数。同理，考虑3n个有区别的球放入n个不同的盒子里，每盒3个，盒中球不计顺，则方案数为：(3)!(3)!3!3!3!23nnnnn���个，方案数是整数，所以(3)!23nnn�是整数。（2）考虑2n个不同的球放入n个相同的盒子，每盒n个，盒中球不计顺序的方案。先假设盒子是不同的，则这样的方案数为：2(2)!()!!!!(!)nnnnnnnn��个，又盒子是相同的，所以方案数应为：221()!()!(!)(!)(!)nnnnnnn�，方案数必然是整数，所以21()!(!)nnn是整数。29．（1）在2n个球中，有n个相同，求从这2n个球中选取n个的方案数。（2）在31n个球中，有n个相同，求从这31n个球中选取n个的方案数。解：（1）问题即：从集合121{,,,,}nnSneeee�中，选取n个的方案数，即多项式2(1)(1)nnxxxx中nx的系数，即101112nnnnnnCCC从这2n个球中选取n个的方案数为2n种。（2）问题即：从集合1222122{,,,,,}nnnSneeeee�中，选取n个的方案数，即多项式221(1)(1)nnxxxx中nx的系数，即1021212121210111224nnninnnnnniCCCC30．证明在由字母表{0,1,2}生成的长度为n的字符串中，组合数学（第二版）第16页（共93页）（1）0出现偶数次的字符串有312n个；（2）231222022nnnnqnnnq，其中22nq。证明：（1）采用数学归纳法当1n时，0出现偶数次（0次），长度为1的字符串为“1”和“2”两个字符串，而13122，故结论成立。假设当(1)nkk时，结论成立，即0出现偶数次，长度为k的字符串有312k个，当1nk时，0出现偶数次，长度为1k的字符串包括两部分：①在0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，这样的字符串有312312kk个。②给0出现奇数次，长度为k的字符串后面再增加一个0，因此，这样的字符串有：3131322kkk。根据加法法则，0出现偶数次，长度为1k的字符串共有：31313122kk+1k，即1nk时，结论也成立。所以，根据数学归纳法，结论成立。（2）由（1）知，右端表示0出现偶数次的字符串数。而左端代表的组合问题是：长度为n的字符串中，有0个0的字符串数有：20nn，有2个0的字符串数有：222nn，…，有q个0的字符串数有：2nqnq，组合数学（第二版）第17页（共93页）根据加法法则，可知，左端代表的是长度为n的字符串中0出现偶数次的字符串数，因此231222022nnnnqnnnq31．5台教学仪器供m个学生使用，要求使用第1台和第2台的人数相等，有多少种分配方案？解：方法一：先从m个学生中选取k个使用第1台机器，再从剩下的mk个学生中选取k个使用第2台机器，其余2mk个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为23mkmmkkk�，这里0,1,2,()2mkqq，于是，按加法原理，共有203qmkkmmkkk�种使用方案。方法二：先从m个学生种选出2k个，再将选出2k个学生平均分到1、2台机器上，其余的2mk个学生可以任意使用剩下的3台机器，按乘法法则，其组合数为2232mkmkkk�，这里0,1,2,()2mkqq于是，按加法原理，共有20232qmkkmkkk�种使用方案。32．由n个0及n个1组成的字符串，其任意前k个字符中，0的个数不少于1的个数的字符串有多少？解：（参见P21，例1.8.8）转化为格路问题。即从点(0,0)到(,)nn，只能从对角线上方走，但可以碰到对角线的所有最短路径数。显然，第一步必然要走到点(0,1)，因此可以转换为从点(0,1)到(,)nn的所有满足条件的路径数，进一步，可以转换为从(0,1)点到(,1)nn，只能从对角线上方走，但不可以碰到对角线的所有路径数，因为从(0,1)点到(,1)nn的所有经过对角线的路径数与从(1,0)点到(,1)nn点的所有路径数是一一对应的，因此，所求的字符串有：组合数学（第二版）第18页（共93页）0(1)11(1)0(2,)(2,1)1nnnnCnnCnnnn（个）方法二：由n个1和n个0组成的2n位二进制数共有2(2)!(!)nn个(2n个不尽相异元素的全排列)，设所求的二进制数共有nb个，不符合要求的数有nr个。而不合要求的数的特征是从左向右扫描时，必然在某一位首次出现0的个数小于1的个数，即从左向右累计到第2k＋1位时出现k个0和1k个1。此时，后2()1nk位上有1nk个1，nk个0。将后部分的0改写为1，1改写为0。结果整个数变成由1n个和1n个0组成的2n位数z。即一个不合要求的数唯一对应于这样的一个数z。反之，给定一个由1n个1和1n个0组成的2n位数z．由于1比0多2个，故一定在某一位首次出现0的累计数少于1的累计数。依同法将此位后的0与1互换，使z变成由n个1和n个0组成的2n位数。所以，这两种二进制数一一对应。即!1!1!2nnnrn故2222!2!2!2!112,1!1!11!!!nnnnnnbrCnnnnnnnnn。习题二（母函数及其应用）1．求下列数列的母函数(0,1,2,)n（1）(1)nan；（2）{5}n；（3）{(1)}nn；（4）{(2)}nn；解：（1）母函数为：00()(1)()(1)nnnannaaGxxxxnn；（2）母函数为：22000554()(5)5(1)1(1)nnnnnnxxGxnxnxxxxx；方法二：组合数学（第二版）第19页（共93页）0001022()(5)14414111114541(1)1nnnnnnnnGxnxnxxxxxxxxxx（3）母函数为：2323000222()(1)(1)2(1)(1)(1)nnnnnnxxxGxnnxnnxnxxxx；方法二：2202222002222023()(1)00121121nnnnnnnnnnGxnnxxnnxxnnxxxxxxxxxx（4）母函数为：232300023()(2)(1)(1)(1)(1)nnnnnnxxxxGxnnxnnxnxxxx。方法二：00002121000023223()(2)1211111121111111131nnnnnnnnnnnnnnnnGxnnxnnxnxxxxxxxxxxxxxxxxxxx2．证明序列(,),(1,),(2,),CnnCnnCnn的母函数为11(1)nx。证明：因为(,)(1,)(1,1)CnknCnknCnkn组合数学（第二版）第20页（共93页）令230()(,)(,)(1,)(2,)(3,)knkGxCnknxCnnCnnxCnnxCnnx，则23()(,)(1,)(2,)nxGxCnnxCnnxCnnx�，231()(1,1)(,1)(1,1)(2,1)nGxCnnCnnxCnnxCnnx而1(1)()()0nnxGxGx故1202111111nnnnGxGxGxGxxxx又23023()(0,0)(1,0)(2,0)(3,0)111GxCCxCxCxxxxx所以111nnxxG方法二：已知12nSeee，，，的k-组合数为(1,)Cnkk，其母函数为：23011()(1)(1)nknknkAxxxxxkx序列(,),(1,),(2,),CnnCnnCnn的母函数为230001()(,)(1,)(2,)(3,)(,)(,)(11,)1(1)kkkkkknGxCnnCnnxCnnxCnnxCnknxCnkkxCnkkxx3．设1234{,,,}Seeee����，求序列{}na的母函数。其中，na是S的满足下列条件的n组合数。（1）S的每个元素都出现奇数次；（2）S的每个元素都出现3的倍数次；（3）1e不出现，2e至多出现一次；（4）1e只出现1、3或11次，2e只出现2、4或5次；（5）S的每个元素至少出现10次。组合数学（第二版）第21页（共93页）解：（1）4352142()()1rxGxxxxxx（2）4363431()(1)1rGxxxxx（3）23221()(1)(1)(1)xGxxxxxx（4）3112452323112453567813151622()()()(1)()()2(1)(1)Gxxxxxxxxxxxxxxxxxxxxxxxxxx（5）41010114()()1xGxxxx4．投掷两个骰子，点数之和为r(212)r，其组合数是多少？解：用ix表示骰子的点数为i，（1）若两个骰子不同，则问题等价于r的特殊有序2-分拆1216,1,2irrrri故相应的母函数为23456223456789101112()()234565432Gxxxxxxxxxxxxxxxxxx则点数之和为r的方案总数就是rx的系数(212)r。（2）若两个骰子相同，则问题等价于r的特殊无序2-分拆121261rrrrr而此问题又可转化为求r的最大分项等于2，且项数不超过6的分拆数，即求方程121212120,1,6xxrxxxx的非负整数解的个数。相应的母函数为225223423456232222223456789101112()111112233323Gxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx其中点数之和为r的方案数就是rx的系数。组合数学（第二版）第22页（共93页）5．投掷4个骰子，其点数之和为12的组合数是多少？解：参考第4题。（第二版第5题）居民小区组织义务活动，号召每家出一到两个人参加。设该小区共有n个家庭，现从中选出r人，问：（1）设每个家庭都是3口之家，有多少种不同的选法？当n=50时，选法有多少种？（2）设n个家庭中两家有4口人，其余家庭都是3口人，有多少种选法？解：（1）12233()nGxCxCx（2）221221223344()nGxCxCxCxCx（第二版第6题）把n个相同的小球放入编号为1,2,3,,m的m个盒子中，使得每个盒子内的球数不小于它的编号数。已知22mmn，求不同的放球方法数(,)gnm。解：对应母函数为：(1)2323412(1)23(1)()()()()(1)(1)(1)(2)(11!2!3!(1)[(1)1][(1)]!mmmmmmmmnmmxGxxxxxxxxxxxmmmmmmxxxxmmmnmmxnmm故2(1)[(1)1](1)(1)(,)[(1)]![(1)]!mmmnmmmmnmgnmnmmnmm6．红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？解：对应的母函数为：23456783323456733234567891011121314234567()()(1)(12345678765432)(1)Gxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx组合数学（第二版）第23页（共93页）从中取9个对应的组合数为9x的系数，即1121314151617128（种）方法二：原问题等价于从集合8,8,8Sabc���中取出9个元素，且每个元素至少取一个。现在先把元素a、b、c各取一个，然后再随意选出6个，则问题转变为从集合17,7,7Sabc���中取出6个元素，且每个元素个数不限，求重复组合的方案数。又由于每个元素的个数大于6，故从1S中取6个元素与从集合1,,Sabc���中取出6个元素的组合数一样多，因此不同的取法为62361828CC（种）7．将币值为2角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？解：该题用1分、2分、5分的硬币组成20分。是可重复的无序拆分：其母函数为：224510510251025100005100()(1)(1)(1)1(1)(1)(1)111111(1)41412(1)111(1)(1)(1)44211(1)2(1)(14iiiiiiiiiiGxxxxxxxxxxxxxxxxxxixxxixxx����)则不同的兑换方法为20x的系数，即2015105011(1)2(201)11(1)2(151)141(1)2(101)11(1)2(51)11(1)2(01)129�����即有29种兑换方法。8．有1克重砝码2枚，2克重砝码3枚，5克重砝码3枚，要求这8个砝码只许放在天平的一端，能称几种重量的物品？有多少种不同的称法？解：该题属于有限重复的无序拆分问题。对应的母函数为：组合数学（第二版）第24页（共93页）224651015234567891011121314151617181920212223()(1)(1)(1)1222332223322233222Gxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx所以能称1～23克等23种重量的物品。总共的称法为母函数的各项系数之和，再减去常数项，即总共有(1)1344147G（种）不同的称法。其中，称1、3、20、22、23克重量各有1种称法；称2、4、5、8、9、10、13、14、15、18、19、21克重量各有2种称法；称6、7、11、12、16、17克重量各有3种乘法；若要枚举出各种方案，则可作母函数：224651015(,,)(1)(1)(1)Gxyzxxyyyzzz项55511222'''''''(,',''0nnnnnnnniiixxyyyzzznnni或）即为称1222555''''''nnnnnnnn克重量的一种方案。9．证明不定方程12nxxxr的正整数解组的个数为(1,1)Crn。解：该问题即，求正整数r的n有序分拆。问题可转换为：将r个无区别的球，放入n个不同的盒子中，每盒至少1个的组合问题。可以先在每个盒子中放1球，再将rn个无区别的球，放入n个不同的盒子中，每盒球数不限，则其方案数为：(()1,)(1,1)CnrnrnCrn故该不定方程的正整数解组的个数为(1,1)Crn。方法二：问题可以视为将r个相同的1放入n个盒子。由于将ix之间的值互换，对应不同的解，所以盒子不同。设共有ra个解，则ra的母函数为231111100001nnnrrrnrknknknrnrkkrrkkxGxxxxxxCxCxCxCx所以1,1raCrn10．求方程24xyz的大于1的整数解的个数。解：该题相当于将24的3有序分拆，并且要求每个分项大于1。其母函数为：组合数学（第二版）第25页（共93页）322335530121()()(1)12(1)2kkxxGxxxxxkkxxx所求的整数解的个数即为24x的系数：119(191)1902��。11．设0(,2)nnkaCnkk，0(,21