《最新组合数学第三版+卢开澄+习题答案》由会员分享，可在线阅读，更多相关《最新组合数学第三版+卢开澄+习题答案（114页珍藏版）》请在金锄头文库上搜索。
1、第 1 章 排列与组合 经过勘误和调整，已经消除了全部的文字错误，不过仍有以下几个题目暂时没有找到解 答： 1.8 1.9 1.16 1.41 （答案略） 1.42 （答案略） 1.1 从1,2, ,50 中找一双数 a,b ，使其满足： ( )5; ( )5. a ab b ab 解 (a) 5ba 将上式分解，得到 5 5 ab ab a = b 5， a=0 时， b5，6， 7，,50 。满足 a=b-5 的点共 50-4=46 个点 . a = b+5 ， a=5 时， b0，1， 2，,45。满足 a=b+5 的点共 45-0+1=46个点 . 所以，共计 92462 个点 . (
2、b) 5ba (610)511 (454)1651141531个点 。 1.2 5 个女生， 7 个男生进行排列， (a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？ (c) 两男生 A 和 B 之间正好有3 个女生的排列是多少？ 解 (a) 女生在一起当作一个人，先排列，然后将女生重新排列。 （71）!5!=8! 5! 40320 120=4838400 (b) 先将男生排列有7!种方案，共有8 个空隙，将5 个女生插入，故需从8 个空 中选 5 个空隙，有 5 8 C种选择。将女生插入，有5!种方案。故按乘法原理，有： 7! 5 8 C5!=3386880
3、0(种)方案。 (c) 先从 5 个女生中选3 个女生放入A，B 之间，有 3 5 C种方案，在让3 个女生 排列，有 3!种排列，将这5 个人看作一个人，再与其余7 个人一块排列，有 (7+1)! = 8! 由于 A，B 可交换，如图 *A*B* 或 *B*A* 故按乘法原理，有： 2 3 5 C3!8!=4838400 （种） 1.3 m 个男生， n 个女生，排成一行，其中m， n 都是正整数，若 (a) 男生不相邻 (mn+1) ； (b) n 个女生形成一个整体； (c) 男生 A 和女生 B 排在一起； 分别讨论有多少种方案. 解 (a) 先将 n 个女生排列，有n!种方法，共有n
4、+1 个空隙，选出m 个空隙，共有 m nC1 种 方法，再插入男生，有m!种方法，按乘法原理，有： n! m n C 1m! n! )!1( ! )!1( mnm n m!= )!1( )!1(! mn nn 种方案。 (b) n 个女生形成一个整体，看作一个人，与m 个男生做重排列，然后，n 个女生部再 作排列，按乘法原理，有(m+1)! n!种方案。 (c) 男生 A 和女生 B 排在一起， 看作一人， 和其余 n-1+m-1=n+m-2个人一起， 作排列， 共有 (n+m-2+1)=(n+m-1)!种方法， A，B 两人部交换，故有2(n+m-1)! 种方案。 1.4 26 个英文字母
5、进行排列，要求x 和 y 之间有 5 个字母的排列数. 解 选入 26224 个字母中选取5 个字母，有 5 24 C 种方法， 5 个字母部排列，有5!种方 案，再将X*Y 这 7 个字母看作一个，与其余19 个合起来作排列，共有(19+1)!=20! 种方 案，又因为X 与 Y 可交换，故按乘法原理，有： 2 5 24 C 5!20!=2 !19! 5 !24 5!20!=40 24! 40 242 24 24 e 又因为： ln40+0.5(lg+lg48)+24(lg24 lge) 1.602059991+0.5(0.497149872+1.681241237)+24(1.380211
6、242-0.434294481) =25.39325777 所以，结果为 25 10e 2.473191664 25 10 1.5 求 3000 到 8000 之间的奇整数的数目，而且没有相同的数字. 解 30008000中各位不同的奇数，分类讨论： 首位 3，18 74（末位不能取3） 首位 4，18 75（末位全取） 首位 5，18 74 首位 6，18 75 首位 7，18 74 从而，由加法原理，得： 87（ 454 54）=56 221232 个。 1.6 计算 1 1! 2 2! 3 3!nnL 解1)!1(! 33!22! 11nnn(参见 p14) ) !1!( 1 1 n k
7、 kkn 1.7 试证 (1)(2)(2 )nnnL 被 2n 除尽 . 证 ! !)!12( !)!2( ! )!2( )2()2)(1( n nn n n nnn!)!12(2 ! !)!12(!2 n n nn n n 故能被 n 2整除。 1.8 求 1040和 2030的公因数 . 解 1.9 试证 n 2 的正除数的数目是奇数. 解 1.10 证明任一正整数n 可惟一地表示成如下形式： 1 !,(0,1) ii i na iai i 证.(1)可表示性： 令 M=( am-1,am-2, ,a2,a1):0 aii，i=1,2,m-1 ，显然 M =m! ； N=0,1,2,m!-
8、1 ，显然 N =m!，其中 m 是大于 n 的任意整数。 定义函数 f : MN f(am-1,am-2,a2,a1)=am-1(m-1)!+ am-2(m-1)!+a22!+a11! (*) 显然， 0= 0(m-1)!+0(m-1)!+0 2!+0 1! am-1(m-1)!+ am-2(m-1)!+a22!+a11! (m-1)(m-1)!+(m-2)(m-1)!+2 2!+1 1! = m!-1 （见 P14） 即 0 f(am-1,am-2,a2,a1) m!-1 由于f 是用普通乘法和普通加法所定义的，故从而f 无歧义。从而有一确定的数K （0 K m!-1 ） ，使 K=f(a
9、m-1,am-2,a2,a1) 为证 N 中的任一数均可表示成上边(*)的形式， 只要证明 f 是满射函数即可。 但由于在两 相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f 是单射 函数即可。 否则，设存在某数K0N, 有(am-1,am-2,a2,a1) (bm-1,bm-2,b2,b1)均属于 M，使 K0=f(am-1,am-2,a2,a1)且 K0=f(bm-1,bm-2,b2,b1) 由于不相等 ,故必有某个j( m-1) ，使ajbj。不妨设这个j 是第一个不使相等的，即 ai=bi)1, 1(jmi， aj bj 且 aj bj，从而由 am-1(m-
10、1)!+ am-2(m-1)!+a22!+a11!= bm-1(m-1)!+ bm-2(m-1)!+b22!+b11! 就可有 (bj- aj)j!+(bj-1- aj-1)(j-1)!+(b2-a2)2!+(b2-a1)1!=0 但是 (bj- aj)j!+(bj-1- aj-1)(j-1)!+(b2-a2)2!+(b2-a1)1! (bj- aj)j!-bj-1- aj-1(j-1)!+ b2-a22!+ b2-a11! j!-(j-1)(j-1)!+2 2!+1 1! =j!-(j!-1) =1 矛盾，这说明f 是单射函数。 由于 M = N =m! 有限， 故 f 是双射函数， 当然是
11、满射函数，从而 0 到 m!-1 中的任何一个 数都可以表示成上边(*)的形式。故，由nN，都有 (am-1,am-2,a2,a1)M，使得 n=am-1(m-1)!+ am-2(m-1)!+a22!+a11! 这就证明了任何n 可表示成以上形式。 (2)唯一性： 用证明单射的方法，就可以证明表示法的唯一性(表示方法见P14)，留给读者。 1.11 证明 (1, )(1) ( ,1)nC nrrC n r ，并给予组合解释. 证.(参见P28 (1-8-4) )1,() 1() 1( )!1()!1( ! )!1( ! )!1( ), 1(rnCrr rnr n rnr n nrnnC 组合意
12、义：（等式右边）由n 个元素中取出r+1 个元素组合（有C(n,r+1) 种） ，再从每个 组合中取出1 个（有r+1 种） ，全部结果为C(n,r+1)(r+1) 。 （等式左边）由此所得的全部结 果相当于从n 个元素中直接取1 个元素（有n 种） ，但有重复，其重复数等于剩下的n-1 个 元素中取r 个元素的组合C(n-1,r) ，故 nC(n-1,r)= (r+1) C(n,r+1) 。 1.12 试证等式： 1 1 ( , )2 n n k kC n kn 证.证法一：根据二项式定理，(参见 P29 (1-8-5) (1+x)n=1+C(n,1)x+C(n,2)x2+ xn 两边对x求
13、导，有 n(1+x)n-1=C(n,1)+2 C(n,2)x+ nxn-1 令 x=1，即得 1 1 2),( n n k nknkC。 证法二： 组合意义：设有n 个不同的小球，并有A、B 两个合子， A 合中恰好放入一个球，B 合 中可放入任意多个球。有两种放球方法： (1)（等式左边）先从n 个球中选取k 个，再从这k 个球中任选一个放入A 合，剩下的 k-1 个球全部放入B 合中，方案数共为 n k knkC 1 ),(； (2)（等式右边）先从n 个球中任选一个放入A 合，剩下的n-1 个球每个都有两种可能， 要么放入B 合，要么不放，方案数共为n2 n-1； 显然，两种放球方法等效
14、，两种放球方案数相等，即 1 1 2),( n n k nknkC。 1.13 有 n 个不同的整数，从中取出两组来，要求第1 组的最小数大于另一个组的最大数. 解 设这 n 个不同的数为 nmmmm321 。 若假定第一组取k1个数，第二组取k2个数，并且令m=k1+k2(m 2)，则要求第一组数 里的最小数大于第二组的最大数，我们只要先从上边那n 个数中任选m 个数 (有 C(n,m) 种选 法)，再从这m 个数中从大到小取k1个数作为第一组数(有 k1=1,2,m-1 共 m-1 种取法 )， 将其余 k2个数作为第二组数，即可。故总方案数为 12)2(),()1( 1 2 n n m
15、nmnCm（参见第3 题等式）。 1.14 6 个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少 种方案？ 解 第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有 三种选择；第三次有2 种,。 即方案数为1 3 2 2 1 1=12 。 1.15 试求从 1 到 1 000 000 的整数中， 0 出现的次数 . 解 (参见 P8)从 1 到 1 000 000 的整数中，0 出现的次数相当于10-99 ， 100-999 ， 1000-9999 , 10000-99999 , 100000-999999,以及 1 000 000中的 0 的
16、个数。 10-99 中的零的个数为：9 100-999 中的零的个数为：180818118999992 个位为零十位为零 两个零 取法，有 的每一种 故对百位 位为零， 十位、个 1000-9999中的零的个数为： 有一位为零有两位为零 有三位为零 99999293 1 3 2 3 CC =27+486+2 187 =2 700 10000-99999中的零的个数为： 有一位零有二位零有三位零 有四位零 9999999299394 1 4 2 4 3 4 CCC =36+972+8 748+26 244 =36 000 100000-99999中的零的个数为： 有一位零有二位零有三位零有四位零 有五位零 9999999992999399
