相信大家在高中阶段一定都接触过排列组合，不知道大家当时感觉排列组合是难还是简单呢？233

由于之前一直有所耳闻，我倾向于认为组合数学就是一门教我们如何计数的学科。当时的我实在太过naive，以致于并没感觉到“计数”实际上大有学问。如何不重复不漏地计数，事实上是十分困难的一件事。而且组合数学研究的问题事实上十分宽泛，绝不仅仅是在研究如何计数的问题，组合存在性、组合设计也都是组合数学的重要组成部分。

在学习的过程中，令我感受最深的是：组合数学是非常需要经验或者技巧的。面对一道习题，第一次做的难度与第二次、第三次做的难度往往千差万别。因此，我认为要掌握好组合数学往往需要进行大量的练习。除此之外，组合数学的另一个特点是：很多问题都可以从多个方面理解，从而被联系在一起。因此，多思考不同问题之间的关联，例如恒等式的组合意义等也是理解组合数学所必须付出的努力。

笔记的组织形式将与往常类似，但是读者会发现新的定义会显著少于前面若干篇笔记。另外，我们默认读者对于排列、组合的定义以及基础应用比较熟悉（包括一些最常见的组合恒等式、二项式定理等）。

在第一章，我们率先介绍组合存在性定理。

首先，我们介绍抽屉原理。

相信读者一定知道抽屉原理的具体含义。然而，抽屉原理的应用方式可谓五花八门。

定理（抽屉原理）

m 个球放入 n 个抽屉，至少有一个抽屉含有 \left \lceil \frac{m}{n}\right \rceil 个球。

利用反证法即可轻松证明其正确性

进一步地，我们进行推广，允许每个抽屉存在差异，可以得到其加强形式。

定理（抽屉原理）

m 个球放入 n 个抽屉 1,2,...,n ，若 m\geq a_1+...+a_n-n+1 ，则必定存在抽屉 i ，其中至少含有 a_i 个球。

同样地利用反证法可以证明其正确性

下面，我们将抽屉原理进一步进行抽象化与严格化

将球放入抽屉的行为可以看作一个映射。球组成的集合即为定义域，而抽屉组成的集合即为像集，则我们可以用集合论的语言来表示抽屉原理。

由此，我们给出与上述两个定理相对应的函数形式：

定理（抽屉原理函数形式）

A,B 非空有限， f:A\rightarrow B 为函数，则 \exists b_1\in B,|f^{-1}(b_1)|\geq \frac{|A|}{|B|} 。

定理（抽屉原理函数形式）

A,B 非空有限， B=\left \{ b_1,...,b_n \right \} ,f:A\rightarrow B 为函数，则若 |A|=x_1+x_2+...+x_n-n+1 ，则 \exists b_i\in B,|f^{-1}(b_i)|\geq x_i 。

在具体应用抽屉原理时，我们往往需要想好用什么作为球而用什么作为抽屉。

下面我们举出一个有关于递增递减子序列的经典例子来说明抽屉原理的使用方式，更多的例子见习题中。

例：任意 n^2+1 个实数，总是存在长度至少为 n+1 的递增子序列或递减子序列。

证明：

不妨设 a_1,a_2,...,a_{n^2+1} 中不存在长度为 n+1 的递增子序列，那么我们只需要证明必定存在长度为 n+1 的递减子序列即可。

不妨假设 a_1,a_2,...,a_{n^2+1} 中最长递增子序列长度不大于 n 。

注意到：抽屉原理中往往会出现 \left \lceil \frac{m}{n}\right \rceil 的形式，我们现在有 n,n^2+1 两个数

我们发现： \left \lceil \frac{n^2+1}{n}\right \rceil=n+1 ，于是我们仿佛找到了解决问题的思路

我们逆向地进行思考：我们要设计一个函数 f ，使得其定义域为 a_1,a_2,...,a_{n^2+1} 组成的集合，而其像集为递增子序列长度。

很自然的一个想法就是： f 将 a_i 映射为以其为开头的最长递增子序列长度。

那么显然在上述条件下， 1\leq f(a_i)\leq n

故由抽屉原理， \exists b_1\in \left \{ 1,2,...,n\right \},|f^{-1}(b_1)|\geq n+1

存在至少 n+1 个 a_i ，使得以其为开头的最长递增子序列长度相同，均为 b_1

不妨设这些数为 a_{k_1},...,a_{k_{n+1}} ，我们下面证明这必定是一个递减子列

若 a_{k_1}n 。

证明：

我们随机地对于 K_n 的边进行红蓝着色，所有边的染色相互独立，每条边等概率地被染成红色或蓝色

考虑 K_n 的含有 k 个顶点的导出子图 R ， A_R 表示“ R 为单色的”这个事件

我们考虑这个事件发生的概率

P(A_R)=C_n^k2^{1-C_k^2}

（注意到先从 n 个顶点中选取 k 个， R 中有 C_k^2 条边，且最终能有 R 全为蓝色或全为红色两种情况，故概率为 C_n^k\times(\frac{1}{2})^{C_k^2}\times2 ）

若 P(A_R)R(k,k)>n

不得不说，Erdos将概率引入的想法非常具有启发性。说组合数学是确定性的，不如说组合数学是不具有随机性的。而正是因为这样的不具有随机性，使得概率一旦介入 (0,1) 之间，就意味着条件的不满足，从而估计出了Ramsey数的组合存在性所需要的下界。

Erdos的这一个证明可以说是为组合数学的发展开辟了一块新的空间，概率论中的大量成熟结果被引入，从而极大地加快了组合数学的发展。

最后，我们用集合论的语言陈述Ramsey定理并且将其推广到更高维的情形。

定理（Ramsey定理的集合论形式）

任意给定 k_1,k_2 ，必定存在 n 与集合 V=\left \{ v_1,...,v_n \right \} ，使得对于集合 P （其为 V 的所有含 2 个元素的子集构成的集合）的任意一个划分为 2 个部分的划分 \left \{ P_1,P_2\right \} （满足 P_1,P_2 不交且并集为 P ），必定对于某个 i\in \left \{ 1,2\right \} ，存在 U_i\subset V ，使得 |U_i|=k_i ，且 U_i 的所有含有 2 个元素的子集都包含于 \left \{ P_1,P_2\right \} 的某一个元素中。

上述集合论形式的Ramsey定理看起来十分繁琐，但是对于我们将其推广到三维、四维甚至更高维的缺乏直观的情况提供了极大的便利。注意 V 事实上就是顶点集，其所有含有 2 个元素的子集构成的集合 P 即为边集，划分为两个部分的划分就是对于边的红蓝染色。最终结论是：必定存在一个单色的 k_1 个元素的边集子集或者一个单色的 k_2 个元素的边集子集。经过上述翻译，我们不难发现这样的表述与前面的图论定义是等价的。

进一步地，我们进行更高维数以及更多种颜色进行颜色的推广。

定理（广义Ramsey定理）

任意给定 p,c,k_1,...,k_c ，必定存在 n 与集合 V=\left \{ v_1,...,v_n \right \} ，使得对于集合 P （其为 V 的所有含 p 个元素的子集构成的集合）的任意一个划分为 c 个部分的划分 \left \{ P_1,P_2,...,P_c\right \} （满足不交且并集为 P ），必定对于某个 i\in \left \{ 1,2,...,c\right \} ，存在 U_i\subset V ，使得 |U_i|=k_i ，且 U_i 的所有含有 p 个元素的子集都包含于\left \{ P_1,P_2,...,P_c\right \} 的某一个元素中，记 n=R(k_1,...,k_c;p) 为广义Ramsey数。

一种理解广义Ramsey定理的方式是将其理解为“超图”，超图中的边不再是两点之间形成的，而是 p 个点之间形成的。同样地，广义Ramsey数表示了任意边集 c 染色后超图中必定存在单色 k_1 阶完全图或单色 k_2 阶完全图或......或单色 k_c 阶完全图的最小顶点数。

特别地，对于一个函数 f:\left \{ 1,2,...,m\right \}\rightarrow \left \{ y_1,...,y_k\right \} ，若对于某个 i 有 \left \{ 1,2,...,m\right \} 的子集 A\subset f^{-1}(y_i) ，则称 A 为单色的。（ f 即可视为一个染色函数，将一个数映射到其所对应的颜色）

总而言之，Ramsey理论虽然问题形式与出发点相对容易，但是处理与估计手段异常复杂，是一个十分难解的问题。其想要表达的中心思想是：绝对而又完全的无序是不存在的。

习题：

1、证明：在任一含有 mn+1 个元素的偏序集中，必定存在长度至少为 m+1 的链或者长度至少为 n+1 的反链。（Dilworth定理）

2、证明：任意选取 101 个不同正整数，则要么存在 11 个正整数，任意两个之间都不能相互整除，要么存在 11 个正整数，使得按照从小到大的顺序排列之后，每一个数都必定能整除其后一个数。

3、 S 为 \left \{ 1,2,...,2n \right \} 任意一个元素个数大于 n 的子集，则证明：必定存在 S 中两个不同的数，且它们互素。

4、S 为 \left \{ 1,2,...,2n \right \} 任意一个元素个数大于 n 的子集，则证明：必定存在 S 中两个不同的数，使得一个数整除另外一个数。

5、在 \mathbb{R}^2 中任取 n^2+1 个不同点，证明：必定存在 n+1 个不同点(x_1,y_1),...,(x_{n+1},y_{n+1}) 使得要么有 x_1\leq x_2\leq ...\leq x_{n+1} 且 y_1\geq y_2\geq ...\geq y_{n+1} 成立，要么有 x_1\leq x_2\leq ...\leq x_{n+1} 且 y_1\leq y_2\leq ...\leq y_{n+1} 成立。

6、求：在边长为 1 的正三角形中至少需要放多少个点才能使得必定存在两点，之间的距离不大于 \frac{1}{n} ？

7、证明：对于任意正整数 n ，总是存在它的一个倍数，使得这个倍数仅由数字 0,7 组成。（如： 4|7700,5|70 ）

8、证明：任意选取 n+2 个正整数，总是存在两个正整数，要么其差被 2n 整除要么其和被 2n 整除。

9、证明：任意一组人中总存在两个人，他们在这组人中认识的人的个数恰好相等。（假设认识是一种具有对称性的关系）

10、求在平面上至少需要取多少个格点，才能保证必定存在三个格点，其重心仍旧为格点？

11、证明： (m,n)=1 ，且 0\leq a\leq m-1,0\leq b\leq n-1 ，则必定存在 x ，使得 x\equiv a\ (mod\ m),x\equiv b\ (mod\ n) 。（中国剩余定理）

12、证明： \forall \alpha\in \mathbb{R},n\in \mathbb{N},\exists p,q\in \mathbb{N} 使得 1\leq q\leq n,|\alpha -\frac{p}{q}|k\geq 3,R(k,k)>2^{\frac{k}{2}} 必定成立。

14、（1）：证明：平面内任意 5 点无 3 点共线，则必定存在一个凸四边形。

（2）：证明：平面上的 m 个点无 3 点共线且任意 4 个点为凸四边形顶点，则这 m 个点必构成凸 m 边形。

（3）：证明：任意正整数 m\geq 3 ，存在正整数 N(m) ，使得 n\geq N(m) 时，若 n 个点中无 3 点共线，则必定存在凸 m 边形。

15、证明： \forall k,\exists m ，使得任一函数 f:\left \{ 1,2,...,m \right \}\rightarrow \left \{ y_1,...,y_k \right \} ，存在 y_i ，使得 \exists a,b,c\in f^{-1}(y_i),a+b=c 。（Schur定理）

提示或解答：

1、提示：

模仿前面的单调子序列例题证明

假设最长链长度不超过 m ，构造一个函数 f ，其定义域中元素为以 a_i 作为开头的最长链长度，像集合为 \left \{ 1,2,...,m \right \} ，则必定存在 \left \lceil \frac{mn+1}{m}\right \rceil=n+1 个元素像相同，可证明这 n+1 个元素必定为反链。

2、提示：

利用习题1，注意到整除为正整数集合上的偏序关系

3、提示：

利用相邻元素必定互素的性质进行分为 n 组 \left \{ 1,2 \right \},\left \{ 3,4\right \},...,\left \{ 2n-1,2n\right \}

则必定存在两个元素在同一组中，得证

分组归类是证明组合存在性的一个重要手段！

4、提示：

注意到任意正整数可以被写为 n=2^kl 的形式，其中 l 为奇数

5、提示：

先对于 x 坐标进行升序排列后再利用单调子序列的结论即可

（化高维问题为低维）

6、解答：

将边长为 1 的正三角形分解为若干个边长为 \frac{1}{n} 的正三角形

则第一层有 1 个正三角形，第二层 3 个，直到第 n 层有 2n-1 个

1+3+5+...+2n-1=n^2

显然如果只有 n^2 个点，则可以在每个小三角形内部取一个点，则不满足题目条件

而如果有 n^2+1 个点，则必定有两个点在同一个小三角形内部或边界上，满足条件

7、解答：

考虑只含有 0,7 的数字的生成方式，我们发现数字 0 事实上可以通过两个 7 相减而生成（如 707=777-77+7,\ 770=777-7 ）

那么我们不妨构造一个序列 a_n ，使得 a_i=77...7 （共有 i 个 7 ）

考虑每一项除以 n 所得余数 r_1,r_2,...,r_n

若 r_i=0,n|a_i 得证

则不妨假设余数取值在 1,2,...,n-1 中

则必定存在 r_i\equiv r_j(mod\ n),i

因此我们可以将这三点视作固定的而去变化另外两个点的取法来组成不同的 A

但是无论剩下两个点如何选取，总是存在 A 中三个点使得其重心为格点。

因此我们证明了 n\leq 9 。

故至少需要 9 个点保证条件成立。

11、提示：

考虑 mod\ n 完全剩余系 a,m+a,...,(n-1)m+a

由于 (m,n)=1 ，导致这个完全剩余系中数除以 n 余数互不相同，故必存在一个数除以 n 余数为 b

12、解答：

我们从结论逆向地思考如何利用抽屉原理进行构造。

我们需要证明 |q\alpha -p|