组合数学引论课后答案

更新时间:2024-04-29 15:20:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

习题二

2.1 证明:在一个至少有2人的小组中,总存在两个人,他们在组内所认识的人数相同。 证明:

假设没有人谁都不认识:那么每个人认识的人数都为[1,n-1],由鸽巢原理知,n个人认识的人数有n-1种,那么至少有2个人认识的人数相同。

假设有1人谁都不认识:那么其他n-1人认识的人数都为[1,n-2],由鸽巢原理知,n-1个人认识的人数有n-2种,那么至少有2个人认识的人数相同。

假设至少有两人谁都不认识,则认识的人数为0的至少有两人。

2.2 任取11个整数,求证其中至少有两个数的差是10的整数倍。

证明:对于任意的一个整数,它除以10的余数只能有10种情况:0,1,…,9。现在有11个整数,由鸽巢原理知,至少有2个整数的余数相同,则这两个整数的差必是10的整数倍。 2.3 证明:平面上任取5个坐标为整数的点,则其中至少有两个点,由它们所连线段的中点的坐标也是整数。 2.3证明:

有5个坐标,每个坐标只有4种可能的情况:(奇数,偶数);(奇数,奇数);(偶数,偶数);(偶数,奇数)。由鸽巢原理知,至少有2个坐标的情况相同。又要想使中点的坐标也是整数,则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ; 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明:存在至少2个坐标的情况相同。证明成立。

2.4 一次选秀活动,每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”,至少有多少人参加才能保证必有100个人得到相同的结果?

证明:

根据推论2.2.1,若将3*(100-1)+1=298个人得到3种结果,必有100人得到相同结果。

2.5 一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果?

证明:

根据推论2.2.1,若将4*(20-1)+ 1 = 77个水果取出,必有20个相同种类的水果。

2.6 证明:在任意选取的n+2个正整数中存在两个正整数,其差或和能被2n整除。(书上例题2.1.3)

证明:对于任意一个整数,它除以2n的余数显然只有2n种情况,即:0,1,2,…,2n-2,2n-1。而现在有任意给定的n+2个整数,我们需要构造n+1个盒子,即对上面2n个余数进行分组,共n+1组: {0},{1,2n-1},{2,2n-2},{3,2n-3},…,{n-1,n+1},{n}。

根据鸽巢原理,n+2个整数,必有两个整数除以2n落入上面n+1个盒子里中的一个,若是{0}或{n}则说明它们的和及差都能被2n整除;若是剩下n-1组,因为一组有两个余数,余数相同则它们的差能被2n整除,不同则它们的和能被2n整除。证明成立。

2.7 一个网站在9天中被访问了1800次,证明:存在连续的3天,这个网站的访问量超多600次。 证明:

设网站在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次。

2.8 将一个矩形分成5行41列的网格,每个格子涂1种颜色,有4种颜色可以选择,证明:无论怎样涂色,其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。

证明:首先对一列而言,因为有5行,只有4只颜色选择,根据鸽巢原理,则必有两个单元格的颜色相同。另外,每列中两个单元格的不同位置组合有

=10种,这样一列中两个同色单元格的位置组合共有(52)10*4=40种情况。

而现在共有41列,根据鸽巢原理,无论怎样涂色,则必有两列相

同,也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。

+1+1列的网格每个格子涂12.9 将一个矩形分成(m+1)行m(m2)种颜色,有m种颜色可以选择,证明:无论怎么涂色,其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明:

(1)对每一列而言,有(m+1)行,m种颜色,有鸽巢原理,则必有两个单元格颜色相同。

+1种,这样一 (2)每列中两个单元格的不同位置组合有(m2)+1m种情况 列中两个同色单元格的位置组合共有 (m2)+1+1列,根据鸽巢原理,必有两列相同。证 (3)现在有m(m2)明结论成立。

2.10 一名实验员在50天里每天至少做一次实验,而实验总次数不超过75。证明一定存在连续的若干天,她正好做了24次实验。

证明:令b1,b2,...,b50 分别为这50天中他每天的实验数,并做部分和

a1 = b1,a2 = b1+b2 ,。。 a50 = b1+b2+...+b50 .

由题,bi>=1(1<=i<=50)且a50<=75 所以 1<=a1

考虑数列 a1,a2,...,a50,a1+24,a2+24,a50+24,它们都在1与75+24=99之间。 由鸽巢原理知,其中必有两项相等。由(*)知,a1,a2,...,a50互不相等,从而a1+24,...a50+24 也互不相等,所以一定存在1<=i

24=aj-ai=(b1+b2+b3+…+bi+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+...+bj

所以从第i+1天到第j天这连续j-i天中,她正好做了24次实验。

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 证明:从1~200中任意选取70个数,总有两个数的差是4,5或9。 证明:设这70个数为 a1,a2,…,a70, a1+4,a2+4,…,a70+4, a1+9,a2+9,…,a70+9, 取值范围209,共210个数

2.13 证明:对于任意大于等于2的正整数n,都有R(2,n)=n。 2.13证明:

要证R(2,n)= n,用红蓝两色涂色Kn的边。 当n=2时,R(2,2)=2,因为不管用红还是蓝色都是完全二边形。

假设当n=k时 成立 ,即存在R(2,k)=k(没有一条红边,只有蓝边), 当n=k+1时,R(2,k+1)

若无红边,要想有完全k+1边形,必得有k+1个点,即R(2,k+1)=k+1。证明成立。

习题三

3.1 有10名大学生被通知参加用人单位的面试,如果5个人被安排在上午面试,5个人被安排在下午面试,则有多少种不同的安排面试的顺序? 解:上午的5个人全排列为5! 下午的5个人全排列为5!

5所以有C10*5!*5!?10!,共14400种不同的安排方法。

3.2 某个单位内部的电话号码是4位数字,如果要求数字不能重复,那么最多可有多少个号码?如果第一位数字不能是0,那么最多能有多少个电话号码?

解:由于数字不能重复,0-9共10个数字,所以最多有10*9*8*7=5040种号码;若第一位不能是0,则最多有9*9*8*7=4536种号码。

3.3 18名排球运动员被分成A,B,C三个组,使得每组有6名运动员,那么有多少种分法?如果是分成三个组(不可区别),使得每组仍有6名运动员,那么有多少种分法?

666解:1)C18种 *C12*C6 2)

666/3! C18*C12*C63.4 教室有两排,每排8个座位。现有学生14人,其中的5个人总坐在前排,4个人总坐在后排,求有多少种方法将学生安排在座位上?

解:前排8个座位,5人固定,共C85*5!种方法;后排8个座位,4人固定,共C84*4!种方法;前排和后排还剩7个座位,由剩下的5人挑选5个座位,共C75*5!种方法;则一共有

55C8*C84*C7*5!*5!*4!种安排方法。

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

解:先排21个辅音字母,共有21! 再将5个元音插入到22个空隙中,P

522故所求为21!?P

522(插入法)

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 求方程x?x12?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? ?14???14???3??680??????

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

n?r?1??20?4?1??17?解:n=20,r=4,? ?????????2380?r??4??4?证明见38页。

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

3.11 确定(2x-3y)5展开式中x4y和x2y4的系数。 解:1)x4y:C45*(2x)4*(?3y)1,系数为-240

2)x2y4:系数为0。

3.12 确定(1+x)展开式中x的系数。

n?r?1?,n=5,r=4,则系数解:(1?x)??(?1)???x?n?rrr?0-54

?r?5?4?1?为(?1)? ???704?4?

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

8!*22*32?151204!*2!*2!

3.14 证明组合等式:??0?????1?????2???????k??????????????中n,k为正整数。

?n??n?1??n?2??n?k??n?k?1??,其?k?解:右边?n?k?1?是(n+k+1)元集合S?{a1,a2,...,an?k?1}上k个元素

??k??子集的个数,这些子集可分为以下k+1类: 第1类:k元子集中不含a的子集有 ??n??? k1?k ??? 个;

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

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

??n?k?2?? ?k?2???……

第k+1类:k元子集中含a1,a2,……, ak,而不含ak+1的子集是

由加法原理得证。 根据组合意义进行证明

??n???0???

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

?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?n?1??n?1?2(n?1)n(n?1)n(n?1)n(n?1)(2n?1) 则原式?2??????????3??2?6663.16 在一局排球比赛中,双方最终的比分是25:11,在比赛过程中没有出现5平的比分,求有多少种可能的比分记录?

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

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

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

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

?11?7?1??11+1+7-2???-?? 11-1??? 11+1?

3.18把

20个苹果和20个橘子一次一个的分发给40个幼儿园的小朋友,如果要求分发过程中任意时刻篮子中余下的两种水果数目都不相同(开始和结束时除外),求有多少种分法方法?

解:根据题意,相当于求从点(0,0)到点(20,20)且不接

2n?2??2n?2?触y=x的非降路径数,即为:2(??????)??n?1??n?38??38? n=20,则方法数为:2(??????)?19??20?2?2n? ??n?1?n?

7??7?3.18计算?和????。

?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

一个递推公式,?? 2)

??5??7??6??6??5??5??5????6??5?6?5????3??3??3??1??2??3??2????????????????n??n??n???????? 2n?1n?1???????n?n?1???2?1 ?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.19 (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?个不同的盒子里,有?? 2n????? 2??种方案,而不符合题意????的摆法是有一排至少有n+1个座位。这相当于将n+1个座位先放到3排中的某一排,再将剩下的2n-(n+1)=n-1个座位任

?意分到3排中,这样的摆法共有3???2n?(n?1)?3?1??n?1???种?3????? 2? ?? 2?方案,所以符合题意的摆法有:

?2n?2??n?1??n?2??? 2???3??? 2????? 2?? ??????可以用代数法

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

习题四

4.1 在1到1000之间不能被2,5和11整除的整数有多少个? 解:设S是这1000个数的集合,性质P2是可1是可被2整除,性质P被5整除,性质P3是可被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%

4.2 求1到1000之间的非完全平方,非完全立方,更不是非完全四次方的数有多少个?

解:设S是1000个数的集合, 性质P1是某数的完全平方, 性质P2是某数的完全立方, 性质P3是某数的完全四次方。

Ai?{x|x?S?x具有性质P},(ii?1,2,3) |A1|???1000???31,|A?32|??1000???10,|A?43|??1000???5|A?A612|???1000???3,|A1?A3|???41000???5|A122?A3|???1000???1, |A121?A2?A3|???1000???1 ?|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,|A1??7???4?8?1?, |?2?8??165??4?5?1??4?7?1?,|A4|???56, |A3|???120????5??7??4?3?1?|A1?A2|???20??3?,,

?4?2?1?|A1?A3|????102???4?3?1?|A2?A3|????203??,,

?4?0?1?|A1?A4|???1??0??4?1?1??4?0?1?, , |A2?A4|???4|A?A|??1?34???1??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?其中|A1|?0,|A2|???56,|A3|???35,???5??4??4?3?1?|A4|???20,|A1?A2|?0,|A1?A3|?0,|A1?A4|?0,??3?|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?x3?15?0?x1?7,0?x2?7,0?x3?7?与{7a,7b,7c}的15组合数相等,为28 2)

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?0?y1?8,0?y2?8,0?y3?8,0?y4?8?与{8a,8b,8c,8d}的16组合数相等为489

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

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

?n??n??n??n??n??n???????,显然n!???D0???D1???D2?...???Dn

?0??1??2??n??0??n?(另一种方法:组合分析法) 4.10证明:Dn满足:

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

证明:由定理4.3.1得

Dn?1?(n?1)!(1?111?...?(?1)n?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名女士参加一个宴会,每人都寄存了一顶帽子和一把雨伞,

而且帽子、雨伞都是互不相同的,当宴会结束的离开的时候,如果帽子和雨伞都是随机的还回的,那么有多少种方法使得每位女士拿到的物品都不是自己的?

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

子全错为

1D10?10!(1?1111111111?????????) 1!2!3!4!5!6!7!8!9!10!21?D10雨伞全错为D10解

10!?10! ?D10?D?D?2e110210

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???k?; (6)ak???3??; ????解:(1)由已知得

bk?k?1B(x)?1

(1?x)21 (x?1)2故A(x)?(2)设bk?(?2)k则G{bk}?1 1?2x又因为ak?kbk故G{ak}?x(G{bk})1?bk?k?2x

(1?2x)2或者

B(x)?x (1?x)2(3)G{ak}?G{bk?k}?G{ck?6}?(4)G{ak}?x(G{bk?k?2})1?x66?5x?? 22(1?x)1?x(1?x)x(3?x) (1?x)3?n?k??n?1?k?1?ak??????kk???? (5)

1G{ak}?(1?x)n?1(6)

?k?ak????3?n?4,?4?k?1??3?k?bk?????? kk?????3?k????3??G{ak}?x3(1?x)4

5.2 求如下数列的指数生成函数。 (1)ak?(?1)k; (2)ak?2kk!;

(3)ak?

1; k?1xk解: (1)Ge{ak}??(?1)?e(?x)

k!k?0?k(2)Ge{ak}??2kxk?G{bk?2k}?k?0?1 1?2x(3) Ge{ak}??xf(x)??????1xk?f(x)

k?0(1?k)!?则

1xk?1k?0(1?k)!1kx?1?ex?1k?0k!ex?1故Ge{ak}?

x

2?3x?9x25.3 已知数列?ak?的生成函数是A(x)?,求ak. 1?3x

?22?3x而A(x)?解: A(x)??2?3kxk 1?3x1?3xk?0?2?3k,k?1故ak??

?9,k?1

5.4 求(1?x4?x8)100展开式中x20的系数是多少?

5(1) 若x8取0,则x4取5个,这种情况有C100种;

331(2) 若x8取1,则x4取3个,这种情况有C1100?C99或C100?C97; 2(3) 若x8取2,则x4取1个,这种情况有C1100?C99; 5312故系数为C100?C1100?C99?C100?C99= 91457520。

其他方法

5.5 三个人每个人投一次骰子,有多少种方法使得总点数为9?

2解:这相当于有9个球,用隔板将其分成3组,共有C8?28种方法。又因为这

次点数小于等于6,即711,171和117三种情况不符,故共有25种方法。

(x?x2?x3?x4?x5?x6)3?(x?x)73??2?k?k??x?k(2)?

5.6 求在102和104之间的各位数字之和等于5?

解:(1) 三位数时,相当于x1?x2?x3?5(1?x1?5,0?x2?5,0?x3?5)的非

故中

G(x)?(x?x2?x3?x4?x5)?(1?x?x2?x3?x4?x5)?(1?x?x2?x3?x4?x5)C5为G(x)展开式x5的系数。

(2) 四位数时,相当于

x1?x2?x3?x4?5(1?x1?5,0?x2?5,0?x3?5,0?x4?5)的非负整数解的个

数。

5.7 一个1×n的方格图形用红、蓝、绿和橙四种颜色涂色,如果有

偶数个方格被涂成红色,还有偶数个方格被涂成绿色,求有多少种方案?

解:涂色方案数为bk则:

22xxeGe{bk}?(1?x(1?x2!?4!??)?2!?3!??)?(2423x?e?x22)?(ex)2?e4x?2e2x?14???14k?0?4k?2k?1xk4k!?

因此:bk?4k?1?2k?1,所以有4n?1?2n?1种方案。

5.8 有4个红球,3个黄球,3个蓝球,每次从中取出5个排成一行,

求排列的方案数?

解:设每次取出的k个球的排列数为bk,数列{bk}的指数型生成函数

为Ge{bk}则有

xxxxxxx而我们所求的是Ge{bk}?(1?1!?x(1?1!?x(1?1!?x2!?3!?4!)?2!?3!)?2!?3!)2342323x55!的

系数b5。故有b5?220。

5.9 计算用3个A,3个G,2个C和1个U构成长度为2不同的RNA

链的数量。

x22x2解: (1?x?)?(1?x?)(1?x)中x2的系数C2,有C2=15.

225.10 计算??和??。 ?3??3??7?解:(1)构造多项式x(x?1)(x?2)(x?3)(x?4)(x?5)(x?6)则??即x3的系数

?3??7?b3,则b3?1524,故???1524。

?3??7??7??7?n(2)????1n1?2n2?33,n1?n2?n3?3?n1?n2?n3?4?4的非负整数解为(0,0,4), (1,2,3),

(0,2,2), (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)

?7?????3?21?33?22?32?23?31?24?11?33?11?21?32?11?22?31?11?23?12?32 ?3??12?21?31?12?22??13?31?13?21?14?3015.11设Bn表示把n元集划分成非空子集的方法数,我们称Bn为Bell数。

证明:Bn??????????。

证明:当有1个盒子时,方法数b1???,

?n?当有2个盒子时,方法数b2???,

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

当有k个盒子时,方法数bk???,

?

?n??k?当有n个盒子时,方法数bn???,

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

故Bn??bi??????????????

i?1n?n??n??n??n??n??1??2??3??n??n?

5.12有重为1g的砝码重为1g的3个,重为2g的4个,重为4g的2

个,求能称出多少种重量?

解:即求多项式(1?x?x2?x3)?(1?x2?x4?x6?x8)?(1?x4?x8)中展开式有

多少项 (除1外),原多项式

?(1?x?x2?x3?x4?x5?x6?x7?x8?x9?x10?x11)?(1?x2?x4?x6?x8)故共有

19种重量。

5.13 已知数列?ak?的指数生成函数是Ge(x)?x2?5ex,求ak.

f(x)?x2?5ex解:设

x2x3?x?5(1?x???..)2!3!2 ak=5, k不等于2 ak=7, k =2

补:3个l,2个2,5个3这十个数字能构成多少个4位数偶数。

解 问题是求多重集S={3个1,2个2,5个3}的4排列数,且要求排列的末尾为2(偶数)。可以把问题转化成求多重集S={3个1,1个2,5个3}, 其

??x2x3?x2x3x4x5?Ge(x)??1?x???(1?x)?1?x?????2!3!?2!3!4!5!???3!3!3!3!3!?x3?3!3!????????????? ?3!1!2!1!2!3!1!2!1!1!1!2!1!?3!x3???20??3!x3展开后得的系数为

3!20,所以能组成20个4位数的偶数。

习题六

6.1 设f(n)?12?22???n2,建立f(n)的递推关系并求解。 解:

?f(n)?f(n?1)?n2,(n?2)??f(1)?1齐次特征方程: x?1?0特征根: x?1非齐次特解: f*(n)?(b0?b1n?b2n2)n代入递推关系得:111b0?,b1?,b2?623111? f(n)?(?n?n2)n623

6.2 求解递推关系:

(1)? 解:

?f(n)?7f(n?1)?12f(n?2)?0,(n?2)

?f(0)?4,f(1)?6;齐次特征方程: x2?7x?12?0特征根: x1?4,x2?3齐次通解: f(n)?c14?c23代入递推关系得:c1?-6,c2?10? f(n)??6?4n?10?3n#nn

(2)??f(n)?f(n?2)?0,(n?2)

?f(0)?0,f(1)?2;x2?1?0解:

x1??i,x2?i

?f(n)?5f(n?1)?6f(n?2)?4f(n?3)?8f(n?4),(n?4)(3)?

f(0)?0,f(1)?1,f(2)?1,f(3)?2,;?解:

?次特征方程: x4-5x3?6 x2?4x-8?0特征根: x1?x2?x3?2,x4?-1?次通解: f#(n)?c12n?c2n2n?c3n22n?c4(?1)n代入?推?系得:8718c1?,c2?,c3?-,c4?-273624278n7n12n8? f(n)?2?n2-n2-(?1)n27362427

?f(n)?3f(n?1)?2f(n?2)?1,(n?2)(4)?

f(0)?4,f(1)?6;?解:

齐次特征方程: x2?3x?2?0特征根: x1?2,x2?1非齐次特解: f*(n)?b0n代入递推关系得:b0??1f#(n)?c12n?c2?nc1?3,c2?1? f(n)?3?2n?1?n

6.3 求解递推关系: (1)?解:

?f(n)?4f(n?1)?4f(n?2)?3n?1,(n?2)

?f(0)?1,f(1)?2;

本文来源:https://www.bwwdw.com/article/mwsg.html

Top