组合数学课后答案

1、精品文档作业习题答案习题二2.1 证明：在一个至少有2 人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为1,n-1，由鸽巢原理知，n 个人认识的人数有n-1 种，那么至少有2 个人认识的人数相同。假设有 1 人谁都不认识： 那么其他n-1 人认识的人数都为1,n-2，由鸽巢原理知， n-1个人认识的人数有n-2 种，那么至少有2 个人认识的人数相同。2.3 证明： 平面上任取5 个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：方法一：有 5 个坐标， 每个坐标只有 4 种可能的情况：（奇数， 偶数）；（奇

2、数， 奇数）；（偶数， 偶数）；（偶数，奇数） 。由鸽巢原理知，至少有 2 个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数 +奇数 =偶数； 偶数 +偶数 =偶数。因此只需找以上2 个情况相同的点。而已证明：存在至少2 个坐标的情况相同。证明成立。方法二：对于平面上的任意整数坐标的点而言，其坐标值对2 取模后的可能取值只有4 种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5 个点中必有2 个点的坐标对2 取模后是相同类型的，那么这两点的连线中点也必为整数。2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”

3、和“待定” ，至少有多少人参加才能保证必有100 个人得到相同的结果？证明：根据推论2.2.1 ，若将 3*（ 100-1 ）+1=298 个人得到3 种结果， 必有 100 人得到相同结果。m12.9 将一个矩形分成 ( m+1) 行 m1列的网格每个格子涂1 种颜色，有 m种颜色可以2选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4 个角上的格子被涂上同一种颜色。证明：（ 1）对每一列而言，有（ m+1）行， m种颜色，有鸽巢原理，则必有两个单元格颜色相同。（ 2）每列中两个单元格的不同位置组合有m 1种，这样一列中两个同色单元格的位2m1置组合共有m 种情况2。1欢迎下载精品文

4、档m1（ 3）现在有 m21列，根据鸽巢原理，必有两列相同。证明结论成立。2.11 证明：从 S=1,3,5,599 这 300个奇数中任意选取101 个数，在所选出的数中一定存在 2 个数，它们之间最多差 4。证明：将 S划分为 1,3,5， 7,9,11,595,597,599 共 100组，由鸽巢原理知任意选取 101个数中必存在2个数来自同一组，即其差最多为4.2.12 证明：从 1200 中任意选取70 个数，总有两个数的差是4，5 或 9。设从 1200 中任意选取的70 个数构成一组，即第一组：a1 , a2 ,K, a70 ；第二组：a14, a24,K, a704 ；第三组：

5、 a19, a29,K , a709 ；显然，这三组数均在 1209 之间，且共有 3*70=210 个数，根据鸽巢原理一定有两个数相等，又因为任取的这 70 个数均不相同，所以这 2 个相等的数一定来自不同组，根据不同组的分布讨论如下：1） 如果这两个数分别来自第一组和第二组，则有a jai4 ；2） 如果这两个数分别来自第一组和第三组，则有a jai9 ；3） 如果这两个数分别来自第二组和第三组，则有a jai5 ；得证。习题三3.8 确定多重集M3 a,4 b,5 c 的 11- 排列数？11!11!11!277203!4!4!3!3!5!2!4!5!3.9 求方程 x1x2x3x420

6、 ，满足 x12, x20, x35, x41的整数解的个数。144168033.10架上有 20 卷百科全书，从中选出4 卷使得任意两本的卷号都不相邻的选法有多少种？。2欢迎下载精品文档解： n=20， r=4 ，nr 1204117r4238043.17一局乒乓球比赛中，运动员甲以11:7战胜运动员乙，若在比赛过程中甲从来没有落后过，求有多少种可能的比分记录？解：根据题意，相当于求从点(0,0)到点 (11,7)且从下方不穿过y=x 的非降路径数，即为：11711171(117)!(117 1) 1326010-12(111)!7!3.211) 会议室中有2n+1 个座位，现摆成3 排，要

7、求任意两排的座位都占大多数，求有多少种摆法？解：(1)方法 1：如果没有附加限制则相当于把2n+1 个相同的小球放到3 个不同的盒子里，有2n1312n3n+1 个座位。这相3-12种方案， 而不符合题意的摆法是有一排至少有当于将 n+1 个座位先放到3 排中的某一排， 再将剩下的2n+1-(n+1)=n个座位任意分到 3 排32n1(n 1) 3 1n 2中，这样的摆法共有3种方案， 所以符合题意的摆法22有：2n3n2n12322方法 2：设第一排座位有x1 个，第二排座位有x2 个，第三排座位有x3 个。x1+x2+x3=2n+1，且 x1+x2(2n+1)/2 ，x1+x3 (2n+1

8、)/2 ，x2 +x3(2n+1)/2 ，即 x1+x2n+1，x1+x3n+1，x2+x3n+1，令 y= x +x-n-1，y = x+x -n-1，y = x +x-n-1，可知 y +y +y =2(2n+1)-3(n+1)=n-1且 y0，112213323123i1i 3。显然， x 方程满足要求的解与y 方程非负整数解一一对应，有n131n1312种。方法 3：要求每行非空如果没有附加限制则相当于把2n+1 个相同的小球放到3 个不同的盒子里， 不允许为空，2n112nn+1 个座位。 这相当于有3-1种方案， 而不符合题意的摆法是有一排至少有2将 n 个座位先放到3 排中的某一

9、排，再将剩下的2n+1-n=n+1 个座位任意分到 3 排中，每排不允许为空， 这样的摆法共有 32n 1 n 1n23种方案， 所以符合题意的摆法有：22n3nn1222。3欢迎下载精品文档(2) 会议室中有 2n 个座位，现摆成 3 排，要求任意两排的座位都占大多数，求有多少种摆法？解：(2)方法 1：如果没有附加限制则相当于把2n 个相同的小球放到 3 个不同的盒子里，有2n312n2n 个座位。这相当于2种方案，而不符合题意的摆法是有一排至少有2将 n 个座位先放到3 排中的某一排，再将剩下的2n-n=n 个座位任意分到3 排中，这样的摆法共有 32nn3 1n 23种方案。需要注意的

10、是，三排中如果任意两排都是22n2n 个座位共有3 种情况， 这 3 种情况在 3中被重复计算了2 次，因此需要将重复减2去的 3 次加上。所以符合题意的摆法有：2n2n2n133222方法 2：设第一排座位有x1 个，第二排座位有x2 个，第三排座位有x3 个。 x1+x 2+x3=2n，且 x1+x2n+1， x1 +x3n+1， x2+x3n+1，令 y1=x1+x2-n-1 ， y2=x1+x3 -n-1 ， y3=x2+x 3-n-1 ，可知y1+y2 +y3=2(2n)-3n-3=n-3 且 yi 0，1i 3。显然， x 方程满足要求的解与 y 方程非负整数解一一对应，有n331

11、n 131种。2方法 3：要求每行非空如果没有附加限制则相当于把2n 个相同的小球放到3 个不同的盒子里，不允许为空，2n12n1种方案， 而不符合题意的摆法是有一排至少有n 个座位。 这相当于将有22n-1 个座位先放到3 排中的某一排，再将剩下的2n-(n-1)=n+1 个座位任意分到 3 排中，每2n (n1) 1n排不允许为空，这样的摆法共有33种方案，所以符合题意的摆22法有：2n 13nn 12223.24n(n 2) 个不同的球分给甲、乙、丙3 人，使得甲至少分得两个球，有多少种不同的分法？n解： 3n2n n2n 1i2n 2n ii。4欢迎下载精品文档3.2524 个相同的球

12、分堆，使得每堆的球不少于5，有多少种不同的分堆方法？方法 1：24i ki24i5(1 x5( x5 )2L)(1x6(x6 ) 2 L )L (1 x24( x24 ) 2(x24 )3L )1(1x5 )(1 x6 ) L(1x24 )每堆去掉4 个球，剩余球分堆的方法数5B(244i,i )B(20,1)B(16,2)B(12,3)B(8, 4)B(4,5)i 118125026其中B(12,3)B(9,1)B(9,2)B(9,3)14B(6,1)B(6,2)B(6,3)1413B(3,1)B(3,2)B(3,3)141311112B(8,4)B(4,1)B(4,2)B(4,3)B(4,

13、4) 12115习题四4.3 一项对于A,B,C 三个频道的收视调查表明，有 20%的用户收看A，16%的用户收看B，14%的用户收看C， 8%的用户收看 A 和 B， 5%的用户收看A 和 C，4%的用户收看 B 和 C， 2%的用户都看。求不收看A,B,C 任何频道的用户百分比？解：设性质P1 是收看 A 频道的用户百分比；P2 是收看 B 频道的用户百分比； P3 是收看 C 频道的用户百分比；Ai=x|xS x 具有性质 Pi ， i=1,2,3。S 是受调查的所有用户的集合。| S |1；|A1|20%,| A2 |16%,| A3| 14%| A1A2 |8%,| A1 A3 |5

14、%,| A2 A3 |4%| A1A2A3|2%根据定理 4.1.1，有|A1A2A3| |S| (|A1|A2|A3|)(|A1A2|A1A3|A2A3|) |A1A2A3|1(20%16%14%)(8%5%4%)2%65%。5欢迎下载精品文档65A9632627BC4.4 某杂志对100 名大学新生的爱好进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中 58 人喜欢看球赛，38 人喜欢看戏剧， 52 人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有 18 人，既喜欢看电影又喜欢看戏剧的有16 人，三种都喜欢看的有12 人，求有多少人只喜欢看电影？解：方法 1：设性质 P1 喜欢看球赛； P2

15、喜欢看戏剧； P3 喜欢看电影。 Ai=x|x Sx 具有性质Pi ，i=1,2,3。S 是 100 名大学新生的集合。|S| 100| A1|58,| A2 |38,| A3 |52| A1A2 |18,| A1 A3 |?,| A2 A3 | 16| A1A2A3 |12由题意可得，这100 名大学生中每人至少有三种兴趣中的一种，| A1A2A3 | |S| (|A1| |A2 | |A3|) (|A1A2 | |A1 A3| |A2 A3 |) |A1 A2 A3|100(5838 52) (18 | A1 A3 | 16) 120所以可得既喜欢看球赛有喜欢看电影的人有| A1A3 |(

16、583852)100(1816)1226因此只喜欢看电影的人有|A1A2A3| |A3|A1A3|A2A3|A1A2A3|=52-(26+16)+12=22人方法 2：|A1A2A3| |S|A1|A2|A1A2| 100(5838)1822。6欢迎下载精品文档方法 3：设只喜欢看球赛的人数为 x；设只喜欢看电影的人数为 y；喜欢看球赛和电影但不喜欢看戏剧的人数为 z，则xyz10038xz5818yz5216解得 y=22，所以 22 人只喜欢看电影。球赛261461222416电影戏剧4.5 某人有六位朋友，他跟这些朋友每一个都一起吃过晚餐12 次，跟他们中任二位一起吃过 6 次晚餐，和任

17、意三位一起吃过4 次晚餐，和任意四位一起吃过3 次晚餐，任意五位一起吃过2 次晚餐，跟六位朋友全部一起吃过一次晚餐，另外，他自己在外吃过8 次晚餐而没碰见任何一位朋友，问他共在外面吃过几次晚餐?解：设n 为在外面共吃过晚餐的次数，性质Pi(1i6) 表示他和第i位朋友吃过晚餐，Ai(1i6) 表示他和第i 位朋友吃过晚餐的次数。显然满足对称筛公式，其中N (1)12, N (2)6, N (3)4, N (4)3, N (5)2, N (6)1,由题可得方程：| A A A A A A | n C112 C26 C34 C43 C52 C 61 8123456666666解得吃饭次数为 C61

18、12C62 6C634C643 C652C661 8364.13计算棋盘多项式R() 。解：R() = x*R()+R() =x*(1+3x+x2)+(1+x)*R()= x3+3x2+x+(1+x)xR()+R()。7欢迎下载精品文档= x3+3x2+x+(1+x)x(1+x)+(1+4x+2x2)= 5x3 +12x2+7x+14.14A, B, C, D, E 五种型号的轿车，用红、白、蓝、绿、黑五种颜色进行涂装。要求A 型车不能涂成黑色； B 型车不能涂成红色和白色； C 型车不能涂成白色和绿色； D 型车不能涂绿色和蓝色； E 型号车不能涂成蓝色，求有多少种涂装方案？解：ABCDE红

19、白蓝绿黑ABCDE蓝绿白红黑ABCDE红白绿蓝黑1. 若未规定不同车型必须涂不同颜色，则：涂装方案4 333 4 4322. 若不同车型必须涂不同颜色，则：禁区的棋盘多项式为：R()=R()R()=(1+x)(xR()+R()=(1+x)(xR()R()+R()R()=(1+x)(x(1+2x)2 +(1+3x+x 2) 2)=1+8x+22x2+25x3 +11x4+x5所以：N =5!-r1× 4!+r2 × 3! r3 × 2!+r4 × 1!- r5× 0!。8欢迎下载精品文档=5！ -8*4 ！ +22*3 ！ -25*2 ！ +11

20、*1 ！-1=20习题五5.1 求如下数列的生成函数。（ 1） ak( 1)k (k1) ；（2） ak( 1) k k2k ；（ 3） akk 6 ；（ 4） akk(k 2) ；（ 5） aknk（ 6） ak；kk3解：(1)A( x)(1)k ( k 1) xk(1)k xk1 ' x'1k 0k01x(1x) 2(2) Ak (x)(1)k k2k xkk(2 x) k(12xk0k 02x) 2(3) A( x)(k6) xkkxk6xkx6x66x6 5xk 0k 0k 0(1 x)21 x(1 x)2(1 x)2(4) A(x)k (k2) xkxk (k1)x

21、k 1kxkxx ''x1'k0k0k01x1x2xx3xx2(1x)3(1x)2(1x)3(5) Ak ( x)nk1kxk(1k0x) n 1kxkk33k22k xk1k 3 xk1k 2 xk1kx k(6) A(x)k 0 3k 066 k 02 k 03 k 01 x4x2x31 x(1x)1x6(1x)42 (1x) 33 (1x) 2x 4x2x33x 3x32x 4x22x3x36(1x)4(1x) 4(6) A(x)kxkkxkkxkx3kxk3k 0 3k 3 3k 3 k 3k 3 k 3x3k3kx3kx(1 x)4k0。9欢迎下载精品文档5.

22、3 已知数列23x9x2ak 的生成函数是 A(x)1，求 ak .3x2 3x9x222kk3xA(x)3x3x3 x11 3xk 0ak9n12 3nn15.15知数列 ak 的指数生成函数是 Gx ( x)x25ex ，求 ak 。Gx (x)x25ex2x2xk2!5k 0 k !ak7k25k26.5平面上有 n 条直线，它们两两相交且沿有三线交于一点，设这n 条直线把平面分成 f (n) 个区域，求f (n) 的递推关系并求解.解：设 n-1 条直线把平面分成f (n-1) 个区域，则第n 条直线与前n-1 条直线都有一个交点，即在第 n 条直线上有 n-1 个交点，并将其分成 n

23、 段，这 n 段又把其所在的区域一分为二。f (n)f ( n1)n,(n2)f (1)2齐次特征方程： x10特征根： x1非齐次特解：f *( n)(b0 b1 n)n代入递推关系得：b0 b11，2(1 n)nf # ( n)c12代入递推关系得：c11f (n)1(1n)n26.6一个 1n 的方格图形用红、 蓝两色涂色每个方格， 如果每个方格只能涂一种颜色，且不允许两个红格相邻，设f ( n) 有种涂色方案，求f ( n) 的递推关系并求解.。10欢迎下载精品文档解：f (n-2)f (n-1)设 f ( n) 为 1 n 的方格图形的涂色方案。当 n=1 时， f (1)=2 ，即

24、一个方格有红、蓝两种涂色方案。当 n=2 时， f (2)=3 ，即两个方格有（红、蓝） ，（蓝、红）、（蓝、蓝）三种涂色方案。由于不允许两个红格相邻，所以不存在（红、红）的情况。当 n>2 时，如果第一个格子涂为蓝色，则剩余n-1个格子的涂色方案数为f( -1) ；如果第n一个格子涂为红色，由于不允许两个红格相邻，所以第二个格子必为蓝色，则剩余n-2 个格子的涂色方案数为 f ( n-2) 。于是，当n>2 时涂色方案数为 f ( n)= f ( n-1)+f ( n-2) 。f (1)2; f (2)3;f (n)f (n -1)f (n - 2).先求解这个递推关系的通解，它

25、的特征方程为x2x10,解这个方程，得x115152, x2.2所以，通解为1n1nf (n)c1552c2.2代入初值来确定c1 和 c2 ，得15c1152,22c2325 c13-5 c23.2求解这个方程组，得22c11 ? 15, c21 ? 15.5252所以，原递推关系的解为115n 3115n 3f (n)5252（ n 0,1,2,）.。11欢迎下载精品文档6.7核反应堆中有和两种粒子，每秒钟内1 个粒子可反应产生出3 个粒子，而 1 个粒子又可反应产生出1 个粒子和 2 个粒子 . 若在 t =0s 时刻反应堆中只有1 个粒子，求 t =100s 时刻反应堆里将有多少个粒子

26、和粒子 .解：设 t 时刻反应堆中粒子数为f (t ) ，粒子数为g(t)在 t-1时刻g(t-1)f (t -1)在 t 时刻3f (t 1) 2g(t-1)g(t -1)f (t)g(t1),( n2)g(t )3 f (t1)2g(t1)f (0)1,g(0)0g(t )3g(t2)2g(t1),(n2)g(0)0, g(1)3齐次特征方程： x22x30特征根： x13, x21齐次通解：g# (t)c1 3tc2 (1)t代入递推关系得：c1 3 ，c2344g(t)3 3t3 (1)t44f (t)3t 13(t 13t3t4341)4( 1)46.8求下列 n 阶行列式的值dn。12欢迎下载精品文档