《组合数学第三版卢开澄习题答案》由会员分享，可在线阅读，更多相关《组合数学第三版卢开澄习题答案（115页珍藏版）》请在金锄头文库上搜索。
1、第一章：排列与组合第1章 排列与组合经过勘误和调整，已经消除了全部的文字错误，不过仍有以下几个题目暂时没有找到解答：1.81.91.16 1.41（答案略）1.42（答案略）1.1 从1,2,50中找一双数a,b，使其满足：解 (a) 将上式分解，得到a = b5，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个点.所以，共计个点.(b) 。1.2 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A和B之间正
2、好有3个女生的排列是多少？解 (a) 女生在一起当作一个人，先排列，然后将女生重新排列。（71）!5!=8!5!40320120=4838400(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有种选择。将女生插入，有5!种方案。故按乘法原理，有：7!5!=33868800(种)方案。(c) 先从5个女生中选3个女生放入A，B之间，有种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有(7+1)! = 8!由于A，B可交换，如图*A*B* 或 *B*A*故按乘法原理，有：23!8!=4838400（种）1.3 m个男生
3、，n个女生，排成一行，其中m，n都是正整数，若(a) 男生不相邻(mn+1)；(b) n个女生形成一个整体；(c) 男生A和女生B排在一起；分别讨论有多少种方案.解 (a) 先将n个女生排列，有n!种方法，共有n+1个空隙，选出m个空隙，共有种方法，再插入男生，有m!种方法，按乘法原理，有：n!m!n!m!=种方案。(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两人内部
4、交换，故有2(n+m-1)!种方案。1.4 26个英文字母进行排列，要求x和y之间有5个字母的排列数.解 选入26224个字母中选取5个字母，有种方法，5个字母内部排列，有5!种方案，再将X*Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X与Y可交换，故按乘法原理，有：25!20!=25!20!=4024! 40又因为：ln40+0.5(lg+lg48)+24(lg24lge)1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481)=25.39325777所以，结果为2.4
5、731916641.5 求3000到8000之间的奇整数的数目，而且没有相同的数字.解 30008000中各位不同的奇数，分类讨论：首位3，1874（末位不能取3）首位4，1875（末位全取）首位5，1874首位6，1875首位7，1874从而，由加法原理，得：87（45454）=56221232个。1.6 计算解 (参见p14) 1.7 试证被2n除尽.证 故能被整除。1.8 求1040和2030的公因数.解1.9 试证n2的正除数的数目是奇数.解1.10 证明任一正整数n可惟一地表示成如下形式：证.(1)可表示性：令M=(am-1,am-2,a2,a1):0aii，i=1,2,m-1，显然
6、|M|=m!；N=0,1,2,m!-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)!+02!+01! am-1(m-1)!+am-2(m-1)!+a22!+a11! (m-1)(m-1)!+(m-2)(m-1)!+22!+11!= m!-1 （见P14）即0 f(am-1,am-2,a2,a1)m!-1由于f是用普通乘法和普通加法所定义的，故从而f无歧义。从而有一确定的数K（0Km!-1），使K=f(am-1,am-2,a2
7、,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，ajbj且ajbj，从而由am-1(m-1)!+am-2(m-1)!+a22!+a11!= bm-1(m-1)!+bm-2(m-1)!+
8、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-a2|2!+|b2-a1|1!j!-(j-1)(j-1)!+22!+11!=j!-(j!-1)=1矛盾，这说明f是单射函数。由于|M|=|N|=m!有限，故f是双射函数，当然是满射函数，从而0到m!-1中的任何一个数都可以表示成上边(*)的形式。故，由nN，都有(am-1,am-2,a2,a1)M，使得n=am-1
9、(m-1)!+am-2(m-1)!+a22!+a11!这就证明了任何n可表示成以上形式。(2)唯一性： 用证明单射的方法，就可以证明表示法的唯一性(表示方法见 P14)，留给读者。1.11 证明，并给予组合解释.证.(参见 P28 (1-8-4)组合意义：（等式右边）由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
10、)。1.12 试证等式：证.证法一：根据二项式定理，(参见 P29 (1-8-5)(1+x)n=1+C(n,1)x+C(n,2)x2+ xn两边对求导，有n(1+x)n-1=C(n,1)+2C(n,2)x+ nxn-1令x=1，即得。证法二：组合意义：设有n个不同的小球，并有A、B两个合子，A合中恰好放入一个球，B合中可放入任意多个球。有两种放球方法：(1)（等式左边）先从n个球中选取k个，再从这k个球中任选一个放入A合，剩下的k-1个球全部放入B合中，方案数共为；(2)（等式右边）先从n个球中任选一个放入A合，剩下的n-1个球每个都有两种可能，要么放入B合，要么不放，方案数共为n2n-1；显
11、然，两种放球方法等效，两种放球方案数相等，即。1.13 有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数.解 设这n个不同的数为。若假定第一组取k1个数，第二组取k2个数，并且令m=k1+k2(m2)，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n个数中任选m个数(有C(n,m)种选法)，再从这m个数中从大到小取k1个数作为第一组数(有k1=1,2,m-1共m-1种取法)，将其余k2个数作为第二组数，即可。故总方案数为（参见第3题等式）。1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？解 第一次点火仅有一种
12、选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种,。即方案数为132211=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的个数。10-99中的零的个数为： 100-999中的零的个数为： 1000-9999中的零的个数为： =27+486+2 187 =2 70010000-99999中的零的个数为： =36+972+8 748+26 244
13、=36 000100000-99999中的零的个数为：=45+1 620+21 870+131 220+295 245=450 0001，000，000中的0的个数为： 6故1到1，000，000的整数中0的个数为：9+180+2 700+36 000+450 000+6=488 895。1.16 n个完全一样的球放到r个有标志的盒（nr）中，无一空盒，试问有多少种方案？解1.17 n和r都是正整数，而且rn，试证下列等式：解 (a) 方法一方法二（组合意义）等式左边：从n个元素种取r个元素做排列有种，就是等式左边；等式右边：先从n个元素中拿出一个元素排在首位，有n种方法，然后再从剩下的n-1
14、个元素中取r-1个元素做后面r-1位的排列，有种方法，按乘法原理，共有n种方法。(b) 方法一方法二（组合意义法）等式左边：从n个元素中取r个元素做r位排列，有种方案。等式右边：先从n个元素中取r-1个元素做r-1位排列，有种方法；再从剩下的n-r+1个元素中取1个元素，共有n-r+1种选法，按乘法原理，共有(c) 方法一方法二：（组合意义法）等式左边：从n个元素中取r个元素做r位排列，其方案数为；等式右边：从n个元素中先取出一个元素放在第一位，有n种方法，再从剩下的n-1个元素种取出r个元素放在第2位，第r位，第r+1位，有种方法，这样就多了一位，故应除去第r+1位的选取方法，共有n-r种选法，故总方案为。(d) 方法一方法二：（组合意义）等式左边：从n+1个不同的元素中取r个元素进行r位排列。其方案为；等式右边：(a) 不取某特定元素b，则r个元素需从剩下的n个元素
