组合数学引论课后答案(部分)

组合数学引论课后答案习题一任何一组人中都有两个人，它们在该组内认识的人数相等。1110n+1n1.14k(k=1,2,…，21)222b＋l lb bl=”。令证明 设伈2b＋l lb bl=”。令，叶＝1＋舫-n由于bi;:a=1(1冬ii])和bi+bi+1h:i+6 12(1i71)所以J冬 a1< a2<::·.. <a71 12x11=132考虑序列,,·宜，

77,a1+

，＂ 2十k,.,71＋k (补)它们的值都是I- 132+k之间整数。于k 所以132+k 希）的项数为习由鸽巢原理可知豐*)中a1,a2,···,

与,a1-1-k,ai +从··•a71+k之间必2项相，即存在1< i<j<

aj=a,+1则 k=a一”i=bi+l+心 ＋…＋bii1天到第j天这连续j-天中,.他刚好下了K盘棋。当k=22，，只 有两种情：(l) al,“2,嘈..7J,a1422,a,2<t22,嘈..鲁”“+ 22这I又项中有2项相等。此时由上面的讨论知结论成立，即他在连续若干夭恰好下22盘棋。(2)ai,a2,.···,a:r,a122,a222,···,a7122这154项中没2~。由于,

121+22<a2+22<u .7+2E154故只能有a1=12=2,吐 ＝2。这他从第1~22天的连续22天里也下棋22盘。1.151,2，…，2nn+11,2,…,20010016一个整除1,2,…,2001005210013（即两个坐标均为整数的点），中的三个点为顶点的三角形，其重心也是整点。9证明：一个有理数的十进制数展开式自某一位后必是循环的。证明：对任意的整数N，存在着N07（N=3,我们有3259=777;N=4,有41952=7700;N=5,有514=70;……）1512；11013；

mn11

mn个点，则其中必有两个点，该两点的距离至多为n；37601131,2,…,2nn+11出的数属于同一个鸽巢，即它们的最大公约数为11.16m,n习题二2证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。1n-1[1,n-2]，由鸽巢原理知，n-1n-22假设至少有两人谁都不认识，则认识的人数为0的至少有两人。11101010：0，1，…，9。现在112105坐标也是整数。证明：54：（奇数，偶数）；（奇数，奇数）；（数）；（偶数，奇数）222100证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。10010010010020证明：根据推论2.2.1，若将4*（20-1）+1=77个水果取出，必有20个相同种类的水果。n+22n整除。（2.1.3）2n2n：0，1，2，…，2n-2，2n-1n+2n+12nn+1{0},{1，2n-1},{2，2n-2},{3,2n-3},…，{n-1,n+1}，{n}。根据鸽巢原理，n+22nn+12nn-12n2n918003次。证明：设网站在9天中访问数分别为a1，a2，...，a9其中a1+a2+...+a9=1800，令a1+a2+a3=b1，a4+a5+a6=b2，a7+a8+a9=b3因为（b1+b2+b3）/3>=600由推论2.2.2知，b1，b2，b3中至少有一个数大于等于600。所以存在有连续的三天，访问量大于等于600次。541144证明：首先对一列而言，因为有5行，只有4只颜色选择，根据鸽巢原理，则必有两个单元格的5)2=10的位置组合共有10*4=40种情况。而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。m+)将一个矩形分成(m+1)行m 2 +1列的网格每个格子涂1种颜色有m种颜色可以选择，4色。证明：对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。m+)每列中两个单元格的不同位置组合有 2 种，这样一列中两个同色单元格的位置组合m+)共有 2 m种情况m+)现在有m 2 +1列，根据鸽巢原理，必有两列相同。证明结论成立。507524证明：令b1，b2，...，b50分别为这50天中他每天的实验数，并做部分和a1=b1，a2=b1+b2，。。a50=b1+b2+...+b50.由题，bi>=1(1<=i<=50)且a50<=75所以1<=a1<a2<a3<…<a50<=75 考虑数列a1，a2，...，a50，a1+24，a2+24，a50+24，它们都在1与75+24=99之间。由鸽巢原理知，其中必有两项相等。由（*）知，a1，a2，...，a50互不相等，从而a1+24，...a50+24也互不相等，所以一定存在1<=i<j<=50,使得aj=ai+24，即24=aj-ai=(b1+b2+b3+…+bi+…+bj)-(b1+b2+…+bi)=b

+b1i+1

+...+bj所以从第i+1天到第j天这连续j-i天中，她正好做了24次实验。S={1,3,5,…,59930010124。证明：将S划分为{1,3,5}，{7,9,11}……,{595,597,599}共100组，由鸽巢原理知任意选取101个数中必存在2个数来自同一组，即其差最多为4.证明：从1~200中任意选取70个数，总有两个数的差是4，5或970a1,a2,…,a70,a1+4,a2+4,…,a70+4,a1+9,a2+9,…,a70+9,取值范围209，共210个数2R(2,n)=n证明：要证R（2，n）= n，用红蓝两色涂色Kn的边。当n=2时，R(2,2)=2，因为不管用红还是蓝色都是完全二边形。n=kR(2,k)=k（没有一条红边，只有蓝边n=k+1，R（2，k+1）若无红边，要想有完全k+1边形，必得有k+1个点，即R（2，k+1）=k+1。证明成立。习题三1055排在下午面试，则有多少种不同的安排面试的顺序？555！所以有C5*5!*5! 10!，共14400种不同的安排方法。1040，那么最多能有多少个电话号码？解：由于数字不能重复，0-91010*9*8*7=504009*9*8*7=453618A,B,C6果是分成三个组（不可区别），6解：1)C6*C6*C6种18 12 62)C6*C6*C6/3!18 12 681454后排，求有多少种方法将学生安排在座位上？解：前排8个座位，5人固定，共C5*5!种方法；后排8个座位，4人固定，共C4*4!种方法；8 8前排和后排还剩7个座位，由剩下的5人挑选5个座位，共C5*5!种方法；则一共有7C5*C4*C5*5!*5!*4!种安排方法。8 8 726法？解：先排21个辅音字母，共有21！522P522故所求为2P522(插入法)66式？解：66!；66！；66666!*6!*2；再除以围圈重复得(6!*6!*2)/12=6!*5!或6566！（5！）。（圆排列可以通过线性排列来解决）15ABC解：1514！；AB2*14!/14=2*13!；AC2*14!/14=2*13!；A与BC同时相邻有2*13!/13=2*12!；AB、C14!-2*13!-2*13!+2*12!（用到了容斥原理3.8Ma,4b,5c}11-排列数？解：M的11排列=[M-{a}]的11排列+[M-{b}]的11排列+[M-{c}]的11排列，即11!

11!

11!=277202!4!5! 3!3!5! 3!4!4!当然了，容斥原理，生成函数也可以做。xx1 2

xx3

20x1

2,x2

0,x3

5,x4

1的整数解的个数。y1

x20,y1

x0,y2

x50,y3

x104yy1 2

yy3

14，由定理3.3.3，解个数为：14411717680 14 14 3204解：n=20，r=4，nr12041172380 r 4 4 证明见38页。若卷号差为2，3，。。。。。，公式为？确定(2-3)5展开式中4y和24的系数。解：1）x4yC4*(2x)4*(3y)1，系数为-24052）x2y40。确定(1+)-5展开式中4的系数。解：

nr1

，n=5，r=4

541(1x)n

(1)r

xr

(1)4 70r0

r 4 确定(x+2y3)8展开式中422的系数。解： 8!4!*2!*2!

*22*32151203.14nn1n2nknk1n,k为正整数。0 1 2 k k 解：右边nk1是（n+k+1）元集合S,a,...,a }上k个元素子集的个数，这些子集可k 1 k

nk1k+1

nk第1类：k元子集中不含a的子集有 个k 1

nk12k含aa的子集是

k11 2 nk2第3类：k元子集中含a和a，而不含a的子集是 1 2 3……

k2nk+1ka，aa

的子集是 1 2 k由加法原理得证。

k+1

0根据组合意义进行证明k k2 3.15k2，求1222n22 解：首先有：n1 n n1 0k

（p51的(3)） 1 k k k根据已知条件代入以上等式得：n n i i 1 1 2 2 n n2 1 2 1 2 1 2 i2 (2)22...22 1 2 1 2 1 2 i1 i1 2122...2n12...n2 2 2 1 1 1 2(12...n)12...n2 2 2 1 1 1 k k k k又由1k k k k 1 1 1 2 2 2 3得12n1 1 1 2 2 2 3 3 2 6 6 则原式2n1n12(n1)n(n1)n(n3 2 6 6 25:115有多少种可能的比分记录？解：根据题意，相当于求从点(0,0)到点(25,11)且不经过(5,5)的非降路径数，即为：25115525-511-5 361026

- 5

11-

11-56 11:7过，求有多少种可能的比分记录？解：根据题意，相当于求从点(0,0)到点(11,7)且从下方不穿过y=x的非降路径数，见58页，117111+1+7-2 11-1 11+1 202040（开始和结束时除外解：根据题意，相当于求从点(0,0)到点(20,20y=x2n2 2n2 22n2(n1 n )n1n n=20

38 3819 2( 19 3.19计算7和7。3 3 763652535353 2 3 2 2 3

1

解：1）155951542494342 3 1 2 2 3

619*727*6301n

n n22n11

2 n2 n

n12）766655565553 3 3 1 2 2 3 1115305111444304442 3 1 2 2 3

111(14*11)30(114*C2)154643.20（1）S(n,3)=33n个盒子为空的情况，即：一个盒子为空（放到两个盒子去），例如第一个盒子为空,第二和第三不空：3（2n-2）两个盒子为空，例如第一个和第二盒子为空：3*1（3n-3（2n-2）-3）/3!nn-212n-232使得一个盒子有3个球：C(n,3)有二个盒子都装2个球：C（n,4）C(4,2)/2!3.21（1）2n+13少种摆法？解：如果没有附加限制则相当于把2n个相同的小球放到3个不同的盒子里，有2n31 2n2

种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当于将2 n+1个座位先放到3排中的某一排，再将剩下的2n-(n+1)=n-1个座位任意分到3排中，这样2n(n1)31 n1的摆法共有3 2 3 2种方案，所以符合题意的摆法有： 2 22n23n 2 2 可以用代数法2n3摆法？习题四4.1在1到1000之间不能被2，5和11整除的整数有多少个？解：设S是这1000个数的集合，性质P是可被2整除，性质P是可被5整除，性质P是可11

1 2 3A{x|xSx具有性质P},(i1,2,3)i i|A|1000/2500，|A1

1000/5200，|A3

|90|AA1

1000/10100，|AA1

1000/2245，|AA2

1000/5518，|

AA2

|91A11

AA2 3

|1000(50020090)(1004518)93644.3A,B,C20A，16B，14%AABA,B,C解|AAA|1(20%16%14%)(8%5%4%)2%65%1 2 34.211000S1000性质P1

是某数的完全平方，性质P是某数的完全立方，2性质P是某数的完全四次方。A{x|xSx具有性质P},(i1,2,3)3 i i|A|100031，|A|3100010，|A|4100051

2

3 |AA

|610003，|A

410005，|

A|1210001，1 2

1 3

2 3 |AA1

A|1210001 |AA1 2

A|1000(31105)(351)196231005838521612解：由题意可得，P1,P2,P3100A20所以可得既喜欢看球赛有喜欢看电影的人有|AA1

(583852)100(1816)1226因此只喜欢看电影的人有A2A2A2A3A2=52-(26+16)+12=22人124328碰见任何一位朋友，问他共在外面吃过几次晚餐?C112C26C34C43C52C618366 6 6 6 6 64.6计算多重集S={4•a,3•b,4•c,6•d}的12-组合的个数？ 12 解：令T{a,b,c,d}的所有12组合构成W4121 12 其中 471 ， 481 ，|A|

|A|

1651 7 2 8 |A|471120，|A|45156，37 4 5 3 |AA

|43120，|A

|42110，|A

|4011， 1 2 3

1 3 2

1 4 0 |AA

43120|AA4114， |AA4011， 2 3 3

2 4 1

3 4 0 |AA1 2

A|03A1

AAA2 3 4

|455(12012016556)(20101204)504.7S={∞•a,4•b,5•c,6•d10解：将a，其他思想同上题。4101W 10

286451 441 431其中|A

|0

|

56|

|

35|

|

20，1 2 5

3 4

4 3 |AA1 2

0，|AA1

|0，|AA1

0，|A2

A|0，|AA3 2

0，|AA3

|0，|AA1

A|03|AA1 2

AA3

|286(563520)1754.8用容斥原理确定如下两个方程的整数解的个数。1）x+x+x=15x,xx7；1 2 3 1 2,32）x+x+x+x=20x,xxx9；1 2 3 4解：

1 2,3,41）xxx1 2 为282）

15 x1

7,0x2

7,0x3

7与{7a,7b,7c}的15组合数相等，xx1 2

xx3

20 x1

9,1x2

9,1x3

9,1x4

9，因此用y+1代替1xy+1xy+1xy+1x有1 2 2 3 3 4 4yy1 2

yy3

0y1

8,0y2

8,0y3

8,0y4

8与{8a,8b,8c,8d}的16组合数相等为4894.9D=1n!nDnDnDLnD012n100 012n10n

n证明考虑到n个数的全排列包含错位排列和非错排其中

表示在n个数中任选k个，k k这个k个数构成了一个错排，而剩余的n-k个数还在原来的位置。n n n n n nQ ，显然n!

... D0 n 0 （另一种方法：组合分析法）证明：D满足：n

1

2

n nD(n1)(D D

ｎ为整数且ｎ３n n1 n2D0,D11 2证明：由定理4.3.1得1 1 1Dn1

(n

...(1)n1 )1! 2! (n1)!1 1 (n1)!(1 ...(1)n21 1 1! 2! (n1 1 1

)(1)n1Dn2

(n

...(1)n2 )1! 2! (n2)!1 1 1Dn1

Dn2

(1 ...(1)n21 1 1! 2! (n1 1

)[(n2)!n](1)n1(n1)(Dn1

Dn2

)

...(1)n2 )(1)n1(n1)1! 2! (n2)!1 1 1 1 1(1 ...(1)n2 (1)n1 (1)n )1! 2! (n2)! (n1)! n!10不相同的，当宴会结束的离开的时候，如果帽子和雨伞都是随机的还回的，那么有多少种方法使得每位女士拿到的物品都不是自己的？解：由于帽子全部拿错和雨伞全部拿错是两个相互独立的事件，设帽子全错为D110!(11111111111)10 1! 2! 3! 4! 5! 6! 7! 8! 9! 10!D210

D1解10D D110 10

D210

10!10!e2)。R()。R( )=x*R(R( )=x*R()+R()=x*(1+3x+x2)+(1+x)*R()=x3+3x2+x+(1+x)[xR( )+R( )]=x3=x3+3x2+x+(1+x)[xR( )+R( )]=5x3+12x2+7x+1A不能涂成黑色；B型车不能涂成红色和白色；C型车不能涂成白色和绿色；D型车不能涂绿色和蓝色；E型号车不能涂成蓝色，求有多少种涂装方案？解：A B C D E红白蓝绿黑1.若未规定不同车型必须涂不同颜色，则：433342.若不同车型必须涂不同颜色，则：禁区的棋盘多项式为：1+8x+22x2+25x3+11x4+x5所以：5！-8*4！+22*3！-25*2！+11*1！-1=204.15计算(210),(105).（舍）4.16计算T={∞•1,∞•2,∞•3，∞•4}的长度为4的圆排列数。（舍）补：（1）1~20007610证明：A1,A2,A36、710A2A2A2A2(A3)A2(A2A1)(A2A3)A2A2A2(A2A1)(A2A3))=219=219(21~20002、35A2A22A2A3=534习题五求如下数列的生成函数。（1）a(1)k(k；（2）a(1)kk2k；k k（3）ak6； （4）ak(k2)；k knk nk k k 3（5）a ； （6）ak k k 3 解：（1）由已知得bk1kB(x) 1(1x)2A(x)

1(x1)21（2）设bk

(2)k则k

12x

2x又因为akb故G{a}x(G{b})1k k bkk或者 x

k (12x)2B(x)

(1x)2（3）}k}

6}

x 6 65xk k

(1x)2 1x (1x)2（4）}kk knk n1k1

x(3x)(1x)3a k（5） k

k （6）

}k

1(1x)n13a3k n4,4k1 3kb k k k 3k3 3 } x3k (1x)4求如下数列的指数生成函数。akak

(1)k；2kk!；ak

1 ；k1解：（）Ga}(

xke(x)e kk0（2）Ga}2kxk

k!2k} 1e kk0

k 12x(3)Ga}

1xkf(x)1e kk0

(1k)!xf(x)则 k

1xk1(1k)!

故G

ex1k0

1xk1ex1k!

e k x已知数列A(x)23x9x2，求a.k 13x k解：A(x)

213x

3xA(x)

213x

2k

3kxk23k ,k1故a k 9 ,k1求x4x8)100的系数是多少？(1)若x8取0，则x4取5个，这种情况有C5种；100(2)x81x43100x82x41100

C399C299

或C3100；

C1；97故系数为C5100

C1100

C399C1100

C299

=91457520。其他方法9？解：这相当于有9个球，用隔板将其分成3组，共有C228种方法。又因为这次点数小于等8于6，即711，171和117三种情况不符，故共有25种方法。(xx2x3x4x5x6)3(xx7)3

2kk(2)xk 1021045？解：(1)三位数时，相当于xxx1 2 3

5(1x1

5,0x2

5,0x3

5)的非负整数解的个数。故G(x)(xx2x3x4x5)g(1xx2x3x4x5)g(1xx2x3x4x5)中C5开式x5的系数。

为G(x)展(2)xx1 2

xx3

5(1x1

5,0x2

5,0x3

5,0x4

5)的非负整数解的个数。1×n的方格图形用红、蓝、绿和橙四种颜色涂色，如果有偶数个方格被涂成红色，还有偶数个方格被涂成绿色，求有多少种方案？解：涂色方案数为b则：kGb}(x2x4L)2(x2x3L)2(exex)2(ex)2e4x2e2x1e k 2!

2! 3! 2 414

k

4k2k1xk4 k!bk

4k12k1，所以有4n12n1种方案。4335解：设每次取出的k个球的排列数为b，数列{b}的指数型生成函数为G{b}则有k k e kG{b}(1xx2x3x4)g(1xx2x3)g(1xx2x3)而我们所求的是x5的系数b。故有e k 1! b220。5

3!

1! 2!

1! 2! 3!

5! 53A，3G，2C1U2RNA链的数量。x2 x2解：(1x )2x )(1x)中x2的系数C2 2 25.10 7和7。

，有C2

=15.3 37解：(1x(x1)(x2)(x3)(x4)(x5)(x6)则x3的系数b，则b

1524，故715243

3 3 37

n n n(2)3 nnn

11g22g33，nnn1 2 34

4的非负整数解为(0,0,4),(1,2,3),(0,2,2),123(0,3,1),(0,4,0),(1,0,3),(1,1,2),(1,2,1),(1,3,0),(2,0,2),(2,1,1),(2,2,0),(3,0,1),(3,1,0),(4,0,0)7322232412312g21g3112g2213g3113g2114301Bn

表示把n元集划分成非空子集的方法数，我们称Bn

Bell数。n n n

。n 2 n1b12b2

n，112n2Mkbk

n kMnbn

n n故B

当有n+1个盒子时，至少有一个空盒，不符。bnnnLn n i1

1 2 3 n1g1g32g44g2(1xx2x3x2x4x6x8x4x8中展开式有多少项1(1xx2x3x4x5x6x7x8x9x10x11)g(1x2x4x6x8)故共有19种重量。已知数列的指数生成函数是G(x)x25ex，求a.k e kf(x)x25ex解：设 x2 x3x25(1x ..)2! 3!a=5,k2ka=7,k=2k补：3个l，2个2，5个3这十个数字能构成多少个4位数偶数。解 问题是求多重集S＝{3个个个3}的4排列数且要求排列的末尾为偶数可以把问题转化成求多重集S＝{3个1，1个2，5个3}, x2 x3 x2 x3 x4 x5G(x)1x (1x)1x e 2! 3! 2! 3! 4! 5! 其指数生成函数为 L3!

3!

3!3!

3!

3!

3!x3L3! 1!2! 1!2! 3! 1!2! 1!1!1!2!1!3!L20x3L3!展开后得x3的系数为20，所以能组成20个4位数的偶数。3!习题六f(n22n2f(n的递推关系并求解。解：f(n)f(nn2, (n2)f(1)1齐次特征方程：x1特征根：x1非齐次特解：f*(n)(bbnbn2)n0 1 2代入递推关系得：1 1 1b ，b ，b0 6 1 2 2 31 1 f(n)( n n2)n1 1 6 2 3求解递推关系：f(n)7f(n1)12f(n2)0,(n2)（1）f(0)4,f(1)6;解：齐次特征方程：x27x120特征根：x1齐次通解：

4,x32f#(n)c4nc3n1 2代入递推关系得：c-6，c1

10f(n)64n103nf(n)f(n2)0,(n2)（2）f(0)0,f(1)2;解：x210x1i,x2if(n)5f(n1)6f(n2)4f(n3)8f(n4),(n4)（3）f(0)0,f(1)1,f(2)1,f(3)2,;解：nx4-x36x2x-80特征根：xx1 2n次通解：

x2,x3

-1f#(n)c2ncn2ncn22nc(1)n1 2 3 4代入n推n系得：8 7c ，c ，c-1，c-81272363244278 7 1 8 f(n) 2n n2n- n22n- 27 36 24 27f(n)3f(n1)2f(n2)1,(n2)（4）f(0)4,f(1)6;解：x23x20特征根：x1

x 12非齐次特解：f*(n)bn0代入递推关系得：b 0f#(n)c1

2nc n2c11 2 f(n)32n1n求解递推关系：f(n)4f(n1)4f(n2)3n1,(n2)（1）f(0)1,f(1)2;齐次特征方程：x24x40特征根：xx1 2

2,非齐次特解：f*(n)b0

bn1解：代入递推关系得：b13,b30 1f#(n)c2nc1 2

n2n3n13c12，c1

10 f(n)122n10n2n13f(n)6f(n1)9f(n2)2n,(n2)（2）f(0)1,f(1)0;解：齐次特征方程：x26x90特征根：xx1 2

3,非齐次特解：f*(n)b0

bn1代入递推关系得：b 12,b40 1f#(n)c1

3nc2

n3n4n12c11，c1

173 f(n)113n17n3n14n12f(n)4f(n1)32n,(n1)（3）f(0)1,齐次特征方程：x40特征根：x4,