组合数学引论课后答案（部分）

组合数学引论课后答案

习题一

1.1

任何一组人中都有两个人，它们在该组内认识的人数相等。

1.2

任取11个整数，求证其中至少有两个数，它们的差是10的倍数

1.3

任取n+1个整数，求证其中至少有两个数，它们的差是n的倍数

1.4

在1.1节例4中证明存在连续的一些天，棋手恰好下了k盘棋(k=1,2,…，21).问是

否可能存在连续的一些天，棋手恰好下了22盘棋

1.5

将1.1节例5推广成从1,2，…，2n中任选n+1个数的问题

1.6

从1,2,…,200中任取100个整数，其中之一小于16，那么必有两个数，一个能被另

一个整除

1.7

从1,2,…,200中取100个整数，使得其中任意两个数之间互相不能整除

1.8

任意给定52个数，它们之中有两个数，其和或差是100的倍数

1.9

在坐标平面上任意给定13个整点（即两个坐标均为整数的点），则必有一个以它们

中的三个点为顶点的三角形，其重心也是整点。

1.10 上题中若改成9个整点，问是否有相同的结论？试证明你的结论

1.11 证明：一个有理数的十进制数展开式自某一位后必是循环的。

1.12 证明：对任意的整数N，存在着N的一个倍数，使得它仅有数字0和7组成。（例如，

N=3,我们有3?259=777;N=4,有4?1952=7700;N=5,有5?14=70;……）

1.13

(1) 在一边长为1的等边三角形中任取5个点，则其中必有两个点，该两点的距离至多为

12；

(2) 在一边长为1的等边三角形中任取10个点，则其中必有两个点，该两点的距离至多

1为3；

(3) 确定

mn，使得在一边长为1的等边三角形中任取mn个点，则其中必有两个点，该两

1点的距离至多为n；

1.14 一位学生有37天时间准备考试，根据以往的经验，她知道至多只需要60个小时的复

习时间，她决定每天至少复习1小时，证明：无论她的复习计划怎样，在此期间都存在一些天，她正好复习了13个小时。

1.15 从1,2,…,2n中任选n+1个整数，则其中必有两个数，它们的最大公约数为1

出的数属于同一个鸽巢，即它们的最大公约数为1

1.16 针对1.1节的例6，当m,n不是互素的两个整数时，举例说明例中的结论不一定成立

习题二

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个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的

坐标也是整数。 证明：

有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只颜色选择，根据鸽巢原理，则必有两个单元格的

颜色相同。另外，每列中两个单元格的不同位置组合有5=10种，这样一列中两个同色单元格

2的位置组合共有10*4=40种情况。

而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。

2.9 将一个矩形分成(m+1)行mm+1+1列的网格每个格子涂1种颜色，有m种颜色可以选择，

2证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明：

（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有m+1种，这样一列中两个同色单元格的位置组合

2共有 m+1m种情况

2（3）现在有mm+1+1列，根据鸽巢原理，必有两列相同。证明结论成立。

22.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

所以从第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。 证明：

要证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*C66662) C18/3! *C12*C63.4 教室有两排，每排8个座位。现有学生14人，其中的5个人总坐在前排，4个人总坐在

后排，求有多少种方法将学生安排在座位上？

5解：前排8个座位，5人固定，共C8*5!种方法；后排8个座位，4人固定，共C84*4!种方法；5前排和后排还剩7个座位，由剩下的5人挑选5个座位，共C7*5!种方法；则一共有55C8*C84*C7*5!*5!*4!种安排方法。

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%

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 ｎ为整数且ｎ?３

证明：由定理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}?

(1) 有D1与Dn-1同色，此时Dn有k-1种方案，可将D1与D n-2看成相邻区域，则D1,D2, …, Dn-2的着色方案为f(n-2)。

(2) D1与Dn-1异色，此时Dn有k-2种方案，可将，则D1,D2, …, Dn-1的着色方案为f(n-1)。

(k-1)f(n-2)+(k-2)f(n-1) n-1

另有：f(n)=k(k-1)-f(n-1)

第七章

例n种颜色涂色装有7颗珠子的手镯，如果只考虑手镯的旋转，求有多少种涂色方案？ 解 对象集D＝{1,2,3,4,5,6,7}，颜色集是R＝(1,2,3,…,n)，D上的置换群G＝

{g0,g1,g2,…,g6}，其中gi表示旋转360°*i/7，因7是质数，所以除λ(g0)＝7外，其它λ(gi)＝1，(i=1,2,3,4,5,6)，代入Polya公式，得 L＝1/7*[n7+6n]

而四边形：转180时 P22 6,8,9

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