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

组合数学（第二版）第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，则可得(