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

【第 1 页 共 42 页】第三章3.12.一年级有 100 名学生参加中文，英语和数学的考试，其中 92 人通过中文考试，75 人通过英语考试，65 人通过数学考试；其中 65 人通过中，英文考试，54 人通过中文和数学考试，45 人通过英语和数学考试，试求通过 3 门学科考试的学生数。解.令：A 1=通过中文考试的学生A2=通过英语考试的学生A3=通过数学考试的学生于是 |Z| =100，|A 1|=92，|A 2|=75，|A 3|=65|A1 A2|=65，|A 1A 3|=54，|A 2A 3|=45此题没有给出：有多少人通过三门中至少一门； 有多少人一门都没通过。但是由 max |A1|,|A2|,|A3| =max92,75,65=92故可以认为：至少有 92 人通过三门中至少一门考试，即 100|A1A 2A 3|92至多有 8 人没通过一门考试，即 0| | 8123于是，根据容斥原理，有|A1A 2 A3|=(|A1|+|A2|+|A3|)-(|A1A2|+|A1A3|+|A2A3|)+|A1A2A3|即 |A 1A2A3|=|A1A 2A 3|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)=|A1A 2A 3|-(92+75+65)+(65+54+45)=|A1A 2A 3|-232+164=|A1A 2A 3|-68从而由 92-68|A 1A 2A 3|-68100-68即 24|A 1A 2A 3|-6832可得 24|A 1A2A3| 32故此，通过 3 门学科考试的学生数在 24 到 32 人之间。也可用容斥原理，即| |=|Z|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)-|A1A2A3|1A23=100-(92+75+65)+(65+54+45)-|A1A2A3|=100-232+164-|A1A2A3|【第 2 页 共 42 页】=32|A 1A2A3|从而有 |A 1A2A3|=32-| |A由已知 0| |8，可得12324|A1A2A3|32故此，通过 3 门学科考试的学生数在 24 到 32 之间。3.13.试证：(a)| B|=|B|-|AB|A(b)| C|=|C|-|AC|-|BC|+|(ABC)|B证.(a)B =BZ (因为 BZ)= B(A ) (零壹律:且有互补律 Z=A )A=(BA)(B ) (分配律 )A=(AB)( B) (交换律 )另外 (AB)( B)= (A )B (结合律，交换律，幂等律)=B (互补律 A =)A= (零壹律)所以 |B|=|AB|+| B|因此 | B|=|B|-|AB|A(b)| C|=| C| (de Morgan 律)B=|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,1000，求其中不被 5 和 7 除尽，但被 3 除尽的数的数目。解.定义： P 1(x):3|x A1=x|xNP1(x)【第 3 页 共 42 页】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因此 |A 1 |=|A1|-|A1A2|-|A1A3|+|A1A2A3|2=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|xNP 1(x)P2(x):3|x A2=x|xN P2(x) P3(x):5|x A3=x|xN P3(x) P4(x):7|x A4=x|xN P4(x)|A1|=120/2=60 |A2|=120/3=40 |A3|=120/5=24 |A4|=120/7=17 |A1 A2|=120/(23)=20 |A1A 3|=120/(25)=12 |A1A 4|=120/(27)=8|A2 A3|=120/(57)=8 |A2A 4|=120/(37)=5 |A3A 4|=120/(57)=3|A1A 2 A3|=120/(235)=4 |A1A 2A 4|=120/(237)=2|A1A 3 A4|=120/(257)=1 |A2A 3A 4|=120/(357)=1|A1 A2A 3A 4|=120/(2357)=0 |N|=120p0=|N|=120 【第 4 页 共 42 页】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+p4=120-141+56-8+0=27当 m=1 时，q 1=p1- p2+ p3- p4=141-256+38-40=53当 m=2 时，q 2= p2- p3+ p4=56-38+60=321当 m=3 时，q 3= p3- p4=8-40=8当 m=4 时，q 4= p4=0 由于 =11，所以不超过 120 的合数一定有不超过 10 的因子，因而一定有1202,3,5,7 的素因子(因为 10 以内的素数只用 2,3,5,7)，所以不超过 120 的素数一定是那些不能被 2,3,5,7 除尽的数( 当然还要去 掉非素数的数 1)，故此不超过 120 的素数的数目=q0-1=27-1=26 个。3.16.求正整数 n 的数目，n 除尽 1040,2030 中的至少一个数。解. 定义：P 1(x):x|1040 A1=x|xNP 1(x)P2(x):x|2030 A2=x|xNP 2(x)由于 10 40=(25)40=240540 2030=(225)30=260530故此 |A 1|=(40+1)(40+1)=1681|A2|=(60+1)(30+1)=1891 (参见第一章第九题)|A1A2|=(40+1)(30+1)=1271于是 |A 1A 2|=|A1|+|A2|-|A1 A2|=1681+1891-1271=2301因此，能至少除尽 1040 和 2030 之一的正整数的数目是 2301 。3.17.n 是除尽 1060,2050,3040 中至少一个数的除数，求 n 的数目。【第 5 页 共 42 页】解. 定义： P 1(x):x|1060 A1=x|xNP 1(x) P2(x):x|2050 A2=x|xNP 2(x) P3(x):x|3040 A3=x|xNP 3(x)由于 10 60=(25)60=260560 2050=(225)50=2100550 3040=(235)40=240340540故此： |A 1|=(60+1)(60+1)=3721|A2|=(100+1)(50+1)=5151|A3|=(40+1)(40+1)(40+1)=68921|A1A2|=(60+1)(50+1)=3111|A1A3|=(40+1)(40+1)=1681|A2A3|=(40+1)(40+1)=1681|A1A2A3|=(40+1)(40+1)=1681根据容斥原理，有|A1A 2 A3|=(|A1|+|A2|+|A3|)- (|A1A2|+|A1A3|+|A2A3|)+|A1A2A3|=(3721+5151+68921)-(3111+1681+1681)+1681=73001所以，至少能整除 1060,2050,3040 之一的正整数 n 有 73001 个 。3.18 求下列集合中不是 ， 形式的数的数目， nN 。2n3（a）1，2， （=N1）410（b） ， +1， （=N2）3104【解】：（a）定义：P1（x）:x= （nN） A1=x|xN1P1(x)2nP2（x）:x= （nN） A1=x|xN2P2(x)3A1= ， ， 故|A1|= =100212)10(N210【第 6 页 共 42 页】A2= ， ， 故|A2|=2131231N（因为 =9261 10648= ）34032A1A2= ， ， ， ，故|A1 A2|=461261N（因为 =4096 15625= ）644065因此，根据容斥原理，有| |=|N1|-（|A1|+|A2|）+|A1A2|1A2= （100+21）+4 =988340（b）定义：P1（x）:x= （nN） A1=x|xN1P1(x)2nP2（x）:x= （nN） A1=x|xN2P2(x)3A1= ， 故|A1|=100-30=70212)10(N（因为 =961 1024= ）2332A2= ， 故|A2|=21-9=121031NA1A2= 故|A1 A2|=1642（因为 =729 =40966331064因此，根据容斥原理，有| |=|N1|-（|A1|+|A2|）+|A1A2|1A2= 9001（70+12）+1【第 7 页 共 42 页】= 89203.19 1000，1001，3000，求其中是 4 的倍数但不是 100 的倍数的数的数目。【解】： 令 N1=1000，1001，3000，则 |N1|=2001P1（x）:4|x A1=x|xN1P1(x)P1（x）:100|x A1=x|xN2P2(x)于是由 A1=4250，4251，4750 N1，故 |A1|=750250+1=501，A1A2=10010，10011，10030 N1，故 |A1A2|=3010+1=21因此 |A1 |=|A1|A1A2|=50 121=4802A所以，10003000 中只能被 4 整除，但不能被 100 整除的数有 480 个。3.20 在由 a,a,a,b,b,b,c,c,c 组成的排列中，求满足下列条件的排列数，（a）不存在相邻 3 元素相同（b）相邻两元素不相同【解】：（a）定义：Z=9 个元素的全排列，|Z|= =1680！ ！ 39P1(x)：排列 x 中有相邻三元素相同，且是 aP2(x)：排列 x 中有相邻三元素相同，且是 bP3(x)：排列 x 中有相邻三元素相同，且是 cA1=x |xZP1(x) |A1 |= =140!37A2=x |xZP2(x) |A2 |= =140!A3=x |xZP3(x) |A3 |= =140!3【第 8 页 共 42 页】|A1A2|= =20 |A1A3|= =20!35!35|A2A3|= =20 |A1A2A3|=3！=6!于是，根据容斥原理，有| |=|Z|（|A1|+|A2|+|A3| ）1A23+（|A1A2|+|A1A3|+|A2A3|）|A1A2A3|=168031403206=1314（b）定义：Z=9 个元素的全排列，|Z|= =1680！ ！ 39P1(x)：排列 x 中有相邻两个元素相同，且是 aP2(x)：排列 x 中有相邻两个元素相同，且是 bP3(x)：排列 x 中有相邻两个元素相同，且是 c=x|xZ (x) (1i3)iAiP|A1|= =1120140=980!387(因为将 aa 与 a 看做为不同的两个元素参与排列，在它们相遇之时会产生重复，其重复因子刚好是将 aaa 看作一个整体参与排列的个数)同理可得：|A2|= =1120140=980!387|A3|= =1120140=980!因为 A1A2 为 aa,bb 图象都出现的排列集合，当我们将 aa 与 a,bb 与 b 看作不同的两对元素进行排列时，在 aa 与 a 相遇而成 aaa 图象及 bb 与 b 相遇而成 bbb 图象时会产生重复计数。当 aaa 图象与 bbb 图象恰出现一个时，重复因子为 2；当图象 aaa 与图象 bbb同时出现时，重复因子为 4 。【第 9 页 共 42 页】设 q1(x)：排列 x 中 aa 与 a 相遇而有 aaa 图象q2(x)：排列 x 中 bb 与 b 相遇而有 bbb 图象故 B1=x |xA1A2q1(x) B2=x |xA1A2q2(x)于是 |B1| = |B2| = =120 |B1B2| = =20!36!35P1 = |B1| + |B2| =2120 =240 P2 = |B1B2 |=20q1=P12P2 =240220=200 q2=P2=20从而 |A1A2| = （q1+3q2）=840(200+320)=580!37同理，|A1A3 | =580 |A2A3 |=580因为 A1A2A3 为 aa，bb，cc 图象出现的排列集合，当我们将 aa 与 a，bb与 b，cc 与 c 看作不同的三对元素进行排列时，在 aa 与 a 相遇而成 aaa 图象，bb 与 b 相遇而成 bbb 图象，cc 与 c 相遇而成 ccc 图象时会产生重复计数。当 aaa，bbb，ccc 图象恰出现一个时，重复因子为 2当 aaa，bbb，ccc 图象恰出现两个时，重复因子为 4当 aaa，bbb，ccc 图象恰同时出现时，重复因子为 8设 q1(x)；排列 x 中有 aaa 图象q2(x)；排