概述

组合数学研究的是：如何对对象的组合进行计数，通常的目标是为了高效地计算出组合的个数，而不用单独生成每一个组合。

例如，考虑将一个正整数 $n$ 拆分成 $\le n$ 的正整数的和的方法个数（不同顺序视作不同方法），例如，对于4来说，有8种方法：

1+1+1+1
1+1+2
1+2+1
2+1+1
1+3
2+2
3+1
4

组合问题往往能够使用递归函数解决，例如上述问题，我们可以使用 $f(n)$ 来代表拆分方法的个数，例如 $f(4)=8$ ， $f(n)$ 可以使用如下公式递归计算得到

$f(n)= \left\{ \begin{array}{lr} 1 , & n=1 \\ 1+f(1)+...+f(n-1) , & n\gt 1 \end{array} \right.$

上述公式的含义是，如果选 $k$ 作为第一个数，则剩下有 $f(n-k)$ 种拆分方法。

有时候，递归的公式有闭合形式的表示方式，例如该问题的闭合形式为 $f(n)=2^{n-1}$ ，因为 $n$ 个 $1$ 之间有 $n-1$ 个位置可以选择放 $+$ 号或者不放，没有 $+$ 号分割的 $1$ 连起来作为一个单独的正整数

二项式系数 Binomial coefficients

二项式系数 $\binom{n}{k}$ 的值等于从 $n$ 个元素的集合中选取 $k$ 个元素的子集的方法数。例如 $\binom{5}{3}=10$ ，因为从集合 ${1,2,3,4,5}$ 种选取 $3$ 个元素的子集共有 $10$ 种方法： $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\}$

公式1

二项式系数可以通过以下公式递归计算：

$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$

这个公式的直观解释是：从 $n$ 个元素中选 $k$ 个元素，可以分为两种情况：1.选 $x$ ，然后从剩下的 $n-1$ 个元素中选 $k-1$ 个元素，2.不选 $x$ ，然后从剩下的 $n-1$ 个元素中选 $k$ 个元素

上述递归公式的基值为：

$\binom{n}{0}=\binom{n}{n}=1$

因为总是有1种方法一个都不选，即空集 $\{\}$ ，同样的，总是有1种方法选取集合中的所有元素

公式2

另一种计算二项式系数的方式：

$\binom{n}{k}=\frac{n!}{k!(n-k)!}$

这个公式的解释是： $n$ 个元素的排列个数是 $n!$ ，选择前 $k$ 个元素，而前选择前 $k$ 个元素的情况下，前 $k$ 个元素和后 $n-k$ 个元素的顺序没有影响，因此，除以 $k!$ 和 $(n-k)!$ 即为结果

性质

$\binom{n}{k}=\binom{n}{n-k}$

因为从 $n$ 个元素中选择 $k$ 个，剩下的元素个数即为 $n-k$ 个，所以它们可以看成是同一种情况

二项式系数的和：

$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}=2^n$

二项式系数这个名称的由来，可以从二项式 $(a+b)$ 的 $n$ 次方的展开看出来：

$(a+b)^n=\binom{n}{0}a^nb^0+\binom{n}{1}a^{n-1}b^1+...+\binom{n}{n-1}a^1b^{n-1}+\binom{n}{n}a^0b^n$

二项式系数也出现在杨辉三角中（帕斯卡三角），在杨辉三角中可以很明显观察到公式一的模式： $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$

$\begin{array}{ccc} n=0| & 1 \\ n=1| & 1 & 1 \\ n=2| & 1 & 2 & 1 \\ n=3| & 1 & 3 & 3 & 1 \\ n=4| & 1 & 4 & 6 & 4 & 1 \\ ... & ... & ... & ... & ... & ... \\ \end{array}$

盒子和球问题

盒子和球是一个非常有用的模型，我们对将k个球放到n个盒子中的方法进行计数，我们考虑3中场景

场景1: 每个盒子最多只能放一个球，例如n=5，k=2的时候，一共有10种情况，这种情况下答案就直接是二项式系数 $\binom{n}{k}$

场景2: 每个盒子中可以放多个球，例如n=5，k=2的时候，一共有15种情况

我们可以使用包含”o”和”→”的字符串来表示对应的方案，刚开始，假设我们处于最左边的盒子，”o”表示我们把一颗球放到当前的盒子中，”→”表示我们移动到右边的盒子，我们一共有k个球，最多可以移动n-1次，因此方案数为： $\binom{k+n-1}{k}$

场景3: 每个盒子最多只能放一个球，且相邻的盒子不能都有球，即有球的盒子之间至少要有一个空盒子，例如n=5，k=2的时候，共有6种情况（ $n-2k+1>=0$ 时才有可能，否则方法数为0）

我们可以这样思考，有k个球，放到k个盒子中，且k个有球的盒子之间都有一个空盒子，共k-1个空盒子，现在还剩余n-2k+1个空盒子，需要插入到k个有球的盒子之间，相当于从k+1个位置中，可以连续的选取n-2k+1个位置，相当于场景2，因此方案数为： $\binom{n-k+1}{n-2k+1}$

也可以这样思考，除了最左边的第1个球以外，剩余的k-1个球，左边必定有一个空盒子，这k-1个球和左边的空盒子如果考虑成1个球，则相当于从n-(k-1)=n-k+1个位置中选取k个位置，相当于场景1，因此方案数为： $\binom{n-k+1}{k}=\binom{n-k+1}{n-2k+1}$

多项式系数

多项式系数可以看作是二项式系数的一般化，相当于将 $n$ 个元素，划分为大小分别为 $k_1,k_2,...,k_m$ 的子集， $k_1+k_2+...+k_m=n$ ，如果 $m=2$ ，则下述公式就相当于是二项式系数公式。

$\binom{n}{k_1,k_2,...,k_m}=\frac{n!}{k_1!k_2!...k_m!}$

220/300

例题

1. (IMO ShortList 1987-P17) A four-coloring of the set M

问题来源：https://artofproblemsolving.com/community/c6h362771p1989408

问题描述：有一个整数集合 $M=\{1,2,...,1987\}$ ，用4种颜色对集合进行着色（集合中的每个数都可以是这4种颜色中的一种），证明至少存在一种着色方法，使得集合中所有长度为10的等差数列，都至少有2种颜色，也就是说集合中不存在长度为10的等差数列只有一种颜色

证明：长度为10的等差数列中，任意的着色方法一共有 $4^{10}$ 种，其中4种是10个数颜色都是相同颜色的着色方法，因此，长度为10的等差数列只有一种颜色的概率为 $\frac{4}{4^{10}}=\frac{1}{4^9}$ ；

设 $M$ 中长度为10的等差数列一共有 $A$ 个，长度为10的等差数列只有一种颜色的数列个数的期望是 $E_1=\frac{A}{4^9}$ ，因为只有一种颜色的等差数列的个数只能是整数，所以如果 $E_1<1$ ，则说明存在概率使得只有一种颜色的等差数列的个数为 $0$ ；

现在来求 $A$ 的个数，设等差数列的第一个数为 $k$ ，则该数列的间隔 $d$ 的范围是： $1\le d\le \frac{1987-k}{9}$ ，即如果等差数列的第一个数是 $k$ ，则 $d$ 有 $\frac{1987-k}{9}$ 种值可取，因此 $A=\sum_{k=1}^{1987-9}\left \lfloor \frac{1987-k}{9}\right \rfloor=\sum_{k=1}^{1978}\left \lfloor \frac{1987-k}{9}\right \rfloor<\frac{1986+1985+...+9}{9}=\frac{(9+1986)*1978/2}{9}=\frac{1978*1995}{18}=219,228\frac{1}{3}<4^9=262,144$ ，因此 $E_1<1$ ，存在概率使得只有一种颜色的等差数列的个数为 $0$ ，也就是说存在着色方法使得集合中不存在长度为10的等差数列只有一种颜色