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

第三章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,6592故可以认为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|-927565655445|A1A2A3|-232164|A1A2A3|-68从而由 92-68|A1A2A3|-68100-68即 24|A1A2A3|-6832可得 24|A1A2A3| 32故此，通过3门学科考试的学生数在24到32人之间。也可用容斥原理，即 |||Z|-|A1||A2||A3||A1A2||A1A3||A2A3|-|A1A2A3|100-927565655445-|A1A2A3|100-232164-|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|证.aB BZ 因为BZ BA 零壹律且有互补律ZA BAB 分配律 ABB 交换律另外 ABB AB 结合律，交换律，幂等律 B 互补律A 零壹律所以 |B||AB||B|因此 |B||B|-|AB|b|C||C| de Morgan律 |C|-|ABC| 根据a，令A1AB |C|-|ACBC| 分配律 |C|-|AC||BC|-|ACBC| |C|-|AC|-|BC||ACBC| |C|-|AC|-|BC||ABC| 结合律，交换律，幂等律3.14. N1,2,,1000，求其中不被5和7除尽，但被3除尽的数的数目。解.定义 P1x3|x A1x|xNP1xP2x5|x A2x|xNP2xP3x7|x A3x|xNP3x|A1| 1000/3333 |A1A2|1000/3566|A1A3|1000/3747 |A1A2A3|1000/3579因此 |A1||A1|-|A1A2|-|A1A3||A1A2A3| 333-66-479229因此 ，在11000中能被3整除，同时不能被5和7整除的数有229个。3.15. N1,2,,120，求其中被2,3,5,7,m个数除尽的数的数目，m0,1,2,3,4 。求不超过120的素数的数目。解.定义 P1x2|x A1x|xNP1xP2x3|x A2x|xNP2x P3x5|x A3x|xNP3x P4x7|x A4x|xNP4x|A1|120/260 |A2|120/340 |A3|120/524 |A4|120/717 |A1A2|120/2320 |A1A3|120/2512 |A1A4|120/278|A2A3|120/578 |A2A4|120/375 |A3A4|120/573 |A1A2A3|120/2354 |A1A2A4|120/2372 |A1A3A4|120/2571 |A2A3A4|120/3571|A1A2A3A4|120/23570 |N|120 p0|N|120 p1|A1||A2||A3||A4|60402417141p2|A1A2||A1A3||A1A4||A2A3||A2A4||A3A4|2012885356p3|A1A2A3||A1A2A4||A1A3A4||A2A3A4|42118p4|A1A2A3A4|0 当m0时，q0p0-p1p2-p3p4120-14156-8027当m1时，q1p1-p2p3-p4141-25638-4053当m2时，q2 p2-p3p456-386032当m3时，q3 p3-p48-408当m4时，q4 p40 由于11，所以不超过120的合数一定有不超过10的因子，因而一定有2,3,5,7的素因子因为10以内的素数只用2,3,5,7，所以不超过120的素数一定是那些不能被2,3,5,7除尽的数当然还要去掉非素数的数1，故此不超过120的素数的数目q0-127-126个。3.16.求正整数n的数目，n除尽1040,2030中的至少一个数。解. 定义P1xx|1040 A1x|xNP1xP2xx|2030 A2x|xNP2x由于 10402540240540 203022530260530故此 |A1|4014011681|A2|6013011891 参见第一章第九题 |A1A2|4013011271于是 |A1A2||A1||A2|-|A1A2|16811891-12712301因此，能至少除尽1040和2030之一的正整数的数目是2301 。3.17.n是除尽1060,2050,3040中至少一个数的除数，求n的数目。解. 定义 P1xx|1060 A1x|xNP1x P2xx|2050 A2x|xNP2x P3xx|3040 A3x|xNP3x由于 10602560260560 2050225502100550 304023540240340540故此 |A1|6016013721 |A2|10015015151 |A3|40140140168921 |A1A2|6015013111 |A1A3|4014011681 |A2A3|4014011681 |A1A2A3|4014011681根据容斥原理，有 |A1A2A3||A1||A2||A3|- |A1A2||A1A3||A2A3||A1A2A3| 3721515168921-3111168116811681 73001所以，至少能整除1060,2050,3040之一的正整数n有73001个 。3.18 求下列集合中不是，形式的数的数目，nN 。 （a）1，2，， （N1） （b），1，， （N2）【解】（a）定义P1（x）x（nN） A1x|xN1P1x P2（x）x（nN） A1x|xN2P2xA1，，， 故|A1|100A2，，， 故|A2|21（因为926110648）A1A2，，，，故|A1A2|4（因为409615625）因此，根据容斥原理，有|||N1|-（|A1||A2|）|A1A2| （10021）4 9883（b）定义P1（x）x（nN） A1x|xN1P1x P2（x）x（nN） A1x|xN2P2x A1，， 故|A1|100-3070 （因为9611024） A2，， 故|A2|21-912A1A2 故|A1A2|1 （因为7294096因此，根据容斥原理，有|||N1|-（|A1||A2|）|A1A2| 9001（7012）1 89203.19 1000，1001，，3000，求其中是4的倍数但不是100的倍数的数的数目。【解】 令N11000，1001，，3000，则 |N1|2001 P1（x）4|x A1x|xN1P1x P1（x）100|x A1x|xN2P2x 于是由 A14250，4251，，4750N1，故 |A1|7502501501， A1A210010，10011，，10030N1，故 |A1A2|3010121因此 |A1||A1||A1A2|50121480所以，10003000中只能被4整除，但不能被100整除的数有480个。3.20 在由a,a,a,b,b,b,c,c,c组成的排列中，求满足下列条件的排列数，（a）不存在相邻3元素相同（b）相邻两元素不相同【解】（a）定义Z9个元素的全排列，|Z|1680 P1x排列x 中有相邻三元素相同，且是a P2x排列x 中有相邻三元素相同，且是b P3x排列x 中有相邻三元素相同，且是c A1x |xZP1x |A1 |140 A2x |xZP2x |A2 |140 A3x |xZP3x |A3 |140 |A1A2|20 |A1A3|20 |A2A3|20 |A1A2A3|36 于是，根据容斥原理，有 |||Z|（|A1||A2||A3|）（|A1A2||A1A3||A2A3|） |A1A2A3| 1680314032061314（b）定义Z9个元素的全排列，|Z|1680 P1x排列x 中有相邻两个元素相同，且是a P2x排列x 中有相邻两个元素相同，且是bP3x排列x 中有相邻两个元素相同，且是cx|xZx 1i3|A1|1120140980因为将aa与a看做为不同的两个元素参与排列，在它们相遇之时会产生重复，其重复因子刚好是将aaa看作一个整体参与排列的个数同理可得|A2|1120140980 |A3|1120140980 因为A1A2为aa,bb图象都出现的排列集合，当我们将aa与a,bb与b看作不同的两对元素进行排列时，在aa与a相遇而成aaa图象及bb与b相遇而成bbb图象时会产生重复计数。当aaa图象与bbb图象恰出现一个时，重复因子为2；当图象aaa与图象bbb同时出现时，重复因子为4 。 设 q1x排列x 中aa与a相遇而有aaa图象 q2x排列x 中bb与b相遇而有bbb图象 故 B1x |xA1A2q1x B2x |xA1A2q2x于是 |B1| |B2| 120 |B1B2| 20 P1 |B1| |B2| 2120 240 P2 |B1B2 |20 q1P12P2 240220200 q2P220从而 |A1A2| （q13q2）840200320580同理，|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设 q1x；排列x中有aaa图象 q2x；排列x中有bbb图象 q3x；排列x中有ccc图象 x |xA1A2A3x 1i3 |B1| |B2||B3|5 |B1B2||B1B3||B2B3|424 |B1B2B3|36 P1|B1||B2||B3|3120360 P2|B1B2||B1B3||B2B3|32472 P3|B1B2B3|6 q1P12P23P336027236234 q2P23P3723654 q3P36因此 |A1A2A3| 6（q13q27q3）72023435476282所以 || |Z|-（|A1||A2||A3|）（|A1A2||A1A3||A2A3|） |A1A2A3| 168039803580282198即 相邻两元素不相同的排列数为1983.21 求出O（0，0）点到（8，4）点的路径数，已知（2，1）到（4，1）的线路，（3，1）到（3，2）的线路被封锁。【解】令P（8，4），A（2，1），B（4，1），C（3，1），D（3，2） P1（x）线段AB在从O到P的路径X上 P2（x）线段CD在从O到P的路径X上 x|xZ 1i2 Z从O到P的路径 |Z|495 |A1| 3105 |A2| 484 |A1A2| 0 故此 || |Z|（|A1||A2|）|A1A2|495（10584）0306 因此，从O到P的路，不过线段AB和CD的有306条。j3.22.求满足条件x1x2x3203 x19，0 x28，7 x317的整数解的数目。解.方法一利用容斥原理二不定方程j与如下的不定方程k等价kx1x2x3100 x16，0 x28，0 x310这可通过作变换来实现。对应于不定方程k的不受限的不定方程为lx1x2x310 x10，x20，x30设Xx|xx1,x2 ,x3是不定方程l的解;A1 x|xx1,x2 ,x3 是不定方程l的解且x1617;A2 x|xx1,x2 ,x3 是不定方程l的解且x2819;A3 x|xx1,x2 ,x3 是不定方程l的解且x310111;因此,根据定理3.6.4.可知，不定方程l的解的数目p0|X|66A1对应的不定方程是mx1x2x310 x17，x20，x30令 x10, x20, x30。利用m我们得到x1x2 x3 x1-7 x2 x3 x1x2x3-710-73所以不定方程m的解与下列不定方程mx1x2 x33x10, x20, x30的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为|A1|10同理可得|A2|3A3对应的不定方程是nx1x2x310 x10，x20，x311由于解若满足条件x10，x20，x311，则有 x1x2x300111110故不定方程n没有解，即|A2|0因此p1|A1||A2||A3|103013A1A2对应的不定方程是ox1x2x310 x17，x29，x30由于解若满足条件x17，x29，x30，则有 x1x2x37901610故不定方程o没有解，即|A1A2|0同理可得|A1A3|0，|A2A3|0因此p2|A1A2||A1A3||A2A3|0000A1A2A3对应的不定方程是px1x2x310 x17，x29，x311由于解若满足条件x17，x29，x311，则有 x1x2x379112710故不定方程p没有解，即p3| A1A2A3|0所以，不定方程k、也即不定方程j的解的数目为q0|| p0-p1 p2- p366-130-053 。方法二利用母函数方法不定方程j对应的母函数是1xx2x3x4x5x61xx2x3x4x5x6x7x81xx2x3x4x5x6x7x8x9x1012x3x24x35x46x57x67x77x86x95x104x113x122x13x14 1xx2x3x4x5x6x7x8x9x10不定方程j的解的数目为上述母函数中x10的系数11213141516171717161511234567776553 。3.23.求满足下列条件jx1x2x3406 x115，5 x220，10 x325的整数解的数目。解.仿3.22题方法一.利用容斥原理二，不定方程j与如下的不定方程k等价kx1x2x3190 x1 9，0 x2 15，0 x3 15这可通过作变换来实现。对应于不定方程k的不受限的不定方程为lx1x2x319x10，x20，x30设Xx|xx1,x2 ,x3是不定方程l的解;A1 x|xx1,x2 ,x3 是不定方程l的解且x19110;A2 x|xx1,x2 ,x3 是不定方程l的解且x215116;A3 x|xx1,x2 ,x3 是不定方程l的解且x315116;因此,根据定理3.6.4.可知，不定方程l的解的数目p0|X|210A1对应的不定方程是x1x2x319x110，x20，x30令 x10, x20, x30。利用m我们得到x1x2 x3 x1-10 x2 x3 x1x2x3-1019-109所以不定方程m的解与下列不定方程x1x2 x39x10, x20, x30的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为|A1|55同理可得|A2|10|A3|10因此p1|A1||A2||A3|55101075A1A2对应的不定方程是x1x2x319x110，x216，x30由于解若满足条件x110，x216，x30，则有x1x2x3101602619故不定方程n没有解，即|A1A2|0同理可得|A1A3|0，|A2A3|0因此p2|A1A2||A1A3||A2A3|0000A1A2A3对应的不定方程是x1x2x319x110，x216，x316由于解若满足条件x110，x216，x316，则有 x1x2x31016164219故不定方程o没有解，即p3| A1A2A3|0所以，不定方程k、也即不定方程j的解的数目为q0|| p0-p1 p2- p3210-750-0135 。方法二利用母函数方法不定方程k对应的母函数是1xx2x3x4x5x6x7x8x9 1xx2x3x4x5x6x7x8x9x10x11x12x13x14x1521-x10-2x162x26x32-x42参见第三版习题2.16P199或第二版第二章习题7P131不定方程j的解的数目为上述母函数中x19的系数1-1-2--2210-55-20135 。3.24.求满足下列条件的整数解的数目x1x2x3x4201 x15，0 x27，4 x38，2 x46。解.仿题3.22方法一利用容斥原理二，不定方程j与如下的不定方程k等价x1x2x3x4130 x14，0 x27，0 x34，0 x44这可通过作变换来实现。对应于不定方程k的不受限的不定方程为x1x2x3x413x10，x20，x30，x40设Xx|xx1,x2 ,x3,x4是不定方程l的解;A1 x| xx1,x2 ,x3,x4是不定方程l的解且x1415;A2 x| xx1,x2 ,x3,x4是不定方程l的解且x2718;A3 x| xx1,x2 ,x3,x4是不定方程l的解且x3415;A4 x| xx1,x2 ,x3,x4是不定方程l的解且x4415;因此,根据定理3.6.4.可知，不定方程l的解的数目p0|X|560A1对应的不定方程是x1x2x3x413x15，x20，x30，x40令 x10, x20, x30, x40。利用m我们得到x1x2 x3x4 x1-5 x2 x3x4 x1x2x3x4-513-58所以不定方程m的解与下列不定方程x1x2x3x48x10, x20, x30, x40的解一一对应。故根据定理3.6.4.可知，不定方程m的解的数目为|A1|165同理可得|A2|56|A3|165|A4|165因此 p1|A1||A2||A3||A4|16556165165551A1A2对应的不定方程是x1x2x3x413x15，x28，x30，x40令 x10, x20, x30, x40。利用n我们得到x1x2x3x4x1-5x2-8 x3x4 x1x2x3x4-5813-130所以不定方程n的解与下列不定方程x1x2x3x40 x10, 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|12020112063A1A2A3对应的不定方程是x1x2x3x413x15，x28，x35，x40由于解若满足条件x15，x28，x35，x40，则有 x1x2x3x458501813故不定方程o没有解，即 |A1A2A3| 0同理可得|A1A2A4| 0，|A1A3A4| 0，|A2A3A4| 0p3|A1A2A3||A1A2A4||A1A3A4||A2A3A4| 0000 0A1A2A3A4对应的不定方程是x1x2x3x413x15，x28，x35，x45由于解若满足条件x15，x28，x35，x40，则有 x1x2x3x458552313故不定方程p没有解，即p4| A1A2A3A4|0所以，不定方程k、也即不定方程j的解的数目为q0|| p0p1p2p3p4560551630072。方法二.利用母函数方法,不定方程k对应的母函数是1xx2x3x4x5x6x71xx2x3x431-3x5-x83x103x13-x15-3x18x23参见第三版习题2.16P199或第二版第二章习题7P131不定方程j的解的数目为上述母函数中x13的系数1-3-133-3-331560-495-5660372 。3.25.试证满足下列条件x1x2xnr0 xi k，i1,2,,n的整数解的数目为。证.方法一.利用容斥原理二，取不定方程 x1x2xnrxi0，i1,2,，n设Xx|xx1,x2,,xn是不定方程k的解 令Pix xx1,x2,,xn是不定方程k的解且满足条件xik1 i1,2,,nAix| xXPix i1,2,,n因此,根据定理3.6.4.可知，不定方程k的解的数目为p0|X|并且，参考第三版P238 第3.9节的方法一，做相应的变换，可得| Ai | 1 i np1| Ai | | AiAj | 1 i j np2| AiAj || AiAjAk| 1 i j k np3| AiAjAk|pn|A1A2An|于是，根据容斥原理二，可知q0||p0p1 p2p3 pn即不定方程j的整数解的数目为 。方法二.利用母函数方法，不定方程j对应的母函数是1xx2xkn-xk1x2k1-1nxnk1-xx2xn参见第三版习题2.16P199或第二版第二章习题7P131不定方程j的解的数目为上述母函数中xr的系数。3.26.试证满足下列条件x1x2xnr1 xi k，i1,2,,n的整数解的数目为。证.方法一.利用习题3.25的结论，对不定方程j做变换 于是 则不定方程j转化为题3.25型的不定方程x1x2xnrn0 x1 k1, 0 x2 k1,, 0 xn k1不定方程j与不定方程k的解是一一对应的，故不定方程k的整数解的数目就是不定方程j的整数解的数目。因此,不定方程j的整数解的数目,也即不定方程k的整数解的数目按题3.25为。方法二.利用母函数方法，不定方程k对应的母函数是1xx2xk-1n xkx2k-1nxnkxx2xn参见第三版习题2.16P199或第二版第二章习题7P131不定方程j的解的数目为上述母函数中xr-n的系数 。3.27.求n对夫妻排成一列，夫妻不相邻的排列数。解.n对夫妻有n个男人，n个女人，总计2n个人。设 Z xx是2n个人的一个排列于是显然有 |Z| 2n。定义Pix在排列x中第i对夫妻相邻 1 i nAi x | x Z Pix 1 i n于是 | Ai | 22n-1 第i对夫妻看作一个整体参加排列，排列数为2n-1，但这对夫妻内部有男女，女男两种排列 | AiAj | 222n-2 第i对，第j对夫妻看作2个人参加排列，排列数2n-2，但i ,j 每对夫妻内部有2种排列 | AiAjAk| 232n-3 第i,j,k对夫妻看作3个人参加排列，排列数2n-3，但i,j,k每对夫妻内部有2种排列 |A1A2An |2nn n对夫妻看作n个人参加排列，有n种排列，而每对夫妻内部有2种排列于是根据容斥原理二，有n对夫妻排成一列，夫妻不相邻的排列数为|| |Z|| Ai || AiAj ||AiAjAk|-1n| A1A2An | 2n22n1222n2232n3-1n2n n 2i2ni 。3.28 设p,qN,p是奇数，现有pq个珠子，着8q种颜色，每种颜色有p个珠子，假定相同颜色的珠子无区别。试分别求满足下列条件的珠子个排列数。（a）同颜色的珠子在一起（b）同颜色的珠子处于不同的块（c）同颜色的珠子最多在两个块证.（a）同颜色的p个珠子在一起，看作一个珠子，故q种颜色的珠子看作q个不同的珠子参加排列，其排列数为q ，故同颜色的珠子在一起有q种排列。（b）同颜色的珠子处于不同的块，同颜色的珠子有p个，3.29.将r个相同的球放进n个有标志的盒子，无一空盒，求方案数。解.方法一隔墙法.将r个相同的球放进n个有标志的盒子，无一空盒的放球方案相当于将r个相同的球排成一列，只有一种排法，形成r1个空隙，将n个不相同的盒子的n1个内档插入这r1个空隙中，有种插法。故放球方案数为。 方法二归约法.将r个相同的球放进n个有标志的盒子，无一会空的方案，相当于先将n个球放入n个不相同的盒