组合数学引论课后答案(部分) 下载本文

内容发布更新时间 : 2024/3/29 18:11:57星期一 下面是文章的全部内容请认真阅读。

4.2 求1到1000之间的非完全平方,非完全立方,更不是非完全四次方的数有多少个? 解:设S是1000个数的集合, 性质P1是某数的完全平方, 性质P2是某数的完全立方, 性质Pi3是某数的完全四次方。A?{x|x?S?x具有性质P},(i?1,2,3) i??31,|A2|??31000??10,|A3|??41000??5 |A1|??1000??????6??3,|A1?A3|??41000??5,|A2?A3|??121000??1, |A1?A2|??1000??????12??1 |A1?A2?A3|??1000???|A1?A2?A3|?1000?(31?10?5)?(3?5?1)?1?962

4.4某杂志对100名大学新生的爱好进行调查,结果发现他们都喜欢看球赛和电影、戏剧。其中58人喜欢看球赛,38人喜欢看戏剧,52人喜欢看电影,既喜欢看球赛又喜欢看戏剧的有18人,既喜欢看电影又喜欢看戏剧的有16人,三种都喜欢看的有12人,求有多少人只喜欢看电影?

解:由题意可得,P1,P2,P3分别表示喜欢看球赛、电影和戏剧的学生,相应的学生集合分别

为A1,A2,A3,依题意,这100名大学生中每人至少有三种兴趣中的一种,则A1?A2?A3?0 所以可得既喜欢看球赛有喜欢看电影的人有

|A1?A2|?(58?38?52)?100?(18?16)?12?26

因此只喜欢看电影的人有A2?A1?A2?A2?A3?A1?A2?A3

=52-(26+16)+12=22人 4.5 某人有六位朋友,他跟这些朋友每一个都一起吃过晚餐12次,跟他们中任二位一起吃过

6次晚餐,和任意三位一起吃过4次晚餐,和任意四位一起吃过3次晚餐,任意五位一起吃过2次晚餐,跟六位朋友全部一起吃过一次晚餐,另外,他自己在外吃过8次晚餐而没

碰见任何一位朋友,问他共在外面吃过几次晚餐?

123456C6?12?C6?6?C6?4?C6?3?C6?2?C6?1?8?36

4.6 计算多重集S={4?a, 3?b, 4?c,6?d }的12-组合的个数? 解:令T?{??a,??b,??c,??d}的所有12组合构成W??4?12?1??455

?12???其中|A|??4?7?1??120,|A|??4?8?1??165,

1?7?2?8??????4?7?1?,|A|??4?5?1??56, |A3|???1204?5??7?????4?0?1?,?4?2?1??4?3?1?,,|A1?A2|????20|A1?A3|??2??10|A1?A4|??0??13???????4?1?1??4?3?1?,, |A?A|??4?0?1??1, |A?A|??4|A2?A3|???2024?1?34??????3??0?|A1?A2?A3|?0

?|A1?A2?A3?A4|?455?(120?120?165?56)?(20?10?1?20?4)?50

4.7 计算多重集S={∞?a, 4?b, 5?c,6?d }的10-组合的个数? 解:将??a,其他思想同上题。

?4?10?1?W???286 ??10??4?5?1??4?4?1??4?3?1?其中|A|A2|???56,|A3|???35,|A4|???20,???1|?0,

?5??4??3?|A1?A2|?0,|A1?A3|?0,|A1?A4|?0,|A2?A3|?0,|A2?A4|?0,|A3?A4|?0,|A1?A2?A3|?0

?|A1?A2?A3?A4|?286?(56?35?20)?175

4.8 用容斥原理确定如下两个方程的整数解的个数。

1)x1+x2+x3=15,其中x1,x2, x3都是非负整数其都不大于7; 2)x1+x2+x3+x4=20,其中x1,x2, x3, x4都是正整数其都不大于9; 解: 1)x1?x2为28 2)

?x3?15?0?x1?7,0?x2?7,0?x3?7?与{7a,7b,7c}的15组合数相等,

x1?x2?x3?x4?20?1?x1?9,1?x2?9,1?x3?9,1?x4?9?,因此用y1+1代替x1,y2+1代替x2,y3+1代替x3,y4+1代替x4有

y1?y2?y3?y4?16的16组合数相等为489

?0?y1?8,0?y2?8,0?y3?8,0?y4?8?与{8a,8b,8c,8d}

n??n??n??n? 4.9 定义D0=1,证明:n!??D?D?D????n??1??2??D0012???????n??n?证明:考虑到n个数的全排列包含错位排列和非错排,其中??Dk表示在n个数中任选k个,

?k?这个k个数构成了一个错排,而剩余的n-k个数还在原来的位置。

?n??n??n??n??n??n??0???n?,显然n!??0?D0??1?D1??2?D2?...??n?Dn ????????????(另一种方法:组合分析法)

4.10证明:Dn满足:

?Dn?(n?1)(Dn?1?Dn?2) ??D1?0,D2?1 n为整数且n?3

证明:由定理4.3.1得

111n?1Dn?1?(n?1)!(1??...?(?1))

1!2!(n?1)!111n?2?(n?1)!(1??...?(?1))?(?1)n?1

1!2!(n?2)!Dn?2?(n?2)!(1??Dn?1?Dn?2111?...?(?1)n?2) 1!2!(n?2)!111n?2?(1??...?(?1))[(n?2)!?n]?(?1)n?11!2!(n?2)!111?...?(?1)n?2)?(?1)n?1(n?1) 1!2!(n?2)!?(n?1)(Dn?1?Dn?2)?n!(1?1111n?2n?1n1?(1??...?(?1)?(?1)?(?1))

1!2!(n?2)!(n?1)!n!4.11有10名女士参加一个宴会,每人都寄存了一顶帽子和一把雨伞,而且帽子、雨伞都是互不相同的,当宴会结束的离开的时候,如果帽子和雨伞都是随机的还回的,那么有多少种方法使得每位女士拿到的物品都不是自己的?

解:由于帽子全部拿错和雨伞全部拿错是两个相互独立的事件,设帽子全错为

1111111111D?10!(1??????????)

1!2!3!4!5!6!7!8!9!10!110雨伞全错为D1021解 ?D1012?D10?D10?D10?10!?10! 2e

4.13计算棋盘多项式R( )。

解: R( ) = x*R()+R( ) =x*(1+3x+x2)+(1+x)*R(= x3+3x2+x+(1+x)[xR(

) )+R(

)]

= x3+3x2+x+(1+x)[x(1+x)+(1+4x+2x2)] = 5x3+12x2+7x+1

4.14有A,B,C,D,E五种型号的轿车,用红、白、蓝、绿、黑五种颜色进行涂装。要求A型车不能涂成黑色;B型车不能涂成红色和白色;C型车不能涂成白色和绿色;D型车不能涂绿色和蓝色;E型号车不能涂成蓝色,求有多少种涂装方案? 解:A B C D E

红 白 蓝 绿 黑

1.若未规定不同车型必须涂不同颜色,则:

涂装方案4?3?3?3?4?432 2.若不同车型必须涂不同颜色,则:

禁区的棋盘多项式为: 1+8x+22x2+25x3+11x4+x5

所以:

5!-8*4!+22*3!-25*2!+11*1!-1=20 4.15计算?(210),?(105). (舍)

4.16计算T={∞?1, ∞?2, ∞?3,∞?4}的长度为4的圆排列数。 (舍)

补:(1)在1~2000中能被7整除,但不能被6和10整除的个数。 证明:A1,A2,A3表示被6、7和10整除的数的子集,所求:

A1?A2?A3?A2?A1?A3?A2?A2?(A1?A3)?A2?(A2?A1)?(A2?A3)?A2?(A2?A1?A2?A3?(A2?A1)?(A2?A3))

=219

(2)在1~2000中至少被2、3和5两个数整除的数的个数?

A2?A1?A2?A3?A1?A3?2A1?A2?A3=534

习题五

5.1 求如下数列的生成函数。

(1)ak?(?1)k(k?1);(2)ak?(?1)kk2k; (3)ak?k?6; (4)ak?k(k?2);

?n?k??n???(5)ak??; (6)a?k?k??3??; ????解:(1)由已知得

bk?k?11

B(x)?(1?x)2故A(x)?1

(x?1)2(2)设bk?(?2)k则G{bk}?1 1?2x?2x

(1?2x)2又因为ak?kbk故G{ak}?x(G{bk})1?bk?k或者

B(x)?x (1?x)2x66?5x??

(1?x)21?x(1?x)2(3)G{ak}?G{bk?k}?G{ck?6}?