绪论

1. 组合数学的研究内容

组合数学研究的中心问题是"按照一定的规则来安排有限多个对象"，它主要涉及四类问题：

安排的存在性问题
安排的总数问题
构造确定的方案
组合优化

我们通过一个例子来了解这四个问题的顺序：

给出一个 $n\times m(m>n)$ 的棋盘，甲从左下角出发前往右上角，每次有且仅有一种前进路线（向上，向下，向左，向右）。现在要求：

存在性——甲能否不跨越棋盘对角线到达右上角？

总数——甲在不跨越对角线的情况下有多少种前进方案？

构造——请写出一种方案，使得甲只跨越一次对角线后到达右上角；

最优化——甲该如何选择路径.使得在不跨越对角线的情况下到达右上角的路程最短？

虽然这个问题可能有临时编造的意思，但是4个小问都很明白的展现出组合数学的研究内容。

2. 组合数学的特征

组合数学最大的特征是离散型。大多数组合数学的问题来源于智力游戏和生产生活，而人的生产生活一定是离散的。

虽不说世界到底是连续的还是离散的，我们日常处理问题，比如安排时间表，我们需要一个一个的把一定时间段内该完成的任务列举出来。也许在一个时间段内人“连续”的完成一件事，然而整个时间表的任务安排确实是离散的。建立在离散的基础上，我们可以讨论时间表安排的具体方案，如何优化方案使得用时最少等等。

离散的特性就是我们可以“一个一个”的把所有可能发生的事情都列举出来，用数学的语言就是一个集合A，它对等于自然数集 $\mathbb{N}$ ，它的基数是 $\aleph_0$ 。

3. 组合数学的应用

如果你是计算机专业的学生，那么一定要学习算法和数据结构的知识，而很多编程练习题的原型就是组合数学题。一道组合数学题，确定其输入和输出后，就可以改编成为一道程序设计题，让广大程序员体会组合数学的爱。

其他领域，比如数字通信，运筹管理，规划等等处理离散对象的问题都可以用组合数学的理论来研究。

例1: 长度为n的线段，从中切开后可以重叠放置在一起，然后再切。问至少要切几刀才可以切成 $n\times 1$ 的线段？

这里如果知道二分法的时间复杂度的话，其实是比较好处理的。
我们切一刀，整个长度变成 $\frac{n}{2}$ ,重叠在一起可以减少切刀的次数（也就是不重叠要切成等分的4块，需要4刀，但是重叠在一起只需要两刀）。设需要k刀可以让整个线段变成长度为1的线段组合，那么一定有
$\frac{n}{2^k}=1$
也就是 $k=\log n$ 。k肯定是整数，所以最少可以切 $\lceil\log n\rceil$ 刀，而前者恰好是二分法的时间复杂度。

4. 我能不能学好组合数学

组合数学来源于生活，而且（表面上）并不涉及过多高深数学知识，任何人都可以学习组合数学。普通人学习数学理论的价值就是应用它的价值。有些组合数学的题目确实很难，不用因为做不出题目而贬低自己。

抽屉原理

抽屉原理又叫“鸽笼原理”、“鸽舍原理”等等，这个定理主要说明放置物品数目的存在性。

1. 抽屉原理及其加强形式

定理1. 如果把 $n+1$ 个物品放入 $n$ 间抽屉，那么至少有一个抽屉中有两件物品或者更多物品。

推论1. 设 $q_1,q_2,\ldots,q_n$ 都是正整数，如果把 $q_1+q_2+\ldots+q_n-n+1$ 个物品放入到n个盒子中，那么或者第一个盒子至少有 $q_1$ 个物品，或者第二个盒子至少有 $q_2$ 个物品…,或者第n个盒子至少有 $q_n$ 个物品。

推论2. 如果将 $n(r-1)$ 个物品放入到 $n$ 个盒子中，那么至少一个盒子中有r个物品。

推论3. 设 $m_1,m_2,\ldots,m_n$ 是n个整数，而且它们的均值大于等于r
$\frac{m_1+m_2+\ldots+m_n}{n}>r-1$
则 $m_1,m_2,\ldots,m_n$ 一定有一个数不小于r。

推论4. 若将m个物品放入到n个盒子中，则至少有一个盒子中有不少于 $\lceil \frac{m}{n}\rceil$ 个物品， $\lceil \frac{m}{n}\rceil$ 表示不小于 $\frac{m}{n}$ 的最小整数。

2. 运用抽屉原理的例子

抽屉原理内容很容易被我们理解，但是想要灵活运用它，需要运用分析的思维，分析出问题中的“抽屉”和“物品”。

例2: 在边长为1的正方形内任取5点，则至少有两点，它们之间的距离不超过 $\sqrt{2}$ 。

证明：

组合数学（一）：绪论、抽屉原理

把正方形按照两对边中点连线分成四个小正方形，每个小正方形的对角线长度为 $\sqrt{2}$ 。这四个小正方形就是我们要找的抽屉。
将五个点放入四个抽屉，那么至少有一个小正方形中有两个点，它们的距离肯定是小于等于 $\sqrt{2}$ 的。

2.1 在处理整数问题时，同余是构造抽屉的有利工具，使用同余，可以将无限的整数分划成有限个等价类，使得每个等价类就是我们需要的抽屉。

例3：设n为正整数。证明：在 $1\thicksim2n$ 中任取n+1个数，一定存在两数之差为n的倍数。

证明：

两数a，b之差为n的倍数，等价于
$a\equiv b(modn)$
取模n完全剩余系
$\{[k]|k=0,1,2,\ldots,n-1\}$
它将 $1\thicksim2n$ 分成n个盒子，我们现在就在这n个盒子中取n+1个数，那么一定有两个数a，b落入同一个盒子。再根据同余的定义，这两个数的差就整除了n。
$\{1,n+1\},\{2,n+2\},\ldots,\{n,2n\}$
就是具体的抽屉。

2.2 一种问题涉及到“双下标序列”，处理这种问题的办法是减少“下标”。比如使用累加和。

例4：给定m个整数 $a_1,a_2,\ldots,a_m$ 证明：必存在整数k，l $(0\leq k<l \leq m)$ 使得
$m|(a_{k+1}+a_{k+2}+\ldots+a_l)$

证明：

构造部分和序列
$s_m = \sum_{k=1}^m a_k$

如果存在整数h $(1\leq h \leq m)$ 使得 $m|s_h$ ，那么取 $k=0,l=h$ 即可。

$m|(a_{k+1}+a_{k+2}+\ldots+a_l)$ 等价于 $m|(s_l - s_k)$ 也就是
$s_l\equiv s_k(mod m)$
想到这一点，将每个 $s_k$ 用m除它的余数 $r_k$ 代替，这样每个 $r_k$ 都小于等于 $m-1$ ，一共有m个余数，由抽屉原理就知道一定存在两个余数相等。不妨记为 $r_k,r_l$ ，从而有
$a_{k+1}+a_{k+2}+\ldots+a_l = s_l - s_k\equiv (r_l - r_k)(mod m)\equiv0(mod m)$

例5：一个学生有37天的时间准备数据结构考试，根据以往的经验，他知道至多需要60个小时的复习时间，所以他决定每天至少复习1小时。证明：无论他的复习计划如何，在此期间都存在一些连续的一些天，他正好复习13小时。

证明：

设 $a_k$ 为这个学生在第k天的复习时间，那么 $k=1,2,\ldots,37$ 。根据已知条件，不难得出
$a_k \geq 1$
$a_1+a_2+\ldots+a_{37} \leq 60$
记部分和
$s_m = \sum_{k=1}^m a_k$
那么可以得到
$1\leq s_1 < s_2 < \ldots <s_{37} \leq 60$
构造新序列
$s_1,s_2,\ldots,s_{37},s_1+13,\ldots,s_{37}+13$
那么每一项都是小于等于73的，一共有74项，由抽屉原理，一定存在两个数相等。而且这两个数一个属于前37项，一个属于后37项。记为 $s_l,s_k+13$ 。
那么有
$s_l - s_k = a_{k+1}+\ldots+a_l = 13$
这表明，存在连续的 $l-k$ 天，他正好复习了13小时。

2.3 再来看几个不是那么明显的运用抽屉原理的问题。

例6：设一个n阶方阵A的所有元素中，有 $n^2-n+1$ 个0。求证：这个方阵A的行列式 $\det A = 0$ 。

证明：

把方阵A的每一列当作一个抽屉，那么就有n个抽屉。将 $n^2-n+1$ 个0放入n个抽屉，那么因为
$n^2-n+1=n(n-1)+1$
也就是至少一列有n个0，根据行列式的性质，有 $\det A = 0$ 。

例7：设有集合 $A=\{a_1,\ldots,a_10\}$ ，其中每个元素都是一个两位数。那么存在集合B和C，使得B中所有元素的数值和与C中的所有元素的数值和相等。

证明：

取A的所有子集，那么一共有 $2^{10}=1024$ 个。而每个子集的元素和一定小于等于 $100*10=1000$ 。所以在 $1024$ 个子集中一定存在两个子集，他们的元素和相等。