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

3.5 将英文字母表中的26个字母排序,要求任意两个元音字母不能相邻,则有多少种排序方

法?

解:先排21个辅音字母,共有21!

5再将5个元音插入到22个空隙中,P22

5故所求为21!?P22

(插入法)

3.6 有6名先生和6名女士围坐一个圆桌就餐,要求男女交替就坐,则有多少种不同的排坐方

式?

解:6男全排列6!;6女全排列6!;6女插入6男的前6个空或者后6个空,即女打头或男打头6!*6!*2;再除以围圈重复得(6!*6!*2)/12=6!*5! 或

男6的圆排列为5!,对每个男的排列,女要在他们之间的6个位置,进行线性排列6!(而不是5!)。

(圆排列可以通过线性排列来解决) 3.7 15个人围坐一个圆桌开会,如果先生A拒绝和先生B和C相邻,那么有多少种排坐方式? 解:15人圆排列14!;

A与B相邻有2*14!/14=2*13!; A与C相邻有2*14!/14=2*13!;

A与BC同时相邻有2*13!/13=2*12!;

于是A不与B、C相邻的坐法共14!- 2*13!- 2*13!+ 2*12!(用到了容斥原理) 3.8 确定多重集M?{3?a,4?b,5?c}的11-排列数?

解:M的11排列=[M-{a}]的11排列+[M-{b}]的11排列+[M-{c}]的11排列,即11!11!11!=27720

??2!4!5!3!3!5!3!4!4!当然了,容斥原理,生成函数也可以做。

3.9求方程x1?x2?x3?x4?20,满足x1?2,x2?0,x3?5,x4??1的整数解的个数。 解:令y1?x1?2?0,y2?x2?0,y3?x3?5?0,y4?x4?1?0

则有y1?y2?y3?y4?14,由定理3.3.3,解个数为:?14?4?1???17???17??680

?14??14??3???????

3.10书架上有20卷百科全书,从中选出4卷使得任意两本的卷号都不相邻的选法有多少种? 解:n=20,r=4,?n?r?1???20?4?1???17??2380

?r????4?4??????证明见38页。

若卷号差为2,3,。。。。。,公式为?

3.11确定(2x-3y)5展开式中x4y和x2y4的系数。

4解:1)x4y:C5*(2x)4*(?3y)1,系数为-240

2)x2y4:系数为0。

3.12确定(1+x)-5展开式中x4的系数。 解:(1?x)?n?n?r?1?r,n=5,r=4,则系数为4?5?4?1???(?1)r?x(?1)?70 ???r?0?r??4??

3.13 确定(x +2y+3z)8展开式中x4y2x2的系数。

8!解:*22*32?15120 4!*2!*2!?n??n?1??n?2??n?k??n?k?1??????3.14 证明组合等式:??0???1???2??????k?????k??,其中n,k为正整数。 ??????????解:右边?n?k?1?是(n+k+1)元集合S?{a1,a2,...,an?k?1}上k个元素子集的个数,这些子集可

??k??分为以下k+1类:

?n?k??第1类:k元子集中不含a1的子集有 个; ?k????

?n?k?1????第2类:k元子集中含a1而不含a2的子集是 个?; k?1??

第3类:k元子集中含a1和a2,而不含a3的子集是 ……

第k+1类:k元子集中含a1,a2,……, ak,而不含ak+1的子集是 由加法原理得证。 根据组合意义进行证明

?n?k?2???k?2?????n???0?????k??k?222???1?2???n3.15利用 k2?2?,求。 ??2??1?????解: 首先有:

?n?1??n??n?1??0??????????????k?1??k??k??k??(p51的(3)) ????????根据已知条件代入以上等式得:

?i??i??1??1??2??2??n??n?i?(2?)?2??2??...?2???2??1??2??1??2??1??2???1?i?1i?1???????????????? ?1??2??n??1??2??n??2???2??...?2?????????...????2??2??2??1??1??1?n2n?1??2??n??1??2??n??2(?????...???)???????...????2??2??2??1??1??1?又由?1???2??...??n???n?1? ?k??k??k??k?1?????????得?1???2??...??n???n?1?,?1???2??...??n???n?1? ?1??1??1??2??2??2??2??3?????????????????则原式?2?n?1???n?1??2(n?1)n(n?1)?n(n?1)?n(n?1)(2n?1)

?3??2?666????3.16在一局排球比赛中,双方最终的比分是25:11,在比赛过程中没有出现5平的比分,求

有多少种可能的比分记录?

解:根据题意,相当于求从点(0,0)到点(25,11)且不经过(5,5)的非降路径数,即为:

?25?11??5?5??25-5?11-5??36??10??26????? ?-?? 5???? ????11??-??5????6?? 1111-5????????????

3.17在一局乒乓球比赛中,运动员甲以11:7战胜运动员乙,若在比赛过程中甲从来没有落后过,求有多少种可能的比分记录?

解:根据题意,相当于求从点(0,0)到点(11,7)且从下方不穿过y=x的非降路径数,见58页,即为:?

3.18把20个苹果和20个橘子一次一个的分发给40个幼儿园的小朋友,如果要求分发过程中任意时刻篮子中余下的两种水果数目都不相同(开始和结束时除外),求有多少种分法方法? 解:根据题意,相当于求从点(0,0)到点(20,20)且不接触y=x的非降路径数,即为:

?2n?2??2n?2?2?2n? 2(??)??n???n?n?1n?1???????11?7?1??11+1+7-2??-?? 11-1 11+1????n=20,则方法数为:2(?38???38?)

?19??20?????

?7??7?3.19计算??和??。

?3??3??7??6??6??5??5???5??5????????3??????2???3????3?????32312????????????2??3??解:1)

??4??4????4??4?? ?5??5??1?5???9???1?5????2????9????3????1?????2??3??2????2??3?????6?19*7?27*6?301?n????n????n???

一个递推公式,????????

2n?1n?1?n?n?1???2?1 ?2?2)

??5??7??6??6??5??5??5????6??5?6?5????3??3??3??1??2??3??2??????????????????4???4??5??5??4???4?? ?1?11???30???1?11????4????30????4????2??3??2???3????1???2?2?1?11(1?4*11)?30(11?4*C4)?1546

3.20 (1)证明 S(n,3)=

方法一:先 考虑3个盒子不同,要保证每个盒子非空:总数为3n,排除到一个盒子为空和两个盒子为空的情况,即:

一个盒子为空(放到两个盒子去),例如第一个盒子为空,第二和第三不空:3( 2n-2) 两个盒子为空,例如第一个和第二盒子为空:3*1 (3n-3( 2n-2)-3)/3! 还可以直接考虑盒子相同。

(2)证明:相当于n个不同球放到相同的n-2个盒子,每个盒子非空,至少为1个,这样使得剩余的2个球要到n-2个盒子,即使得一个盒子有3个,或有二个盒子都装2个球: 使得一个盒子有3个球:C(n,3)

有二个盒子都装2个球:C(n,4)C(4,2)/2!

3.21(1)会议室中有2n+1个座位,现摆成3排,要求任意两排的座位都占大多数,求有多少种摆法?

解:如果没有附加限制则相当于把2n个相同的小球放到3个不同的盒子里,有

?2n?3?1??2n?2????种方案,而不符合题意的摆法是有一排至少有n+1个座位。这相当于将??? ???2n?? 2??n+1个座位先放到3排中的某一排,再将剩下的2n-(n+1)=n-1个座位任意分到3排中,这样

?2n?(n?1)?3?1??n?1????的摆法共有3??种方案,所以符合题意的摆法有: ?3?? ??? 2??? 2??2n?2??n?1??n?2?????3?? 2?? 2????? 2?? ??????可以用代数法

(2) 会议室中有2n个座位,现摆成3排,要求任意两排的座位都占大多数,求有多少种摆法?

习题四

4.1 在1到1000之间不能被2,5和11整除的整数有多少个?

解:设S是这1000个数的集合,性质P2是可被5整除,性质P3是可1是可被2整除,性质P被11整除。

Ai?{x|x?S?x具有性质P},(i?1,2,3) i|A1|?1000/2?500,|A2|?1000/5?200,|A3|???1000/11???90 |A1?A2|?1000/10?100,|A1?A3|???1000/22???45,|A2?A3|???1000/55???18,|A1?A2?A3|???1000/110???9 ?|A1?A2?A3|?1000?(500?200?90)?(100?45?18)?9?364

4.3 一项对于A,B,C三个频道的收视调查表明,有20%的用户收看A,16%的用户收看B,14%

的用户收看C,8%的用户收看A和B,5%的用户收看A和C,4%的用户收看B和C,2%的用户都看。求不收看A,B,C任何频道的用户百分比? 解|A1?A2?A3|?1?(20%?16%?14%)?(8%?5%?4%)?2%?65%

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4