组合数学第三版卢开澄习题答案

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之间正好有3个女生的排列

2、是多少？解 (a) 女生在一起当作一个人，先排列，然后将女生重新排列。（71）!×5!=8!×5!40320×120=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*故按乘法原理，有：2&#

3、215;×3!×8!=4838400（种）1.3 m个男生，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和

4、女生B排在一起，看作一人，和其余n-1+m-1=n+m-2个人一起，作排列，共有(n+m-2+1)=(n+m-1)!种方法，A，B两人内部交换，故有2×(n+m-1)!种方案。1.4 26个英文字母进行排列，要求x和y之间有5个字母的排列数.解 选入26224个字母中选取5个字母，有种方法，5个字母内部排列，有5!种方案，再将X*Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X与Y可交换，故按乘法原理，有：2××5!×20!=2××5!×20!=40×24! 40×

5、;×又因为：ln40+0.5(lg+lg48)+24(lg24lge)1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481)=25.39325777所以，结果为2.473191664×1.5 求3000到8000之间的奇整数的数目，而且没有相同的数字.解 30008000中各位不同的奇数，分类讨论：首位3，1×8×7×4（末位不能取3）首位4，1×8×7×5（末位全取）首位5，1×8×7×4首位6，1&#

6、215;8×7×5首位7，1×8×7×4从而，由加法原理，得：8×7×（45454）=56×221232个。1.6 计算解 (参见p14) 1.7 试证被2n除尽.证 故能被整除。1.8 求1040和2030的公因数.解1.9 试证n2的正除数的数目是奇数.解1.10 证明任一正整数n可惟一地表示成如下形式：证.(1)可表示性：令M=(am-1,am-2,¼,a2,a1):0£ai£i，i=1,2,¼,m-1，显然|M|=m!；N=0,1,2,¼,m!-1，显然|N

7、|=m!，其中m是大于n的任意整数。定义函数f : M®N 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)

8、£m!-1由于f是用普通乘法和普通加法所定义的，故从而f无歧义。从而有一确定的数K（0£K£m!-1），使K=f(am-1,am-2,¼,a2,a1)为证N中的任一数均可表示成上边(*)的形式，只要证明f是满射函数即可。但由于在两相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f是单射函数即可。否则，设存在某数K0ÎN,有(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

9、-2,¼,b2,b1)由于不相等,故必有某个j(£m-1)，使aj¹bj。不妨设这个j是第一个不使相等的，即ai=bi，aj¹bj且aj<bj，从而由am-1(m-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

10、-aj)j!-|bj-1-aj-1|×(j-1)!+¼+|b2-a2|×2!+|b2-a1|×1!³j!-(j-1)×(j-1)!+¼+2×2!+1×1!=j!-(j!-1)=1矛盾，这说明f是单射函数。由于|M|=|N|=m!有限，故f是双射函数，当然是满射函数，从而0到m!-1中的任何一个数都可以表示成上边(*)的形式。故，由nÎN，都有(am-1,am-2,¼,a2,a1)ÎM，使得n=am-1(m-1)!+am-2(m-1)!+¼+a22!+a11!这就证明

11、了任何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)。1.12 试证等式：证.证法一：根据二项式定理，(参见 P

12、29 (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；显然，两种放球方法等效，两种放球方案

13、数相等，即。1.13 有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数.解 设这n个不同的数为。若假定第一组取k1个数，第二组取k2个数，并且令m=k1+k2(m³2)，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n个数中任选m个数(有C(n,m)种选法)，再从这m个数中从大到小取k1个数作为第一组数(有k1=1,2,¼,m-1共m-1种取法)，将其余k2个数作为第二组数，即可。故总方案数为（参见第3题等式）。1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？解 第一次点火仅有一种选择，即

14、点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有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的个数。10-99中的零的个数为： 100-999中的零的个数为： 1000-9999中的零的个数为： =27+486+2 187 =2 70010000-99999中的零的

15、个数为： =36+972+8 748+26 244 =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个元素中拿

16、出一个元素排在首位，有n种方法，然后再从剩下的n-1个元素中取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位，有种方法，这样就多

17、了一位，故应除去第r+1位的选取方法，共有n-r种选法，故总方案为。(d) 方法一方法二：（组合意义）等式左边：从n+1个不同的元素中取r个元素进行r位排列。其方案为；等式右边：(a) 不取某特定元素b，则r个元素需从剩下的n个元素中取，然后做r位排列，共有种方案。(b) 取定某特定元素b，则其余r-1个元素需从剩下的n个元素中取，先做r-1位排列，共有种方法，再将特定元素b插入这r-1个元素形成的r个空隙中，有r种方法，故按乘法原理，共有r种方案。(e) 方法一 （根据(d)可得）方法二：组合意义（同样根据d）等式左边：从n+1个不同元素取r个元素做r位排列，其方案数为：等式右边：设是n-r

18、+1个特定元素。(a) 不取特定元素，剩下的r个元素做全排列，有=r!种方案。(b)(1)：取特定元素，但不取特定元素，于是先在剩下的r个元素中取r-1个元素做排列，有种方法，然后将插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r种方案。(2)：取特定元素，但不取特定元素，于是先在剩下的r+1个元素中取r-1个元素做排列，有种方法，然后，将插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r种方案。(n-r)：取特定元素，但不取特定元素，于是先在剩下的n-1个元素中取r-1个元素做排列，有种方法，然后，将插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r种方

19、案。(n-r+1）：取特定元素，先在剩下的n个元素中取r-1个元素做排列，有种方法，然后，将插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r种方案。最后，按加法原理，共有：1.18 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？解 先将5个球进行全排列，有5!种方法，再将三个空格插入5个球的6个空隙中，有种方法，然后将这/元素的排列一对一的放入8个盒子中，即完成了每盒最多一球，空盒不相邻的放球要求，总方案有：（种）1.19 n+m位由m个0，n个1组成符号串，其中nm+1，试问不存在两个1相邻的符号串的数目。解：先将m个0排成一

20、排，再将n个1插入m个0的m+1个空隙（因为nm+1,这可实现）,就得到了无相邻的n+m位0-1符号串，其方案数为。1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位.试问有多少种方案？解 甲单位选4人，则乙单位只能选3人；另外男同志要5人，而乙单位的3人全是男同志，还差2名男同志，故甲单位的男同志人数应至少是2，至多为4。1.21 一个盒子里有7个无区别的白球，5个无区别的黑球. 每次从中随机取走一个球，已知前面取走6个，其中3个是白的. 试问取第6个球是白球的概率.解 已知前面取走6个球，有

21、3个白球，则有3个黑球。故总的取球方案是；第六个球是白球的方案是因此取出第6个球是白球的概率1.22 求下图中从0到P的路径数：(a) 路径必须过A点；(b) 路径必须过道路AB；(c) 路径必须过A和C；(d) 道路AB封锁（但A，B两点开放）. 解 O(0,0), A(3,2), B(4,2), P(8,5), C(6,3)(a) 路分为两段：先从O到A，再从A到P，则有：(b)路分为三段：先从O到A，再从A到B；再从A到B；然后从B到P；(c) 路分为三段：先从O到A；再从A到C；然后从C到P；(d) (采用排除法)从O到P的满足不过AB的路 从O到P的路从O到P经过AB的路，因此：1.

22、23 另s=1,2,3,n+1,n2，试证：证而，故1.24 A=(a, b)|a, bZ, 0a9,0b5(a) 求x-y平面上以A作顶点的长方形的数目.(b) 求x-y平面上以A作顶点的正方形数目.解 (a) 先选定横作标，再选定纵坐标，其方案数为：(b) 求xy平面上以A作顶点的正方形数目。按边长分类：边长为1的正方形：9×545边长为2的正方形：(9-1)×(5-1)=32边长为3的正方形：(9-2)×(5-2)=21边长为4的正方形：(9-3)×(5-3)=12边长为5的正方形：(9-4)×(5-1)=5故总的以xy平面上A点作顶点的

23、正方形的数目，按加法原理可得数目为115.1.25 平面上有15个点P1, P2, , P15，其中P1, P2, P3, P4, P5共线，此外不存在3点共线的.(a) 求至少过15个点中两点的直线的数目.(b) 求由15个点中3点组成的三角形的数目.解 (a) (采用排除法)至少过15个点中两点的直线数目在15个点中任选2个点将有一条直线从中选2点构成直线所在的直线l(b) (采用排除法)由15个点中3点组成的三角形的数目任在15个点中取3点构成三角形的数目在5个点中取3点构成的“三角形”的数目1.26 S=1, 2, , 1000，a，bS，使ab0 mod 5，求数偶a, b的数目.解

24、 因为 所以 ab5k （k是整数）1a1000, 1b10001ab100000015k10000001k200000所以满足 且1a,b1000的a,b的数目为2000001.27 6位男宾，5位女宾围一圆桌而坐(a) 女宾不相邻有多少种方案？(b) 所有女宾在一起有多少种方案？(c) 一女宾A和两位男宾相邻又有多少种方案？解 (a) 先将6位男宾作圆排列有在将5位女宾插入6个空格，每格一人，共有6×5×4×3×2×1720按乘法原理：有120×72086400(b) 5位女宾在一起，可看作一人，与6位男宾一起，先做圆排列，有=6

25、!=720然后5位女宾内部作线排列，有5!120。所以，总方案为：720×12086400(c) 先将6个男宾做圆排列，共有=120种方法。再将女宾A随便插入6个空格中的一个，有6种方法。然后将剩下的4个女宾插入5个空格中，但每个空格不限人数，故相当于将4个有区别的球放入5个不同的盒子中的放球方案(可重组合)，共有=5×6×7×81680。所以，按乘法原理，有120×6×16801209600种方案。1.28 k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数.解 先将k×n个来宾分成k堆，每堆n个人，有再将每堆n个

26、人做圆排列，有(n-1)!,共有种方法。故按乘法原理，有1.29 从n个对象中取r个作圆排列，求其方案数目. 已知1rn.解 每一个r个人围成的圈（圆排列）即每一个r圈相当于r个r排列。故不同的方案数为若不计顺逆方向，则为。1.30 试证下列等式证 (a) 方法一方法二：组合意义法：一方面，从n个元素中取出r个元素，然后再做排列，故按乘法原理，其数目为另一方面：先从n个元素中取出1个元素，排在第一位，再从剩下的n-1个元素中取出r-1个元素，并将这r-1个元素排在第2r位，故按乘法原理，其方案数为这两方面的组合意义相同，故有因此，有：(b) 方法一方法二：组合意义一方面：从n个元素中取出r个元

27、素来，然后，在做排列，故按乘法原理，其方案数为另一方面：先从n个元素中先取出r-1个元素，将其排排列再第1r-1位，再从剩下的n-r+1个元素中取出1个元素排在第r位。故按乘法原理，其方案数为：；这两方面的组合意义相同，故有所以，有：(c) 方法一方法二：组合意义一方面，从n个元素中取出n-r个元素，然后再做排列，按乘法原理，其方案数为：另一方面，选从n个元素中取出1个元素排再第一位，再从剩下的n-1个元素中选取n-r+1个元素，排在第2n-r位。故按乘法原理，其方案数为这两方面的组合意义相同，可得：故有：1.31 试证任意r个相邻数的连乘：被r！除尽.证 由于是从n+r个元素中选取r个元素的

28、组合数，故当然是整数，因此，(n+1)(n+2)(n+r)可以整除r!，其商为组合数。1.32 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必须夹在两个x之间，问这样的排列数等于多少？解 由于y必须乘在两个x之间，故两个y只能夹在仅有的三个x之间，形成图象xyxyx，形成6个空档。其余的6个元素a,b,c,d,e,y,只能放在这6个空格处，这相当于将6个不同的小球放入6个不同的盒子中，允许空盒，且盒内还要排列的方案数。故：1.33 已知r, n, k都是正整数，rnk，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？解 先将nk个球

29、放入n个有标志的盒中，每盒k个球，其方案为1。再将剩下的r-nk个球放入这n个盒中，每盒球数不限，其方案数为故总的方案为1.34 在r, s, t, u, v, w, x, y, z的排列中求y居x和z中间的排列数.解 由于y必须居于x和z之间，故形成图象xyz，形成4个空格。其余r,s,t,u,v,w这6个元素，只能放在这4个空格处，这相当于将6个不同的小球放入4个不同的盒子中，允许空盒，且盒内还要进行排列的方案数。故有：方法2：将9个字母进行全排列，有9!中排列，而x,y,z这3个字母形成的3!个排列只看作一种排列xyz，故有：1.35 凸十边形的任意三条对角线不共点. 试求这凸十边形的对

30、角线交于多少个点？解 从一个顶点可引出7条线和第一条（从右到左）交的有1×7，和第二条交的有2×6条故和一个顶点引出的7条线相交的点为： 1×7+2×6+3×5+4×4+5×3+6×2+7×1=84故和从10点引出的对角线交的点有个84´10=840，但每个点重复了四次（因为每个点在两条线上，而每条线有两个端点）。故凸10 边形（这样的）对角线交于个点。故也可为1.36 试证一整数是另一整数的平方的必要条件是除尽它的数的数目是整数.证 “必要性”。若整数n是另一个整数的平方，则n一定可写成如下形

31、式： （参见P7例4）其中P1,P2,¼,Pe是e个不同的素数。由于第9题可得，除尽n的正整数数目为 (2a1+1)(2a2+1)¼(2ae+1)为奇数。“充分性”。若除尽正整数n的正整数的数目为奇数。则n一定是某个正整数的平方，否则，n不是平方数，则n一定是可分解成如下形式：其中P1,P2,¼,Pe是e个不同的素数，且b1,b2,¼,be中至少有一个奇数（否则n为平方数）。于是(2b1+1)(2b2+1)¼(2be+1)必为偶数，与充分性假设矛盾。1.37 给出的组合意义.证 组合意义一：从(n+r+1)个元素1,2,¼,n+r+1

32、中取出个元素i1<i2<¼<ir<ir+2<ir+2<¼ <in+r+1-m 的个数是。其中第r+1个位置上的元素ir+1可取r+1,r+2,¼,r+1+m。当ir+1取(r+1+k)时(k=0,1,2,¼,m)，前边r个数i1,i2,¼,ir可在1,2,¼,r+1+(k-1)这(r+k)个数里取，故有种取法；后边(n+r+1-m)-(r+1)=n-m个数ir+2,¼,in+r+1-m可在r+1+k+1, ¼,n+r+1这(n+r+1)-(r+1+k)=n-k个数中取，故有

33、。根据乘法原理，当ir+1=r+1+k时，这样的组合数为。根据加法原理，对k=0,1,2,¼,m作和，就有。注：参见 Combinatorial Problems and Exercise by L.Lovasz 0143.7 L896cP18-42 (i) P96 P172(i)The number of those(n+r+1-m)-tuples of1,2,¼,n+r+1Whose element is r+k+1is . Summing for k=0,1,2,¼,m,we get the result.第15题图1D(0, k)C (-1, k)A (-

34、r-1, 0)O (0, 0)组合意义二：（格路方法）等式左端：从点A(-r-1,0)到点C(-1,k)(k=0,1,2,¼,m)直接经过点D(0,k)再到点B(n-m,m)的路径数(参见本题图1)；等式右端：从点A(-r-1,0)到点B(n-m,m)的路径数。1.38 给出的组合意义.证.组合意义一：等式右端是从n+r+1个元素中取出r+1个作不允许重复的组合，结果不外乎有以下几种情况(参见P25等式3的组合意义)：第16题图1(1) r+1个元素的组合中含有的，相当于从n个元素中取r个组合，其组合数为（即A）。(2)r+1个元素的组合中不含有，但又含有元素的。即一个(r-1)-组

35、合。依来分，不外乎含和不含；不含的又依分，不外乎含和不含。不含而含的组合，相当于从n-1个元素中取r个元素的组合，然后加上而成，其组合数为。(3)r+1个元素的组合中不含和，但含有元素的。即不含的依来分，不外乎含和不含。不含而含的组合，相当于从n-2个元素中取出r个元素的组合，然后再加上而成，其组合数为。取出的r+1个组合元素中不含，但含有元素的。即不含的，又依来分，不外乎含有和不含有。不含而含的组合，相当于从n-(n-r-1)=r+1个元素中取出r个元素的组合而加上而成，其组合数为。(4)由组成的(r+1)-组合的组合数为。而且组合意义二：等式右端：从n+1个不同元素a1,a2,¼

36、,an,an+1,中任选r+1个元素的组合方案数；等式左端：从n+1个不同元素a1,a2,¼,an,an+1,中选取r+1个元素，一定选元素ar+k+1(k=0,1,2,¼,n-r)，但是不选元素ar+k+2,¼,an,an+1的组合方案数。1.39 证明证.借助P28等式4，可知： (n³r) (r=0,1,2,¼,n)从而有 (用了P29等式5)组合意义一：等式右端可看作从m个元素中取出n个元素进行组合。然后对这取出的n个元素进行染色（红，白）的所有方案，它为；等式左端可看作先从m个元素中取出k个元素（个数为），全部染以红色。再从剩下的(m

37、-k)个元素中取出(n-k)个元素（个数为），全部染以白色。根据乘法原理，从m个元素中取出n个元素，k个染上红色，(n-k)个染上白色的方案数为，k=0,1,2,¼,n；而从m个元素中取出n个元素染以红白两色的方案可分解成有0个，1个，n个染以红色的总和。故根据加法原理，17题成立。组合意义二：等式右端：将从m个不同的小球中任意选出的n个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数；等式左端：先从m个球中任选k个球放入第一个合子里(k=0,1,2,¼,n)，再从剩下的m-k个球中任选n-k个球放入第二个合子里，然后对k从0到n求和，就得到了

38、所有可能的放球方案数。1.40 从n个人中选r个围成一个圆圈，问有多少种不同的方案？解.每一个r个人围成的圈（圆排列）即每一个r圈相当于r个r排列。故不同的方案数为若不计顺逆方向，则为。1.41 分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法.解.（略）1.42 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法.解.（略）1.43 对于给定的正整数n，证明，当时，C(n,k)的最大值.证 取C(n,k)与C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)

39、/k。当k<n/2时，(n-k+1)/k>1，即C(n,k)>C(n,k-1)；当k>n/2时，(n-k+1)/k<1，即C(n,k)<C(n,k-1)；因此，得到当k=n/2或最接近n/2时，C(n,k)取得最大值。1.44 (a) 用组合方法证明和都是整数.(b) 证明是整数.证 (a)考虑2n个不同的球放入n个不同的合子里，每合两个的方案数。这个方案数应该是整数。对2n个球进行排列的方案数为(2n)!。而把2个球放入同一个合子里不计顺序，重复因子是2。n个合子内部的排列共重复计算了2n次，故总的重复因子是2n。因此，把2n个不同的球放入n个不同的合子里

40、，每合两个的方案数是。所以，是整数。同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。对3n个球进行排列的方案数为(3n)!。而把3个球放入同一个合子里不计顺序，重复因子是3!=2×3。n个合子内部的排列共重复计算了2n×3n次，故总的重复因子是2n×3n。因此，把3n个不同的球放入n个不同的合子里，每合3个的方案数是。所以，是整数。(b)考虑n2个不同的球放入n个相同的合子里，每合n个的方案数。这个方案数应该是整数。对n2个球进行排列的方案数为(n2)!。而把n个球放入同一个合子里不计顺序，重复因子是n!。n个合子内部的排列共

41、重复计算了(n!)n次，故重复因子是(n!)n。另外，由于n个合子相同，放入不同的合子是没有区别的，其重复因子是n!。故此，总的重复因子是(n!)n+1。因此，把n2个不同的球放入n个相同的合子里，每合n个的方案数是。所以，是整数。1.45 (a) 在2n个球中，有n个相同. 求从这2n个球中选取n个的方案数.(b) 在3n+1个球中，有n个相同. 求从这3n+1个球中选取n个的方案数.解 (a)相当于从n个不同的小球中取出m个小球(0£m£n),再从n个相同的小球中取出n-m个小球，m=0,1,2,¼,n的方案数。根据加法原理，这个方案数应该是：C(n,0)+

42、C(n,1)+¼+ C(n,n)=2n。同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。(b)相当于从2n+1个不同的小球中取出m个小球(0£m£n),再从n个相同的小球中取出n-m个小球，m=0,1,2,¼,n的方案数。根据加法原理，这个方案数应该是：C(2n+1,0)+ C(2n+1,1)+¼+ C(2n+1,n)。1.46 证明在由字母表0, 1, 2生成的长度为n的字符串中(a) 0出现偶数次的字符串有个；(b) 证 (a)方法一：采用（串值）数学归纳法基始当n=1时，0出现偶数次，长度为1的字符串

43、有=2个（即1和2两个长度为1的字符串）。所证结论成立；归纳假设当n=m(1£m£k)时，假设所证结论成立。即，0出现偶数次，长度为m的字符串有个；归纳当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：(1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，按乘法原理，由归纳假设，此种字符串有×2=3k+1个；(2)给0出现奇数次，长度为k的字符串后面再增加一位是0的数，因此，按乘法原理，由归纳假设，此种字符串有×1=个；所以，按加法原理，0出现偶数次，长度为k+1的字符串共有(3k+1)+= 个。所证结论成立；

44、归纳完毕。方法二：采用指数型母函数方法设：an0出现偶数次，长度为n的字符串的个数，则an的指数型母函数所以，（规定a0=1）。(b)利用组合意义法来证考虑0出现偶数次，长度为n的字符串的个数。根据上面(a)，已证其个数为；另一方面，相当于先从n个位置中选取2m(0£2m£n)个（有种选择）放置上数0,再在剩下的n-2m个位置上放置数1或2（有2n-2m种放法），按乘法原理，是个，m=0,1,2,¼,q ()的方案数。按加法原理，此方案数为。因此，我们有。1.47 5台教学机器m个学生使用.使用第1台和第2台的人数相等，有多少种分配方案？解 先从m个学生中选取k个

45、使用第1台机器，再从剩下的m-k个学生中选取k个使用第2台机器，其余m-2k个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C(m,k) C(m-k,k)×3(m-2k)。这里k=0,1,2,¼,q ()，于是，按加法原理，共有种使用方案。1.48 在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？(n+1,n+1)(0,1)(1,0)(n,n+1)(n,n)(0,0)第48题图1解 转化为格路问题（弱领先条件参见P36例4该例是强领先条件）。即从(0,0)到(n,n)，只能从对角线上方走，但可以碰到对角线。它可看作是从(0

46、,1)到(n,n+1)的强领先条件（只能从对角线上方走，但不可以碰到对角线）的格路问题。更进一步的，它可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(因为此种格路第一步必到(0,1)格点)。故这样的字符串有1.49 在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？解 设：g(n,k)为从1n中选取不同且互不相邻的k个数的方案数。于是，按这k个数中有无数n而分为两种情况：(1)若选n，则必不能选n-1，故此种方案数为g(n-2,k-1)；(2)若不选n，则可以选n-1，故此种方案数为g(n-1,k)；所以，按加法原理，总的方案数g(n,k)=g(n-2,k-1)+g(

47、n-1,k)。且只有当n³2k-1时，g(n,k)>0；否则g(n,k)=0。因此，可给定初始值：g(2k-1,k)=1，g(2k-2,k)=0。1.50 (a) 在由5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？(b) 在m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个？解 (a)先将5个0排成一列：00000，一个1若插在两个0中间，就形成一个“010”，则同时出现“01”和“10”，计数为2；若插在两端，则仅出现一个01”或“10”，计数为1。现在要出现01”或“10”的总次数为4，可有两种办法：(1)先把两个1插入

48、五个0所形成的四个空档内，再将剩下的两个1放在已插入的1的前面，比如：011100100。按乘法原理，有C(4,2)×C(2+2-1,2)= C(4,2)×C(3,2)种方案；(2)先把一个1插入五个0所形成的四个空档内，然后取两个1分别插入两端，剩下的一个1放在已插入的1的前面，比如：100011001。按乘法原理，有C(4,1)×3种方案；最后，按加法原理，总的方案数为C(4,2)×C(3,2)+C(4,1)×3=30。(b)若k为奇数，则只有一种办法：先把个1插入m个0所形成的m-1个空档内，然后取一个1插入头或尾，最后将剩下的个1放在已

49、插入的个1的前面，形成出现k个01或10的格局。按乘法原理，总的方案数为；若k为偶数，则现在可有两种办法：(1)先把个1插入m个0所形成的m-1个空档内，再将剩下的个1放在已插入的个1的前面，形成出现k个01或10的格局。按乘法原理，有=种方案；(2)先把个1插入m个0所形成的m-1个空档内，然后取两个1分别插入两端，再将剩下的个1放在已插入的个1的前面，形成出现k个01或10的格局。按乘法原理，有=种方案；最后，按加法原理，总的方案数为+。1.51 从N=1, 2, , 20中选出3个数，使得没有两个数相邻，有多少种方案？解 方法一（采用排除法）在20个数中选取3个数都不相邻的方案数；从12

50、0这20个数中选取3个数，总数为然后在其中去掉有3个数相邻的方案数，也要去掉有两个数相邻的方案数。这样，就是在20个数中选取3个数都不相邻的方案数。设选取的3个数，。如果这三个数相邻，若，则118。故此种方案有18个。如果有两个数相邻，不妨设是，且，则119，但是，当1或19时，2或20，只有3和18不能选，故有3个数不能选，17种选择方案；当1或19时，有4个数不能选。故有16种选择，因此，此种方案数为：2×1717×16故此，从120这20个数种选取3个互不相邻的数的方案数为：方法二（采用一一对应技术）设：A:从120这20个数中选取三个数，使得无两数相邻的方案集。B：

51、从118这18个数中选取三个数，使得三数可相邻的方案集。这里，<< 且 2，2设：<< 且 1，1建立双射函数h：AB，使得：h(,)=(,)其有逆函数:BA,（，）（，）故此，根据一一对应技术，有1.52 从N=1, 2, , n中选出k个数，使之没有两数相邻，求不同方案数.解 （采用一一对应技术）设：A：从1n这n个数中选取k个数，使之无二数相邻的方案集。B：从1n-k+1这n-k+1个数中选取k个数，二数可相邻的方案集。这里：，（i1k-1），（i=1k-1）建立双射函数：h：ABh(,)=(,)其逆函数为：:BA故此，根据一一对应技术，有：1.53 把n个无区别

52、的球放进有标志1, 2, , n的n个盒子中，每个盒子可放多于一个球，求有多少种方案？解 （采用一一对应技术）设：A：将n个无区别的球放进n个有区别的盒子中，每盒球数不限的方案集。B：n个“*”，n-1个隔档“1”构成的线性图案集。于是一种放球方案与一种图案一一对应，根据一一对应技术，有1.54 m个1，n个0进行排列，求1不相邻的排列数. 设n>m.解 n个0有n+1个空隙（内外都计），选取m个空隙（可以选取，因为m<n<n+1）, 插入m个1 ，每空插入一个1，使得后两个1相邻。故其方案数为：1.55 偶数位的对称数，即从左向右读法与从右向左的读法相同，如3223. 试证

53、这样的数可被11整除.证 此种偶数位得对称数形式语言称为迴文。设任一个这样得数m有2n位，故有：由于（当k是奇数时），故可被11整除。1.56 n个男人与n个女人沿一圆桌坐下，问两个女人之间坐一个男人的方案数. 又m个女人n个男人，且m<n，沿一圆桌坐下，求无两个女人并坐的方案数.解 先将n个女人进行圆排列，共有=(n-1)! 种方法，再将n个男人插入n个女人形成得n个空位中，则有n!种方法。故按乘法原理，此种方案数为(n-1)!×n! 个。先将n个男人进行圆排列，共有=(n-1)! 种方法，再将m个女人插入n个男人形成得n个空位中。则有。按乘法原理，此种排法有1.57 n个人分别沿着两圆桌坐下，一张r个人，另一张n-r个人，试问有多少种不同的方案？解 先从n个人中选取r个人，有种选法，然后将r个人排成一圆桌，有=(r-1)!种方法，再将其余(n-r)个人排成一圆桌=(n-r-1)!种方法，故共有×(r-1)!×(n-r-1)!=1.58 一圆周上n个点标以1, 2, , n. 每一点与其他n-1个点连以直线，试问这些直线交于圆内有多少点？解