组合数学及其应用课后答案

主要内容

前言 绪论

第1章 鸽巢原理

1.1 鸽巢原理的简单形式 1.2 鸽巢原理的加强形式 1.3 Ramsey问题与Ramsey数 1.4 Ramsey数的推广 习题

第2章 基本计数问题

2.1 加法原则与乘法原则 2.2 排列与组合

2.3 多重集合的排列与组合 2.4 二项式系数

2.5 集合的分划与第二类Stirling数 2.6 正整数的分拆 2.7 分配问题 习题

第3章 容斥原理

3.1 引论 3.2 容斥原理

3.3 容斥原理的应用

3.4 Mobius反演及可重复的圆排列 习题

第4章 递推关系

4.1 递推关系的建立

4.2 常系数线性齐次递推关系的求解 4.3 常系数线性非齐次递推关系的求解 4.4 用迭代归纳法求解递推关系 4.5 Fibonacci数和Catalan数 习题

第5章 生成函数

5.1 引论

5.2 形式幂级数

5.3 生成函数的性质

5.4 用生成函数求解递推关系 5.5 生成函数在计数问题中的

5.6 有限制位置的排列及棋子多项式 习题

第6章 Polya计数理论

6.1 引论

6.2 置换群的基本知识 6.3 计数问题的数学模型 6.4 Burnside引理 6.5 映射的等价类

习题二

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人的小组中，总存在两个人，他们在组内所认识的人数相同。证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：

习题二

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.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个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶

组合数学引论课后答案

习题一

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

《组合数学》课程结课作业

题目 系 号 递推关系的求解及其应用

控制与计算机工程学院

2018年5月

院 专业班级学生姓名学

摘要

递推关系作为数学的一种思维，充分的展现了生活中许多事物现象变化所遵循的规律。所有的事物都不是单一存在的，而是和某些东西相互依存的。比如在求解排列组合、数列中都会用到递推关系的思想与方法。本论文将围绕着递推思维及求解在数列、排列组合上的应用展开讨论。本论文阐述递推关系不是单一的个体，它与生成函数、线性关系、数列组合综合使用，并到达解决问题的思想。也说明学科之间是一个统一的整体。

关键词：递推关系;求解方法;递推思维;应用

1 绪论

递推关系几乎在所有的数学领域中都占据着重要的比例和广泛应用,在物理学上也有着深刻的影响，是数学运算中的一个强有力的工具。因此不管是在教学中还是生活中，都可能要用递推关系来解决所碰到的问题，或与其他学科相结合形成性学科的过程中用递推关系，比如递推关系可和数列、线性规划与矩阵相结合形成要实现这一目的新学科，把所学的知识串连在一起，形成一种新的思维。首要的关键是用递推方法来探究这一过程，搭建一桥梁。在此基础上才能用所学的递推理论和方法进行分析和应用，从而才能解决实

1.1 题（宗传玉）

从{1，2，??50}中找两个数{a，b}，使其满足 （1）|a-b|=5； （2）|a-b|?5； 解：（1）：

由|a-b|=5?a-b=5或者a-b=-5，由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）??（50，45），共有45对。

当a-b=-5时，两数的序列为（1，6），（2，7）??（45，50）也有45对。 所以这样的序列有90对。 （2）：

由题意知，|a-b|?5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0；

由上题知当|a-b|=5时 有90对序列。

当|a-b|=1时，两数的序列有（1，2），（3，4），（2，1）（1，2）??（49，50），（50，49）这样的序列有49*2=98对。

当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对，

当|a-b|=0时有50对

所以总的序列数=90+98+96+94+92+50=520 1.2题（王星） 解：

（a）可将5个女生看作一个单位，共

第二章作业答案

7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明 用100分别除这52个整数，得到的余数必为0, 1,?, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，?，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则a?b能被100整除。若a和b被100除余数之和是100，则a?b能被100整除。

11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i天她共学习了ai小时。因为她每天至少学习1小时，所以

a1,a2,?,a37和a1?13,a2?13,?,a37?13都是严格单调递增序列。因为总的学习时间

不超过

60

小时，所以a37?60，a37?13?73。a1,a2,?,a37,

a1?13,a2?13,?,a37?

填空题

1．将5封信投入3个邮筒，有_____243 _种不同的投法．

2．5个男孩和4个女孩站成一排。如果没有两个女孩相邻，有 43200 方法．

3．22件产品中有2件次品，任取3件，恰有一件次品方式数为__ 380 ______． 4．(x?y)6所有项的系数和是_64_ _．答案：64 5．不定方程x1?x2?x3?2的非负整数解的个数为_ 6 ___．

6．由初始条件f(0)?1,f(1)?1及递推关系f(n?2)?f(n?1)?f(n)确定的数列

{f(n)}(n?0)叫做Fibonacci数列

7．（3x-2y）20 的展开式中x10y10的系数是

c1020310(?2)10．

8．求6的4拆分数P4(6)? 2 ．

?5,f(5)?，试求89．已知在Fibonacci数列中，已知f(3)?3,f(4)Fibonacci数f(20)?10946

10．计算P4(12)?

P4(12)??Pk(12)?P1(8)?P2(8)?P3(8)?P4(8)k?14?P1(8)?P2(8)??Pk(5)??Pk(4)?1?4?5?5?15

k?1k?13411