组合数学第四版卢开澄标准答案-第三章资料11519.pdf

《组合数学第四版卢开澄标准答案-第三章资料11519.pdf》由会员分享，可在线阅读，更多相关《组合数学第四版卢开澄标准答案-第三章资料11519.pdf（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【第 1 页 共 42 页】第三章 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 此题没有给出：有多少人通过三门中至少一门；有多少人一门都没通过。但是由 max|A1|,|A2|

2、,|A3|=max92,75,65=92 故可以认为：至少有 92 人通过三门中至少一门考试，即 100|A1A2A3|92 至多有 8 人没通过一门考试，即 0|1A2A3A|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|-6810

3、0-68 即 24|A1A2A3|-6832 可得 24|A1A2A3|32 故此，通过 3 门学科考试的学生数在 24 到 32 人之间。也可用容斥原理，即|1A2A3A|=|Z|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)-|A1A2A3|=100-(92+75+65)+(65+54+45)-|A1A2A3|=100-232+164-|A1A2A3|【第 2 页 共 42 页】=32|A1A2A3|从而有|A1A2A3|=32-|1A2A3A|由已知 0|1A2A3A|8，可得 24|A1A2A3|32 故此，通过 3 门学科考试的学生数在 24 到 3

4、2 之间。3.13.试证：(a)|AB|=|B|-|AB|(b)|ABC|=|C|-|AC|-|BC|+|(ABC)|证.(a)B=BZ (因为 BZ)=B(AA)(零壹律:且有互补律 Z=AA)=(BA)(BA)(分配律)=(AB)(AB)(交换律)另外 (AB)(AB)=(AA)B (结合律，交换律，幂等律)=B (互补律 AA=)=(零壹律)所以|B|=|AB|+|AB|因此|AB|=|B|-|AB|(b)|ABC|=|BA C|(de Morgan 律)=|C|-|(AB)C|(根据(a)，令 A1=AB)=|C|-|(AC)(BC)|(分配律)【第 3 页 共 42 页】=|C|-(

5、|AC|+|BC|-|(AC)(BC)|)=|C|-|AC|-|BC|+|(AC)(BC)|=|C|-|AC|-|BC|+|(ABC)|(结合律，交换律，幂等律)3.14.N=1,2,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 因此|A12A3A|=|A1|-|A1A2|-|A1A3|

6、+|A1A2A3|=333-66-47+9=229 因此，在 11000 中能被 3 整除，同时不能被 5 和 7 整除的数有 229 个。3.15.N=1,2,120，求其中被 2,3,5,7,m 个数除尽的数的数目，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

7、|A1A3|=120/(25)=12|A1A4|=120/(27)=8|A2A3|=120/(57)=8|A2A4|=120/(37)=5|A3A4|=120/(57)=3|A1A2A3|=120/(235)=4|A1A2A4|=120/(237)=2 【第 4 页 共 42 页】|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=141 p2=|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+

8、|A3A4|=20+12+8+8+5+3=56 p3=|A1A2A3|+|A1A2A4|+|A1A3A4|+|A2A3A4|=4+2+1+1=8 p4=|A1A2A3A4|=0 当 m=0 时，q0=p0-p1+p2-p3+p4=120-141+56-8+0=27 当 m=1 时，q1=p1-12p2+23p3-34p4=141-256+38-40=53 当 m=2 时，q2=p2-13p3+24p4=56-38+60=32 当 m=3 时，q3=p3-14p4=8-40=8 当 m=4 时，q4=p4=0 由于12010 故不定方程没有解，即|A2|=0 因此 p1=|A1|+|A2|+|A

9、3|=10+3+0=13 A1A2对应的不定方程是：x1+x2+x3=10 x17，x29，x30 由于解若满足条件 x17，x29，x30，则有 x1+x2+x37+9+0=1610 故不定方程没有解，即|A1A2|=0 同理可得：|A1A3|=0，|A2A3|=0 因此 p2=|A1A2|+|A1A3|+|A2A3|=0+0+0=0 A1A2A3对应的不定方程是：x1+x2+x3=10 x17，x29，x311 由于解若满足条件 x17，x29，x311，则有 【第 13 页 共 42 页】x1+x2+x37+9+11=2710 故不定方程没有解，即 p3=|A1A2A3|=0 所以，不定

10、方程、也即不定方程的解的数目为：q0=|321AAA|=p0-p1+p2-p3=66-13+0-0=53 。方法二：利用母函数方法 不定方程对应的母函数是：(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+3x2+4x3+5x4+6x5+7x6+7x7+7x8+6x9+5x10+4x11+3x12+2x13+x14)(1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10)不定方程的解的数目为上述母函数中 x10的系数：11+21+31+41+51+61+71+71

11、+71+61+51=1+2+3+4+5+6+7+7+7+6+5=53 。3.23.求满足下列条件：x1+x2+x3=40 6 x115，5 x220，10 x325 的整数解的数目。解.(仿 3.22 题)方法一.利用容斥原理二，不定方程与如下的不定方程等价：x1+x2+x3=19 0 x1 9，0 x2 15，0 x3 15(这可通过作变换1056332211xxx来实现)。对应于不定方程的不受限的不定方程为：x1+x2+x3=19 x10，x20，x30 【第 14 页 共 42 页】设：X=x|x=(x1,x2,x3)是不定方程的解;A1=x|x=(x1,x2,x3)是不定方程的解且 x

12、19+1=10;A2=x|x=(x1,x2,x3)是不定方程的解且 x215+1=16;A3=x|x=(x1,x2,x3)是不定方程的解且 x315+1=16;因此,根据定理 3.6.4.可知，不定方程的解的数目：p0=|X|=191193=1921=221=122021=210 A1对应的不定方程是：x1+x2+x3=19 x110，x20，x30 令：33221110 xxx(10,20,30)。利用我们得到：1+2+3=(x1-10)+x2+x3=(x1+x2+x3)-10=19-10=9 所以不定方程的解与下列不定方程：1+2+3=9 10,20,30 的解一一对应。故根据定理 3.6

13、.4.可知，不定方程的解的数目为：|A1|=9193=911=211=121011=55 同理可得：|A2|=1619116193)(=35=25=1245=10|A3|=1619116193)(=35=25=1245=10因此p1=|A1|+|A2|+|A3|=55+10+10=75 A1A2对应的不定方程是：x1+x2+x3=19 x110，x216，x30 由于解若满足条件 x110，x216，x30，则有 x1+x2+x310+16+0=2619 故不定方程没有解，即|A1A2|=0 同理可得：|A1A3|=0，|A2A3|=0 因此 p2=|A1A2|+|A1A3|+|A2A3|=0

14、+0+0=0 【第 15 页 共 42 页】A1A2A3对应的不定方程是：x1+x2+x3=19 x110，x216，x316 由于解若满足条件 x110，x216，x316，则有 x1+x2+x310+16+16=4219 故不定方程没有解，即 p3=|A1A2A3|=0 所以，不定方程、也即不定方程的解的数目为：q0=|321AAA|=p0-p1+p2-p3=210-75+0-0=135。方法二：利用母函数方法 不定方程对应的母函数是：(1+x+x2+x3+x4+x5+x6+x7+x8+x9)(1+x+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+

15、x15)2 216101111xxxx3321610)1()21)(1(xxxx=(1-x10-2x16+2x26+x32-x42)nxnxx222423222(参见第三版习题 2.16(P199)或第二版第二章习题 7(P131)不定方程的解的数目为上述母函数中 x19的系数：1221-1211-225=122021-121011-21245=210-55-20=135。3.24.求满足下列条件的整数解的数目：x1+x2+x3+x4=20 1 x15，0 x27，4 x38，2 x46。解.(仿题 3.22)方法一：利用容斥原理二，不定方程与如下的不定方程等价：x1+x2+x3+x4=13

16、0 x14，0 x27，0 x34，0 x44 【第 16 页 共 42 页】(这可通过作变换24144332211xxxx来实现)。对应于不定方程的不受限的不定方程为：x1+x2+x3+x4=13 x10，x20，x30，x40 设：X=x|x=(x1,x2,x3,x4)是不定方程的解;A1=x|x=(x1,x2,x3,x4)是不定方程的解且 x14+1=5;A2=x|x=(x1,x2,x3,x4)是不定方程的解且 x27+1=8;A3=x|x=(x1,x2,x3,x4)是不定方程的解且 x34+1=5;A4=x|x=(x1,x2,x3,x4)是不定方程的解且 x44+1=5;因此,根据定理

17、 3.6.4.可知，不定方程的解的数目：p0=|X|=131134=1316=316=123141516=560 A1对应的不定方程是：x1+x2+x3+x4=13 x15，x20，x30，x40 令：443322115xxxx(10,20,30,40)。利用我们得到：1+2+3+4=(x1-5)+x2+x3+x4=(x1+x2+x3+x4)-5=13-5=8 所以不定方程的解与下列不定方程：1+2+3+4=8 10,20,30,40 的解一一对应。故根据定理 3.6.4.可知，不定方程的解的数目为：|A1|=8184=811=311=12391011=165 同理可得：|A2|=8131)8

18、13(4=58=38=123678=56 【第 17 页 共 42 页】|A3|=5131)513(4=811=311=12391011=165|A4|=5131)513(4=811=311=12391011=165 因此 p1=|A1|+|A2|+|A3|+|A4|=165+56+165+165=551 A1A2对应的不定方程是：x1+x2+x3+x4=13 x15，x28，x30，x40 令：4433221185xxxx(10,20,30,40)。利用我们得到：1+2+3+4=(x1-5)+(x2-8)+x3+x4=(x1+x2+x3+x4)-(5+8)=13-13=0 所以不定方程的解与

19、下列不定方程：1+2+3+4=0 10,20,30,40 的解一一对应。故根据定理 3.6.4.可知，不定方程的解的数目为：|A1A2|=0104=03=1 同理可得：|A1A3|=55131)5513(4=36=123456=20|A1A4|=55131)5513(4=36=123456=20|A2A3|=58131)5813(4=03=1|A2A4|=58131)5813(4=03=1|A3A4|=55131)5513(4=36=123456=20因此 p2=|A1A2|+|A1A3|+|A1A4|+|A2A3|+|A2A4|+|A3A4|=1+20+20+1+1+20=63A1A2A3对

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

21、45+8+5+5=2313 故不定方程没有解，即 p4=|A1A2A3A4|=0 所以，不定方程、也即不定方程的解的数目为：q0=|1A2A3A4A|=p0p1+p2p3+p4=560551+630+0=72。方法二.利用母函数方法,不定方程对应的母函数是：(1+x+x2+x3+x4+x5+x6+x7)(1+x+x2+x3+x4)3 3581111xxxx4151058)1()331)(1(xxxxx=(1-3x5-x8+3x10+3x13-x15-3x18+x23)nxnxx333534332(参见第三版习题 2.16(P199)或第二版第二章习题 7(P131)不定方程的解的数目为上述母函

22、数中 x13的系数：1316-3311-138+336+333=123141516-312391011-123678+3123456+31=560-495-56+60+3=72。3.25.试证满足下列条件：x1+x2+xn=r 0 xi k，i=1,2,n 【第 19 页 共 42 页】的整数解的数目为：nii0)1(in11)1(nnikr。证.方法一.利用容斥原理二，取不定方程：x1+x2+xn=r xi0，i=1,2,，n 设：X=x|x=(x1,x2,xn)是不定方程的解 令：Pi(x):x=(x1,x2,xn)是不定方程的解且满足条件：xik+1 (i=1,2,n)Ai=x|xXPi

23、(x)(i=1,2,n)因此,根据定理 3.6.4.可知，不定方程的解的数目为：p0=|X|=rrn1=11nnr=0n11nnr 并且，参考第三版 P238 第 3.9 节的方法一，做相应的变换，可得：|Ai|=)1(1)1(krkrn=11)1(nnkr (1 i n)p1=ni 1|Ai|=1n11)1(nnkr|AiAj|=)1(21)1(2(krkrn=11)1(2nnkr(1 i j n)p2=ji|AiAj|=2n11)1(2nnkr|AiAjAk|=11)1(3nnkr(1 i j n。证.(组合模型法)考虑不定方程:x1+x2+xn=r(xi 1,1 i n)的整数解。一方面

24、，根据题 3.29 的方法三(第三章 3.4 节不定方程解法二)，有不定方程解的个数为11nr个。另一方面，采用第三章 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|=rrn1|Ai|=rrn1)1(=rrn11 (少一个变量)|AiAj|=rrn1)2(=rrn12 (少二个变量)|AiAjAk|=rrn1)3(=rrn13 (少三个变量)|A1A2Am|=0 (没有变量)【第 24 页 共 42 页】于是根据容斥原理二，有方程的整数解的个数为|1A2AnA|=|

25、Z|ni 1|Ai|+ji|AiAj|kji|AiAjAk|+(-1)n|A1A2An|=rrn11nrrn11+2nrrn12 3nrrn13+(-1)n-1rr+(-1)n0 =10)1(niiinrirn1。故此，10)1(niiinrirn1=11nr。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，因此

26、子集 AC 有rnmn种选法，故子集 C 有rnmn种选法。3.32.m，r，nN，满足 mrn，试证：rnmn=mii0)1(im rin。证.(组合模型法)设 A=a1,a2,an，B=b1,b2,bm，并且 BA，考虑在集合 A 中选取子集 C=1ia,ria的个数，使得 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，为rnmn；另一方面，由于|Z|=rn，|Ai|=rn 1，|AiAj|=rn2|AiAjAk|=rn3，|A1A2Am|=rmn 于是按容

27、斥原理，为 【第 25 页 共 42 页】|1A2AmA|=|Z|mi 1|Ai|+ji|AiAj|kji|AiAjAk|+(-1)m|A1A2Am|=rn1m rn 1+2m rn23m rn3+(-1)m rmn =mii0)1(im rin 因此，我们得到：rnmn=mii0)1(im rin。3.33.试证：(a)D(n,r,k)=krD(n-k,r-k,0)(b)D(n,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

28、-1,k)+(-1)n-kkn(d)tkD(n,r,k)=trD(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)=riir0D(n-i,r-i,0)，其中 D(n,n,0)=Dn D(n,r,k)是 3.6 节中的推广了的错排。证.(a)从 1n 个数中取出 r 个元素进行 r 位排列，要求其中有 k 个位满足条件：ai=i 的方案(其方案数为 D(n,r,k)；相当于在 r 位中选出 k 个位，让这 k 个位满足条件：ai=i(这有kr种选法)，其余的 r-k 个位从剩下的 n-k 个数中选数做

29、完全的错排(无一位满足条件 ai=i)(这有D(n-k,r-k,0)种排法)的方案(根据乘法原理，其方案数为krD(n-k,r-k,0)。所以 D(n,r,k)=krD(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 个位满足条件：ai=i，其方案数为 D(n-1,r-1,k-1)；【第 26 页 共 42 页】2)若

30、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位，此种方案其余部分

31、所构成的方案集，我们设其为 A A：从 1,2,i0-1,i0+1,r,r+1,n 这 n-1 个数中取出 r-1 个元素进行排列的方案，要求其中有 k 个位满足条件：ai=i(2 i r 且 i i0)。为了计算|A|，我们来考虑另一方案集 B B：从 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)个，但是又多了不动位集为0ia=i0

32、,1ia=i1,1kia=ik-1的方案，这种方案有 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-

33、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)。(c)D(n,n,k)为将 1n 这 n 个数进行全排列，要求其中有 k 个位满足条件：ai=i 的方案数；相当于在 n 位中选出 k 个位，让这 k 个位满足条件：ai=i，这有kn种选法，其余的 n-k 个位用剩下的 n-k 个数做完全的错排(无一位满足条件 ai=i)，有 Dn-k种错排，于是，根据乘法原理，有knDn-k种方案。所以 D(n,n,k)=knDn-k。根据 ppt 第二章9 定理 2.9.1(2)Dn-nDn-1=(-1)n 可得 Dn-k=(n-k

34、)Dn-k-1+(-1)n-k 于是，有 【第 27 页 共 42 页】D(n,n,k)=knDn-k=(n-k)knDn-k-1+(-1)n-kkn=(n-k)!)!(!kknnDn-k-1+(-1)n-kkn=n!)!1()!1(kknnDn-k-1+(-1)n-kkn=n kn 1Dn-k-1+(-1)n-kkn=nD(n-1,n-1,k)+(-1)n-kkn。(d)从1n个数中取出r个元素进行r位排列，要求其中有k个位满足条件：ai=i(有D(n,r,k)种排法)，然后再从这 k 个位中选取 t 个位打上标记*(有tk种选法)的方案(根据乘法原理，其方案数为tkD(n,r,k)；相当于

35、先在 r 位中选出 t 个位让其满足条件：ai=i 并打上标记*(有tr种选法)，而后在剩下的 n-t 个数中取出 r-t 个元素进行 r-t 位排列，要求其中有 k-t 个位 满 足 条 件：ai=i(有 D(n-t,r-t,k-t)种 排 法)的 方 案(根 据 乘 法 原 理，其 方 案 数 为trD(n-t,r-t,k-t)。所以 tkD(n,r,k)=trD(n-t,r-t,k-t)。(e)从 1n 个数中取出 r 个元素进行 r 位排列，要求其中有 k 个位满足条件：ai=i，其方案数为 D(n,r,k)；因为 r n，根据所选的 r 个元素中含数 n 和不含数 n 可分成两个部分

36、：1)若含数 n，则数 n 可排在这 r 个位的任一位上，有 n 种排法，此种方案其余部分为从1n-1 这 n-1 个数中取出 r-1 个元素进行 r-1 位排列，要求其中有 k-1 个位满足条件：ai=i，其方案数为 D(n-1,r-1,k-1)，于是，根据乘法原理，其方案数为 rD(n-1,r-1,k)；2)若不含数 n，则此种方案为从 1n-1 这 n-1 个数中取出 r 个元素进行 r 位排列，要求其中有 k 个位满足条件：ai=i，其方案数为 D(n-1,r,k)；最后，按加法原理，我们有 D(n,r,k)=rD(n-1,r-1,k)+D(n-1,r,k)。(f)【第 28 页 共

37、42 页】D(n,n-r,0)=riir0D(n-i,r-i,0)，其中 D(n,n,0)=Dn。3.34.nN，设 Pn表示在1,2,n的全排列中，排除了 k，紧随以 k+1，k=1,2,k+1，试证：Pn=Dn+Dn-1，nN。3.35.令 Dn(k)=D(n,n,k)，试证(a)Dn(k)=knDn-k(b)1nD1+2nD2+nnDn=n!(c)(k+1)Dn+1(k+1)=(n+1)Dn(k)。3.36.令 Dn(k)=D(n,n,k)，试证(a)nkk0Dn(k)=n!(b)Dn(0)Dn(1)=(-1)n(c)nkk02)1(Dn(k)=n!(d)1()1(0rkknkDn(k)

38、=n!，其中 r n。3.37.试证：(a)(mn)=(m)(n)(条件：(m,n)=1,即 m,n 互素)(b)对于素数 pi，i 1,(pi)=pi-pi-1 证.(a)可设 m=11p22pkkp (其中：i1(1 i k)n=11q22qllq (其中：j1(1 j l)由于(m,n)=1，即，m,n 互素，故素数 p1,p2,pk与素数 q1,q2,ql没有相同的，即，对任何i,j(1 i k，1 j l)，都有 piqj。故此 (mn)=mn(111p)(121p)(1kp1)(111q)(121q)(1lq1)=m(111p)(121p)(1kp1)n(111q)(121q)(1

39、lq1)=(m)(n)。若(m,n)1，即，m,n 不互素，则此等式不成立。例如，若 【第 29 页 共 42 页】m=20=225，n=30=235，(m,n)=25=101，即，m,n 不互素；mn=2030=600=23352。(m)=20(121)(151)=2252154=24=8(n)=30(121)(131)(151)=235213254=124=8(mn)=600(121)(131)(151)=23352213254=225124=160 则(mn)(m)(n)。(b)对于素数 pi，i 1,(pi)=pi(1p1)=pi-pi-1。3.38.试证：(a)ndd)(=n (b)

40、(mn)(h)=(m)(n)h，其中 m，nN，h=(m,n)(c)nN，h 3，(n)通常是偶数。证.(a)由于(n)=ndd)(dn (引理一)，根据 Mobius 反演，可得 n=ndd)(其中 f(dn)=dn，f(n)=n，g(d)=(d)，g(n)=(n)(b)由于(m,n)=h，故可设 m=11p22pkkp11q22qllq(其中：i1(0 i k)，j1(1 j l)n=11q22qllq11r22rttr(其中：j1(1 j l)，i1(0 s t)h=11q22qllq(其中：jminj,j (1 j l)(且诸 pi,qj,rs,等素数互不相同)于是(mn)(h)=mn

41、(111p)(121p)(1kp1)(111q)(121q)(1lq1)(111r)(121r)(1lr1)h(111q)(121q)(1lq1)=m(111p)(121p)(1kp1)(111q)(121q)(1lq1)n(111q)(121q)(1lq1)(111r)(121r)(1lr1)h=(m)(n)h。(c)由于 n3，故此在 n 的素数分解式：【第 30 页 共 42 页】n=11p22pkkp (其中：i1(1 i k)中，若 i)若至少有一奇素数因子，比如 0ip(1 i0 k)，从而 0ip1 是偶数，故此 (n)=n(111p)(121p)(1kp1)=11p22pkkp

42、(111p)(101ip)(1kp1)=11p00iipkkp(111p)(101ip)(1kp1)=11p00iipkkp111pp 001iipp kkpp1=111p100iip1kkp(p11)(0ip1)(pk1)含有偶数因子(0ip1)，故(n)是偶数。ii)否则，若 n 没有奇素数因子，故 n=2，由于 n 3，故 2，因此(n)=2(121)=221=2-1是偶数(因为1 1)。3.39.n 2，试证若 n 有 k 个不同的奇偶数因子，则(a)(n)n2-k(b)2k|(n)(c)(2n)=是偶数，是奇数，nnnn)(2)(。注.此题疑有误。没有条件中“奇偶数因子”这个概念，疑

43、是概念“奇质数因子”。证.(a)设 n 的素数分解式为：n=11p22pkkp (其中：pi为奇质(素)数 且 i1 (1 i k)对于任何 i，1 i k，由于 pi为奇质(素)数，故 pi 3，从而 ip121，于是有 1ip1121=21。所以(n)=n(111p)(121p)(1kp1)n212121=nk21=n2-k。(b)设 n 的素数分解式为：n=11p22pkkp (其中：pi为奇质(素)数 且 i1 (1 i k)【第 31 页 共 42 页】对于任何 i，1 i k，由于 pi为奇质(素)数，故 pi 3，从而iip 3，设 ni=iip，根据3.38.题(c)可知(ni

44、)是偶数，于是有 2|(ni)。又根据 3.37.题(a)可知(n)=(n1n2nk)=(n1)(n2)(nk)所以，2k|(n)。(c)若 n 是奇数，则 2 与 n 互素，即，(2,n)=1，故由(2)=1 及 3.37.题(a)可知(2n)=(2)(n)=(n)。若 n 是偶数，则 2 与 n 不互素，即，(2,n)=2，故由(2)=1 及 3.38.题(b)可知(2n)=(2n)(2)=(2)(n)2=2(n)。3.40.从集合=1,2,3,4,5,6,7,8,9,A,B,C,D,J,K,L,U,X,Y,Z 中随机抽取 28 次，求出现块CUBAJULY1987 的几率。解.3.41.

45、从 26 个英文字母中抽 35 次，求出现 MERRYCHRISTMAS 的几率。解.3.42.一组有 1990 个人，每人至少有 1327 位朋友，试证其中 4 位，使得彼此都是朋友。证.将 1990 个人看作 1990 个结点，若两个人彼此是朋友，则在表示他们的两个结点间连一条边，从而我们得到一个简单无向图G=(V,E)，并 且|V|=1990，deg(v)=1327(vV)。问题变为要证在图 G 中必存在一个完全子图 K4。在 图 G 中 任 取 一 结 点 aV，由 于deg(a)=1327，故从结点 a 可引出 1327 条边，并有 1327 个端点，在这 1327 个端点中任选一个

46、结点 b，则结点 a 和结点 b 显然相邻。设 A 是与结点 a 相邻的结点的集合，B 是与结点 b 相邻的结点的集合，则与结点 a 和结点 b 都相邻的结点的集合 AB 的大小|AB|=|A|+|B|-|AB|A|+|B|-|V|=1327+1327-1990=664 我们在 AB 的至少 664 个结点中任取一结点 c，则 a,b 和 c 三结点显然两两相邻。现在我们来证在 AB 中剩下的至少 663 个结点中一定存在一个结点 d，它与结点 c 相邻，从而 a,b,c 和 d 四结点显然两两相邻，故此 a,b,c 和 d 四结点就构成我们所要寻找的完全子图 K4。实际上，由于 deg(c)

47、=1327，故与结点 c 不相邻的结点个数仅为 1990-1327-1=662 个，因而在 AB 中剩下的至少 663 个结点中一定存在一个结点与 c 相邻，设此结点为 d，即为所求。3.44.单位圆周上任意 n+1 个不相同的点至少存在两点，其间距离不超过 2sinn。证.将单位圆周等分为n等份(每一等份圆弧及圆心角为n2，【第 32 页 共 42 页】半角为n)，因此，在单位圆周上的任意 n+1 个不相同的点，按鸽巢原理，至少存在两个不同的点，落入同一等份。而每一等份圆弧上任意两个点的距离不超过该弧所对的弦长，此弦长为：21sinn=2 sinn 故此，至少存在两点，其间距离不超过 2si

48、nn。3.45.边长为 1 的正方形内任取 9 点，试证存在 3 个不同的点，由此构成的三角形面积不超过81。证.将边长为 1 的正方形等分为 4 个小正方形(每一个小正方形的边长为21)，因此，在正方形内的任意 9 个点，按鸽巢原理二推论 3.8.1.，至少存在 419+1=3 个点，落入同一小正方形。而每一小正方形内任意 3 个点所构成的三角形面积不会超过该小正方形面积的一半，即 212121=81 故此，存在 3 个不同的点，由此构成的三角形面积不超过81。3.46.任给 5 个整数，试证必存在 3 个数的和被 3 除尽。证.任何整数被 3 除，可能的余数为：0,1,2。5 个数被 3

49、除，若余数为 0,1,2 的数各(至少)有一个，则此 3 个数的和就能被 3 除尽；若余数最多只有 0,1,2 中的两种，则根据鸽巢原理二(加强形式)推论 3.8.1.，至少存在着 215+1=3 个数，余数相同，则此 3 个数的和也能被 3 除尽。3.47.A 是 n+1 个数的集合，试证其中必存在两个数，它们的差被 n 除尽。证.设 A=a1,a2,an,an+1，并设 A 中 n+1 个数被 n 除的余数为：r1,r2,rn,rn+1。任何整数被 n 除，可能的余数为：0,1,2,n-1，因而按鸽巢原理，n+1 个数中必至少有 2 个数的余数相同，设 ai，aj是 n+1 个数中余数相同

50、的那两个数，则有 ai-aj的余数为 0，于是有 2(ai-aj)。即在 A 的 n+1 个数中，必存在两个数，它们的差能被 n 除尽。3.48.A=a1,a2,a2k+1，k1，ai是正整数，i=1,2,2k+1，试证 A 的任意排列：1ia,2ia,12 kia 恒有 )(121jikjaaj 为偶数。证.由于 A 中这 2k+1 个数都是正整数，而正整数可分为奇数和偶数两类。从而根据鸽巢原【第 33 页 共 42 页】理二(加强形式)推论 3.8.1.，至少存在着21)12(k+1=k+1 个数，属于同一类，即同为奇数或同为偶数。不妨设这 k+1 个数是1sa,2sa,1ksa，它们任意