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

组合数学组合数学(第第 2 版版)-姜建国姜建国,岳建国岳建国 习题一（排列与组合）习题一（排列与组合） 1．在 1 到 9999 之间，有多少个每位上数字全不相同而且由奇数构成的整数？ 解：该题相当于从“1，3，5，7，9”五个数字中分别选出 1，2，3，4 作排列 的方案数； （1）选 1 个，即构成 1 位数，共有个； 1 5 P （2）选 2 个，即构成两位数，共有个； 2 5 P （3）选 3 个，即构成 3 位数，共有个； 3 5 P （4）选 4 个，即构成 4 位数，共有个； 4 5 P 由加法法则可知，所求的整数共有：个 1234 5555 205PPPP 2．比 5400 小并具有下列性质的正整数有多少个？ （1）每位的数字全不同； （2）每位数字不同且不出现数字 2 与 7； 解：（1）比 5400 小且每位数字全不同的正整数； 按正整数的位数可分为以下几种情况： ① 一位数，可从 1～9 中任取一个，共有 9 个； ② 两位数十位上的数可从 1～9 中选取，个位数上的数可从其余 9 个数 字中选取，根据乘法法则，共有个；9 981 ③ 三位数百位上的数可从 1～9 中选取，剩下的两位数可从其余 9 个数 中选 2 个进行排列，根据乘法法则，共有个； 2 9 9648P ④ 四位数。

又可分三种情况： 千位上的数从 1～4 中选取，剩下的三位数从剩下的 9 个数字中选 3 个进行排列，根据乘法法则，共有个； 3 9 42016P 千位上的数取 5，百位上的数从 1～3 中选取，剩下的两位数从剩 下的 8 个数字中选 2 个进行排列，共有个； 2 8 3168P 千位上的数取 5，百位上的数取 0，剩下的两位数从剩下的 8 个数 字中选 2 个进行排列，共有个； 2 8 56P  根据加法法则，满足条件的正整数共有： 个；981 6482016 168562978 （2）比 5400 小且每位数字不同且不出现数字 2 与 7 的正整数； 按正整数的位数可分为以下几种情况：设{0,1,3,4,5,6,8,9}A  ① 一位数，可从中任取一个，共有 7 个；{0}A ② 两位数十位上的数可从中选取，个位数上的数可从 A 中其余{0}A 7 个数字中选取，根据乘法法则，共有个；7 749 ③ 三位数百位上的数可从中选取，剩下的两位数可从 A 其余 7{0}A 个数中选 2 个进行排列，根据乘法法则，共有个； 2 7 7294P ④ 四位数。

又可分三种情况： 千位上的数从 1，3，4 中选取，剩下的三位数从 A 中剩下的 7 个 数字中选 3 个进行排列，根据乘法法则，共有个； 3 7 3630P 千位上的数取 5，百位上的数从 0，1，3 中选取，剩下的两位数 从 A 中剩下的 6 个数字中选 2 个进行排列，共有个； 2 6 390P 根据加法法则，满足条件的正整数共有：个；749294630901070 3．一教室有两排，每排 8 个座位，今有 14 名学生，问按下列不同的方式入座， 各有多少种做法？ （1）规定某 5 人总坐在前排，某 4 人总坐在后排，但每人具体座位不指定； （2）要求前排至少坐 5 人，后排至少坐 4 人 解：（1）因为就坐是有次序的，所有是排列问题 5 人坐前排，其坐法数为，4 人坐后排，其坐法数为，(8,5)P(8,4)P 剩下的 5 个人在其余座位的就坐方式有种，(7,5)P 根据乘法原理，就座方式总共有： （种）(8,5)(8,4)(7,5)28 449 792 000PPPAA （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) 10 461394944 000 CPPCPPCPP  典型错误典型错误： 组合数学（第二版） 第 3 页（共 97 页） 先选 6 人坐前排，再选 4 人坐后排，剩下的 4 人坐入余下的 6 个座 位。

故总的入坐方式共有：种 (14,6)8,6(8,4)8,46,4CPCPP 但这样计算无疑是有重复的，例如恰好选 6 人坐前排，其余 8 人全 坐后排，那么上式中的就有重复(8,4)8,4CP 4．一位学者要在一周内安排 50 个小时的工作时间，而且每天至少工作 5 小时， 问共有多少种安排方案？ 解：用表示第 i 天的工作时间，，则问题转化为求不定方程 i x1,2,,7i  的整数解的组数，且，于是又可以转 1234567 50xxxxxxx5 i x  化为求不定方程的整数解的组数 1234567 15yyyyyyy 该问题等价于：将 15 个没有区别的球，放入 7 个不同的盒子中，每盒球数 不限，即相异元素允许重复的组合问题 故安排方案共有： （种）( ,15)(157 1,15)54 264RCC 另解： 因为允许，所以问题转化为长度为 1 的 15 条线段中间有 14 个空，再0 i y  加上前后两个空，共 16 个空，在这 16 个空中放入 6 个“＋”号，每个空放置 的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数。

从而 不定方程的整数解共有： （组） 21 20 19 18 17 16 ( ,6)(166 1,6)54 264 6 5 4 3 2 1 RCC        即共有 54 264 种安排方案 5．若某两人拒绝相邻而坐，问 12 个人围圆周就坐有多少种方式？ 解：12 个人围圆周就坐的方式有：种，(12,12)11!CP 设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为 1 人，则 这样的就坐方式有：种；由于甲乙相邻而坐，可能是“甲乙”(11,11)10!CP 也可能是“乙甲” ；所以 则满足条件的就坐方式有：种11! 2 10!32 659 200  6．有 15 名选手，其中 5 名只能打后卫，8 名只能打前锋，2 名只能打前锋或后 卫，今欲选出 11 人组成一支球队，而且需要 7 人打前锋，4 人打后卫，试 问有多少种选法？ 解：用 A、B、C 分别代表 5 名打后卫、8 名打前锋、2 名可打前锋或后卫的集 合， 则可分为以下几种情况： （1）7 个前锋从 B 中选取，有种选法，4 个后卫从 A 中选取，有种， 7 8 C 4 5 C 根据乘法法则，这种选取方案有：种； 74 85 CCA （2）7 个前锋从 B 中选取，从 A 中选取 3 名后卫，从 C 中选 1 名后卫， 根据乘法法则，这种选取方案有：种； 731 852 CCCAA （3）7 个前锋从 B 中选取，从 A 中选取 2 名后卫，C 中 2 名当后卫， 根据乘法法则，这种选取方案有：种； 72 85 CCA （4）从 B 中选 6 个前锋，从 C 中选 1 个前锋，从 A 中选 4 个后卫， 根据乘法法则，这种选取方案有：种； 614 825 CCCAA （5）从 B 中选 6 个前锋，从 C 中选 1 个前锋，从 A 中选 3 个后卫，C 中剩 下的一个当后卫，选取方案有：种； 613 825 CCCAA （6）从 B 中选 5 个前锋，C 中 2 个当前锋，从 A 中选 4 个后卫， 选取方案有：种； 54 85 CCA 根据加法法则，总的方案数为： 747317261461354 858528582582585 1400CCCCCCCCCCCCCCCAAAAAAAAA 7．求展开式中项的系数。

8 (2)xyzw 2222 x y z w 解：令，则中项的系数为,,2 ,ax by cz dw   8 ()abcd  2222 a b c z ，即中，的系数， 8 8!7! 2 2 2 22!2!2!2!2     8 (2)xyzw 2222 () ( 2 )xyzw 因此，的系数为： 2222 x y z w 22 7! 2 ( 1)( 2)10 080AA 8．求的展开式 4 ()xyz 解：，展开式共有（项） ， 所以，4,3nt( ,4)(43 1,4)15RCC  组合数学（第二版） 第 5 页（共 97 页） 444433 22222 3322 3 44444 () 4 0 00 4 00 0 4310301 444 2 2 02 0 2211 4444 130103112121 44 013031 xyzxyzx yx z x yx zx yz xyxzxyzxy z yz                 322 444333333 222222222 4 0 2 2 444444 666121212 y zy z xyzx yx zxyxzyzy z x yx zy zx yzxyzxy z       9．求展开式中的系数。

10 12345 ()xxxxx 36 234 x x x 解：的系数为： 36 234 x x x 10 10! 840 0316 03! 1! 6!     AA 10．试证任一整数 n 可唯一表示成如下形式： 1 !,0,1,2, ii i naiai i     证明：（1）可表示性 令，显然， 1221 {(,,,,)|0,1,2,,1} mmi Maaa aai im  !Mm ，显然，{0,1,2,,! 1}Nm!Nm 定义函数，:fMN ， 12211221 (,,,,)(1)!(2)!2!1! mmmm f aaa aamamaa  AA 显然， 1221 00 (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!! 1 mm mm amamaa mmmm mmmmm      AAAA AA AA  即， 1221 0(,,,,)! 1 mm f aaa am   由于 f 是用普通乘法和普通加法所定义的，故 f 无歧义，肯定是一个函 数。

从而必有一确定的数，使得，(0! 1)KKm 1221 (,,,,) mm Kf aaa a   为了证明 N 中的任一数 n 均可表示成的形式， 1 ! i i nai   只需证明 f 是满射函数即可又因为 f 是定义在两个有限且基数相等的 函数上，因此如果能证明 f 单射，则 f 必是满射 假设 f 不是单射，则存在， 12211221 (,,,,),(,,,,) mmmm aaa abbb bM   ，且有，使得 12211221 (,,,,)(,,,,) mmmm aaa abbb b   0 KN 012211221 (,,,,)(,,,,) m。