《《组合数学》第二版(姜建国著)-课后习题答案全》由会员分享，可在线阅读，更多相关《《组合数学》第二版(姜建国著)-课后习题答案全（93页珍藏版）》请在金锄头文库上搜索。
1、组合数学（第二版） 第 1 页（共 93 页） 习题一（排列与组合）习题一（排列与组合） 1在 1 到 9999 之间，有多少个每位上数字全不相同而且由奇数构成的整数？ 解：该题相当于从“1，3，5，7，9”五个数字中分别选出 1，2，3，4 作排列的方案数； （1）选 1 个，即构成 1 位数，共有1 5P个； （2）选 2 个，即构成两位数，共有2 5P个； （3）选 3 个，即构成 3 位数，共有3 5P个； （4）选 4 个，即构成 4 位数，共有4 5P个； 由加法法则可知，所求的整数共有：1234 5555205PPPP个。 2比5400小并具有下列性质的正整数有多少个？ （1）每
2、位的数字全不同； （2）每位数字不同且不出现数字2与7； 解： （1）比5400小且每位数字全不同的正整数； 按正整数的位数可分为以下几种情况： 一位数，可从19中任取一个，共有9个； 两位数。十位上的数可从19中选取，个位数上的数可从其余9个数字中选取，根据乘法法则，共有9 981个； 三位数。百位上的数可从19中选取，剩下的两位数可从其余9个数中选2个进行排列，根据乘法法则，共有2 99648P个； 四位数。又可分三种情况： 千位上的数从14中选取，剩下的三位数从剩下的9个数字中选3个进行排列，根据乘法法则，共有3 942016P个； 千位上的数取5，百位上的数从13中选取，剩下的两位数从
3、剩下的8个数字中选2个进行排列，共有2 83168P个； 千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数字中选2个进行排列，共有2 856P 个； 根据加法法则， 满足条件的正整数共有：981 6482016 168562978个； （2）比5400小且每位数字不同且不出现数字2与7的正整数； 按正整数的位数可分为以下几种情况：设0,1,3,4,5,6,8,9A 一位数，可从0A中任取一个，共有7个； 组合数学（第二版） 第 2 页（共 93 页） 两位数。 十位上的数可从0A中选取， 个位数上的数可从A中其余7个数字中选取，根据乘法法则，共有7 749个； 三位数。百位上的数可从
4、0A中选取，剩下的两位数可从A其余7个数中选2个进行排列，根据乘法法则，共有2 77294P个； 四位数。又可分三种情况： 千位上的数从1，3，4中选取，剩下的三位数从A中剩下的7个数字中选3个进行排列，根据乘法法则，共有3 73630P个； 千位上的数取5，百位上的数从0，1，3中选取，剩下的两位数从A中剩下的6个数字中选2个进行排列，共有2 6390P个； 根据加法法则，满足条件的正整数共有：749294630901070个； 3一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？ （1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定； （2）
5、要求前排至少坐5人，后排至少坐4人。 解： （1）因为就坐是有次序的，所有是排列问题。 5人坐前排，其坐法数为(8,5)P，4人坐后排，其坐法数为(8,4)P， 剩下的5个人在其余座位的就坐方式有(7,5)P种， 根据乘法原理，就座方式总共有： (8,5)(8,4)(7,5)28 449792 000PPP?（种） （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、6)CPP； 各类入座方式互相不同，由加法法则，总的入座方式总数为： (14,6) (8,6) (8,8)(14,7) (8,7) (8,7)(14,8) (8,8) (8,6)10 461394944000CPPCPPCPP 典型错误典型错误： 先选 6 人坐前排，再选 4 人坐后排，剩下的 4 人坐入余下的 6 个座位。故总的入坐方式共有： (14,6)8,6(8,4)8,46,4CPCPP种。 但这样计算无疑是有重复的，例如恰好选 6 人坐前排，其余 8 人全坐后排，那么上式中的(8,4)8,4CP就有重复。 组合数学（第二版） 第 3 页（共 93 页） 4一位学者要在一周内安排50个
7、小时的工作时间，而且每天至少工作5小时， 问共有多少种安排方案？ 解：用ix 表示第i天的工作时间，1,2,7i ，则问题转化为求不定方程 123456750xxxxxxx的整数解的组数，且5ix ，于是又可以转化为求不定方程123456715yyyyyyy的整数解的组数。 该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。 故安排方案共有：( ,15)(157 1,15)54 264RCC （种） 另解： 因为允许0iy ，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“”号，每个空放
8、置的“”号数不限，未放“”号的线段合成一条线段，求放法的总数。从而不定方程的整数解共有： 21 20 19 18 17 16( ,6)(166 1,6)54 2646 5 4 3 2 1RCC （组） 即共有54 264种安排方案。 5若某两人拒绝相邻而坐，问12个人围圆周就坐有多少种方式？ 解：12个人围圆周就坐的方式有：(12,12)11!CP种， 设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为1人，则这样的就坐方式有：(11,11)10!CP种；由于甲乙相邻而坐，可能是“甲乙”也可能是“乙甲” ；所以 则满足条件的就坐方式有：11! 2 10!32659 200 种。 6有15
9、名选手，其中5名只能打后卫，8名只能打前锋，2名只能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？ 解：用A、B、C分别代表5名打后卫、8名打前锋、2名可打前锋或后卫的集合， 则可分为以下几种情况： （1）7个前锋从B中选取，有7 8C种选法，4个后卫从A中选取，有4 5C种， 根据乘法法则，这种选取方案有：74 85CC?种； （2）7个前锋从B中选取，从A中选取3名后卫，从C中选1名后卫， 根据乘法法则，这种选取方案有：731 852CCC?种； （3）7个前锋从B中选取，从A中选取2名后卫，C中2名当后卫， 根据乘法法则，这种选取方案有：72
10、 85CC?种； 组合数学（第二版） 第 4 页（共 93 页） （4）从B中选6个前锋，从C中选1个前锋，从A中选4个后卫， 根据乘法法则，这种选取方案有：614 825CCC?种； （5）从B中选6个前锋，从C中选1个前锋，从A中选3个后卫，C中剩下的一个当后卫，选取方案有：613 825CCC?种； （6）从B中选5个前锋，C中2个当前锋，从A中选4个后卫， 选取方案有：54 85CC?种； 根据加法法则，总的方案数为： 747317261461354 8585285825825851400CCCCCCCCCCCCCCC? 7求8(2)xyzw展开式中2222x y z w项的系数。 解
11、：令,2 ,ax by cz dw ，则8()abcd 中2222a b c z项的系数为 88!7! 2 2 2 22!2!2!2!2，即8(2)xyzw中，2222() ( 2 )xyzw的系数， 因此，2222x y z w的系数为：227! 2 ( 1)( 2)10080?。 8求4()xyz的展开式。 解：4,3nt，展开式共有( ,4)(43 1,4)15RCC （项） ， 所以， 444433222223322344444()4 0 00 4 00 0 4310301444 2 202 0 22114444 13010311212144 013031xyzxyzx yx zx y
12、x zx yzxyxzxyzxy zyz 3224443333332222222224 0 2 2444444666121212y zy zxyzx yx zxyxzyzy zx yx zy zx yzxyzxy z 9求10 12345()xxxxx展开式中36 234x x x的系数。 解：36 234x x x的系数为： 1010!8400316 03! 1! 6!?10试证任一整数n可唯一表示成如下形式： 1!,0,1,2,ii inaiai i 组合数学（第二版） 第 5 页（共 93 页） 证明： （1）可表示性。 令1221(,)|0,1,2,1mmiMaaa aai im，显然
13、!Mm， 0,1,2,! 1Nm，显然!Nm， 定义函数:fMN， 12211221(,)(1)!(2)!2!1!mmmmf aaa aamamaa?， 显然，122100 (1)! 0 (2)!0 2! 0 1! (1)!(2)!2!1!(1)(1)! (2)(2)!2 2! 1 1! ! (1)! (1)! (2)!3! 2! 2! 1! 1mmmm amamaammmm mmmmm ? ? 即12210(,)! 1mmf aaa am， 由于 f 是用普通乘法和普通加法所定义的， 故 f 无歧义， 肯定是一个函数。 从而必有一确定的数(0! 1)KKm，使得1221(,)mmKf aaa
14、 a， 为了证明 N 中的任一数 n 均可表示成1!i inai的形式， 只需证明f是满射函数即可。又因为f是定义在两个有限且基数相等的函数上，因此如果能证明f单射，则f必是满射。 假设f不是单射，则存在12211221(,),(,)mmmmaaa abbb bM， 12211221(,)(,)mmmmaaa abbb b，且有0KN，使得 012211221(,)(,)mmmmKf aaa af bbb b 由于12211221(,)(,)mmmmaaa abbb b，故必存在1jm，使得jjab。不妨设这个j是第一个使之不相等的，即(1,1)iiab imj，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)!2 2! 1 1!mmmmjjjjjjbmbmbbamamaabajbajbabajbajbabajjjj
