组合数学第四版卢开澄标准答案-第三章

1、第三章3.12.一年级有100名学生参加中文，英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，试求通过3门学科考试的学生数。解.令：A1=通过中文考试的学生 A2=通过英语考试的学生 A3=通过数学考试的学生于是 |Z| =100，|A1|=92，|A2|=75，|A3|=65|A1A2|=65，|A1A3|=54，|A2A3|=45 此题没有给出：j有多少人通过三门中至少一门； k有多少人一门都没通过。但是由 max |A1|,|A2|,|A3| =max92,75,65=92故

2、可以认为：j至少有92人通过三门中至少一门考试，即100|A1A2A3|92k至多有8人没通过一门考试，即0| 8于是，根据容斥原理，有 |A1A2A3|=(|A1|+|A2|+|A3|)-(|A1A2|+|A1A3|+|A2A3|)+|A1A2A3|即 |A1A2A3|=|A1A2A3|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)=|A1A2A3|-(92+75+65)+(65+54+45)=|A1A2A3|-232+164=|A1A2A3|-68从而由 92-68|A1A2A3|-68100-68即 24|A1A2A3|-6832可得 24|A1A2A3

3、| 32故此，通过3门学科考试的学生数在24到32人之间。也可用容斥原理，即 |=|Z|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)-|A1A2A3|=100-(92+75+65)+(65+54+45)-|A1A2A3|=100-232+164-|A1A2A3|=32|A1A2A3|从而有 |A1A2A3|=32-|由已知 0|8，可得 24|A1A2A3|32故此，通过3门学科考试的学生数在24到32之间。3.13.试证：(a)|B|=|B|-|AB| (b)|C|=|C|-|AC|-|BC|+|(ABC)|证.(a)B =BZ (因为BZ)= B(A)

4、(零壹律:且有互补律Z=A) =(BA)(B) (分配律) =(AB)(B) (交换律)另外 (AB)(B) = (A)B (结合律，交换律，幂等律) =B (互补律A=) = (零壹律)所以 |B|=|AB|+|B|因此 |B|=|B|-|AB|(b)|C|=|C| (de Morgan律) =|C|-|(AB)C| (根据(a)，令A1=AB) =|C|-|(AC)(BC)| (分配律) =|C|-(|AC|+|BC|-|(AC)(BC)|) =|C|-|AC|-|BC|+|(AC)(BC)| =|C|-|AC|-|BC|+|(ABC)| (结合律，交换律，幂等律)3.14. N=1,2,

5、1000，求其中不被5和7除尽，但被3除尽的数的数目。解.定义： P1(x):3|x A1=x|xNP1(x)P2(x):5|x A2=x|xNP2(x)P3(x):7|x A3=x|xNP3(x)|A1| =1000/3=333 |A1A2|=1000/(35)=66|A1A3|=1000/(37)=47 |A1A2A3|=1000/(357)=9因此 |A1|=|A1|-|A1A2|-|A1A3|+|A1A2A3| =333-66-47+9=229因此 ，在11000中能被3整除，同时不能被5和7整除的数有229个。3.15. N=1,2,120，求其中被2,3,5,7,m个数除尽的数的数

6、目，m=0,1,2,3,4 。求不超过120的素数的数目。解.定义 P1(x):2|x A1=x|xNP1(x)P2(x):3|x A2=x|xNP2(x) P3(x):5|x A3=x|xNP3(x) P4(x):7|x A4=x|xNP4(x)|A1|=120/2=60 |A2|=120/3=40 |A3|=120/5=24 |A4|=120/7=17 |A1A2|=120/(23)=20 |A1A3|=120/(25)=12 |A1A4|=120/(27)=8|A2A3|=120/(57)=8 |A2A4|=120/(37)=5 |A3A4|=120/(57)=3 |A1A2A3|=12

7、0/(235)=4 |A1A2A4|=120/(237)=2 |A1A3A4|=120/(257)=1 |A2A3A4|=120/(357)=1|A1A2A3A4|=120/(2357)=0 |N|=120 p0=|N|=120 p1=|A1|+|A2|+|A3|+|A4|=60+40+24+17=141p2=|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+|A3A4|=20+12+8+8+5+3=56p3=|A1A2A3|+|A1A2A4|+|A1A3A4|+|A2A3A4|=4+2+1+1=8p4=|A1A2A3A4|=0 当m=0时，q0=p0-p1+p2-p3+p

8、4=120-141+56-8+0=27当m=1时，q1=p1-p2+p3-p4=141-256+38-40=53当m=2时，q2= p2-p3+p4=56-38+60=32当m=3时，q3= p3-p4=8-40=8当m=4时，q4= p4=0 由于10故不定方程n没有解，即|A2|=0因此p1=|A1|+|A2|+|A3|=10+3+0=13A1A2对应的不定方程是：ox1+x2+x3=10x17，x29，x30由于解若满足条件x17，x29，x30，则有 x1+x2+x37+9+0=1610故不定方程o没有解，即|A1A2|=0同理可得：|A1A3|=0，|A2A3|=0因此p2=|A1A

9、2|+|A1A3|+|A2A3|=0+0+0=0A1A2A3对应的不定方程是：px1+x2+x3=10x17，x29，x311由于解若满足条件x17，x29，x311，则有 x1+x2+x37+9+11=2710故不定方程p没有解，即p3=| A1A2A3|=0所以，不定方程k、也即不定方程j的解的数目为：q0=|= p0-p1+ p2- p3=66-13+0-0=53 。方法二：利用母函数方法不定方程j对应的母函数是：(1+x+x2+x3+x4+x5+x6)(1+x+x2+x3+x4+x5+x6+x7+x8)(1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)=(1+2x+3x

10、2+4x3+5x4+6x5+7x6+7x7+7x8+6x9+5x10+4x11+3x12+2x13+x14) (1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)不定方程j的解的数目为上述母函数中x10的系数：11+21+31+41+51+61+71+71+71+61+51=1+2+3+4+5+6+7+7+7+6+5=53 。3.23.求满足下列条件：jx1+x2+x3=406 x115，5 x220，10 x325的整数解的数目。解.(仿3.22题)方法一.利用容斥原理二，不定方程j与如下的不定方程k等价：kx1+x2+x3=190 x1 9，0 x2 15，0 x3 15(这

11、可通过作变换来实现)。对应于不定方程k的不受限的不定方程为：lx1+x2+x3=19x10，x20，x30设：X=x|x=(x1,x2 ,x3)是不定方程l的解;A1= x|x=(x1,x2 ,x3) 是不定方程l的解且x19+1=10;A2= x|x=(x1,x2 ,x3) 是不定方程l的解且x215+1=16;A3= x|x=(x1,x2 ,x3) 是不定方程l的解且x315+1=16;因此,根据定理3.6.4.可知，不定方程l的解的数目：p0=|X|=210A1对应的不定方程是：x1+x2+x3=19x110，x20，x30令： (x10, x20, x30)。利用m我们得到：x1+x2

12、+ x3=( x1-10)+ x2+ x3=( x1+x2+x3)-10=19-10=9所以不定方程m的解与下列不定方程：x1+x2+ x3=9x10, x20, x30的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为：|A1|=55同理可得：|A2|=10|A3|=10因此p1=|A1|+|A2|+|A3|=55+10+10=75A1A2对应的不定方程是：x1+x2+x3=19x110，x216，x30由于解若满足条件x110，x216，x30，则有x1+x2+x310+16+0=2619故不定方程n没有解，即|A1A2|=0同理可得：|A1A3|=0，|A2A3|=0因此p

13、2=|A1A2|+|A1A3|+|A2A3|=0+0+0=0A1A2A3对应的不定方程是：x1+x2+x3=19x110，x216，x316由于解若满足条件x110，x216，x316，则有 x1+x2+x310+16+16=4219故不定方程o没有解，即p3=| A1A2A3|=0所以，不定方程k、也即不定方程j的解的数目为：q0=|= p0-p1+ p2- p3=210-75+0-0=135 。方法二：利用母函数方法不定方程k对应的母函数是：(1+x+x2+x3+x4+x5+x6+x7+x8+x9) (1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+

14、x14+x15)2=(1-x10-2x16+2x26+x32-x42)(参见第三版习题2.16(P199)或第二版第二章习题7(P131)不定方程j的解的数目为上述母函数中x19的系数：1-1-2=-2=210-55-20=135 。3.24.求满足下列条件的整数解的数目：x1+x2+x3+x4=201 x15，0 x27，4 x38，2 x46。解.(仿题3.22)方法一：利用容斥原理二，不定方程j与如下的不定方程k等价：x1+x2+x3+x4=130 x14，0 x27，0 x34，0 x44(这可通过作变换来实现)。对应于不定方程k的不受限的不定方程为：x1+x2+x3+x4=13x10

15、，x20，x30，x40设：X=x|x=(x1,x2 ,x3,x4)是不定方程l的解;A1= x| x=(x1,x2 ,x3,x4)是不定方程l的解且x14+1=5;A2= x| x=(x1,x2 ,x3,x4)是不定方程l的解且x27+1=8;A3= x| x=(x1,x2 ,x3,x4)是不定方程l的解且x34+1=5;A4= x| x=(x1,x2 ,x3,x4)是不定方程l的解且x44+1=5;因此,根据定理3.6.4.可知，不定方程l的解的数目：p0=|X|=560A1对应的不定方程是：x1+x2+x3+x4=13x15，x20，x30，x40令： (x10, x20, x30, x

16、40)。利用m我们得到：x1+x2+ x3+x4=( x1-5)+ x2+ x3+x4=( x1+x2+x3+x4)-5=13-5=8所以不定方程m的解与下列不定方程：x1+x2+x3+x4=8x10, x20, x30, x40的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为：|A1|=165同理可得：|A2|=56|A3|=165|A4|=165因此 p1=|A1|+|A2|+|A3|+|A4|=165+56+165+165=551A1A2对应的不定方程是：x1+x2+x3+x4=13x15，x28，x30，x40令： (x10, x20, x30, x40)。利用n我们得

17、到：x1+x2+x3+x4=(x1-5)+(x2-8)+ x3+x4=( x1+x2+x3+x4)-(5+8)=13-13=0所以不定方程n的解与下列不定方程：x1+x2+x3+x4=0x10, x20, x30, x40的解一一对应。故根据定理3.6.4.可知，不定方程n的解的数目为：|A1A2| =1同理可得：|A1A3| =20|A1A4| =20|A2A3| =1|A2A4| =1|A3A4| =20因此 p2=|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+|A3A4|=1+20+20+1+1+20=63A1A2A3对应的不定方程是：x1+x2+x3+x4=13

18、x15，x28，x35，x40由于解若满足条件x15，x28，x35，x40，则有 x1+x2+x3+x45+8+5+0=1813故不定方程o没有解，即 |A1A2A3| = 0同理可得：|A1A2A4| = 0，|A1A3A4| = 0，|A2A3A4| = 0p3=|A1A2A3|+|A1A2A4|+|A1A3A4|+|A2A3A4| = 0+0+0+0 = 0A1A2A3A4对应的不定方程是：x1+x2+x3+x4=13x15，x28，x35，x45由于解若满足条件x15，x28，x35，x40，则有 x1+x2+x3+x45+8+5+5=2313故不定方程p没有解，即p4=| A1A2

19、A3A4|=0所以，不定方程k、也即不定方程j的解的数目为：q0=| = p0p1+p2p3+p4=560551+630+0=72。方法二.利用母函数方法,不定方程k对应的母函数是：(1+x+x2+x3+x4+x5+x6+x7)(1+x+x2+x3+x4)3=(1-3x5-x8+3x10+3x13-x15-3x18+x23)(参见第三版习题2.16(P199)或第二版第二章习题7(P131)不定方程j的解的数目为上述母函数中x13的系数：1-3-1+3+3=-3-+3+31=560-495-56+60+3=72 。3.25.试证满足下列条件：x1+x2+xn=r0 xi k，i=1,2,n的整

20、数解的数目为：。证.方法一.利用容斥原理二，取不定方程： x1+x2+xn=rxi0，i=1,2,，n设：X=x|x=(x1,x2,xn)是不定方程k的解 令：Pi(x): x=(x1,x2,xn)是不定方程k的解且满足条件：xik+1 (i=1,2,n)Ai=x| xXPi(x) (i=1,2,n)因此,根据定理3.6.4.可知，不定方程k的解的数目为：p0=|X|=并且，参考第三版P238 第3.9节的方法一，做相应的变换，可得：| Ai | = (1 i n)p1=| Ai | =| AiAj | = (1 i j n)p2=| AiAj |=| AiAjAk|= (1 i j n。证.

21、(组合模型法)考虑不定方程: x1+x2+xn=r (xi 1,1 i n) 的整数解。一方面，根据题3.29的方法三(第三章3.4节不定方程解法二)，有不定方程解的个数为个。另一方面，采用第三章3.4节不定方程解法一，令： Z = (x1,x2,xn)| x1+x2+xn=r, xi0 (1 i n) Pi(x): x Z 且 xi =0 Ai = x | Pi(x) (1 i n)于是 |Z| = | Ai | = = (少一个变量) | AiAj | = (少二个变量) | AiAjAk| = (少三个变量) | A1A2Am |=0 (没有变量)于是根据容斥原理二，有方程的整数解的个数

22、为| = |Z| Ai |+| AiAj |AiAjAk|+(-1)n| A1A2An | = + +(-1)n-1+(-1)n0 = 。故此，=。3.31. 设B是A的子集，|A|=n，|B|=m，求A的子集包含B的子集的数目，设子集的元素数目为r，m r n 。解. 设CA，BC，|C| = r，因此，为了求子集C的数目，只需将子集AC选定，即可得子集C，AC应在AB中选取，即能保证BC(ACAB BC(逆否律)而 |AB| =nm，|AC| =nr，因此子集AC有种选法，故子集C有种选法。3.32. m，r，nN，满足mrn，试证：= 。证.(组合模型法)设A=a1,a2,an，B=b1

23、,b2,bm，并且BA，考虑在集合A中选取子集C=,的个数，使得BC，令Z=C|CA|C|=r ，定义Pi( C ):CZ 且 biC (1 i m) Ai = C | CZ Pi( C ) (1 i m)则包含B的子集C的数目： 一方面，按题3.31，为 ； 另一方面，由于 |Z|=，| Ai |=，| AiAj | =| AiAjAk| =，| A1A2Am |=于是按容斥原理，为| = |Z| Ai |+| AiAj |AiAjAk|+(-1)m| A1A2Am | = +(-1)m = 因此，我们得到 ：= 。3.33.试证：(a)D(n,r,k)=D(n-k,r-k,0)(b)D(n

24、,r,k)=D(n-1,r-1,k-1)+(n-1)D(n-1,r-1,k)+(r-1)D(n-2,r-2,k)-D(n-2,r-2,k-1)其中D(n,r,-1)定义为0。(c)D(n,n,k)=nD(n-1,n-1,k)+(-1)n-k(d)D(n,r,k)=D(n-t,r-t,k-t)，t 0(e)D(n,r,k)=rD(n-1,r-1,k)+D(n-1,r,k)，其中r n(f)D(n,n-r,0) =D(n-i,r-i,0)，其中D(n,n,0) =DnD(n,r,k)是3.6节中的推广了的错排。证.(a)从1n个数中取出r个元素进行r位排列，要求其中有k个位满足条件：ai=i的方案

25、(其方案数为D(n,r,k)；相当于在r位中选出k个位，让这k个位满足条件：ai=i(这有种选法)，其余的r-k个位从剩下的n-k个数中选数做完全的错排(无一位满足条件ai=i)(这有D(n-k,r-k,0)种排法)的方案(根据乘法原理，其方案数为D(n-k,r-k,0)。所以D(n,r,k)=D(n-k,r-k,0)。(b)从1n个数中取出r个元素进行排列，要求其中有且仅有k个位满足条件：ai=i，其方案数为D(n,r,k)；根据a1=1和a11可分成两个部分：1)若a1=1，即数1排在第一位，则此种方案其余部分为从2n这n-1个数中取出r-1个元素进行排列，要求其中有k-1个位满足条件：a

26、i=i，其方案数为D(n-1,r-1,k-1)；2)若a11，即数1不排在第一位，于是可设a1=i0(i0=2,3,n)，即数i0排在第一位，根据2 i0 r和r+1 i0 n此种方案可分成两个部分：i)若r+1 i0 n，即数i0排在第一位，有n-r种选法，此种方案其余部分为从1,2, r ,r+1,i0-1,i0+1,n这n-1个数中取出r-1个元素进行排列，要求其中有k个位满足条件：ai=i，其选法为D(n-1,r-1,k)；于是，根据乘法原理，此种方案有(n-r)D(n-1,r-1,k)个。ii)若2 i0 r，即数i0排在第一位，有r-1种选法，并且数i0不排在第i0位，此种方案其余

27、部分所构成的方案集，我们设其为AA：从1,2, ,i0-1,i0+1,r,r+1,n这n-1个数中取出r-1个元素进行排列的方案，要求其中有k个位满足条件：ai=i (2 i r且 i i0)。为了计算|A|，我们来考虑另一方案集BB：从2,r,r+1,n这n-1个数中取出r-1个元素进行排列的方案，要求其中有k个位满足条件：ai=i (2 i r)。显然，|B| = D(n-1,r-1,k)。但是方案集B比方案集A，少了取数集为1,j1,jr-2(这里：ji i0(1 i r-2)的方案，这种方案有D(n-2,r-2,k)个，但是又多了不动位集为= i0,= i1,= ik-1的方案，这种方

28、案有D(n-2,r-2,k-1)个。所以，|A|=|B|+D(n-2,r-2,k)-D(n-2,r-2,k-1) = D(n-1,r-1,k)+D(n-2,r-2,k)-D(n-2,r-2,k-1)。因此，根据乘法原理，这类方案总数为(r-1)|A|=(r-1)D(n-1,r-1,k)+D(n-2,r-2,k)-D(n-2,r-2,k-1)。最后，按加法原理，我们有D(n,r,k) =D(n-1,r-1,k-1)+(n-r)D(n-1,r-1,k)+(r-1) D(n-1,r-1,k)+D(n-2,r-2,k)-D(n-2,r-2,k-1)=D(n-1,r-1,k-1)+(n-1)D(n-1,

29、r-1,k)+(r-1)D(n-2,r-2,k)-D(n-2,r-2,k-1)。(c)D(n,n,k)为将1n这n个数进行全排列，要求其中有k个位满足条件：ai=i的方案数；相当于在n位中选出k个位，让这k个位满足条件：ai=i，这有种选法，其余的n-k个位用剩下的n-k个数做完全的错排(无一位满足条件ai=i)，有Dn-k种错排，于是，根据乘法原理，有Dn-k种方案。所以D(n,n,k)=Dn-k。根据ppt第二章9定理2.9.1(2)Dn-nDn-1=(-1)n 可得Dn-k= (n-k)Dn-k-1+(-1)n-k于是，有D(n,n,k)=Dn-k= (n-k)Dn-k-1+(-1)n-k= (n-k)Dn-k-1+(-1)n-k= nDn-k-1+(-1)n-k= nDn-k-1+(-1)n-k=nD(n-1,n-1,k)+(-1)n-k。(d)从1n个数中取出r个元素进行r位排列，要求其中有k个位满足条件：ai=i(有D(n,r,k)种排法)，然后再从这k个位中选取t个位打上标记*(有种选法)的方案(根据乘法原理，其方案数为D(n,r,k)；相当于先在r位中选出t个位让其满足条件：ai=i并打上标记*(有种选法)，而后在剩下的n-t个数中取出r-t个元素进行r-t位排列，要求其中有k-t个位满足