多项式组合

其他组合数

在掌握了二项式定理和基本组合恒等式之后，我们来学习几种进阶的计数方法和原理。它们在竞赛数学和离散数学中有广泛应用。

多重集

多重集（或称可重集）是集合概念的推广。在普通集合中，相同的元素只能出现一次，因此只能表现出「有或无」的属性；而在多重集中，同一个元素可以出现多次，因此可以表现出元素的个数。

我们将其表示为：

\{a_1,a_1,\dots,a_1,a_2,\dots\}

为简便起见，下文采用如下简记法：

\{n_1\cdot a_1,n_2\cdot a_2,\dots\}

多重集 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\} 的全排列个数为：

{n\choose n_1,n_2,\dots,n_k}={n!\over\prod_{1\le i\le k}n_i!}

这个全排列数被称为多重集的排列数，也常被称为多重组合数。容易注意到：

{m\choose n_1,n_2}={m\choose n_1}

在 n_1+n_2+\dots=n 的情形下，其直观意义就是：从 n 个元素中，先选出 n_1 个，再选出 n_2 个，依此类推。

也就是说，当 n_1+n_2+n_3=n 时，我们有弱化的等价形式：

{n\choose n_1,n_2,n_3}={n\choose n_1}{n-n_1\choose n_2}{n-n_1-n_2\choose n_3}

请注意区分下标之和是否为 n 的情形。例如：

{6\choose 2,2,2}

是合法的多重集排列数（因为 2+2+2=6），而：

{6\choose 2,2}

则不符合上述「下标之和为 n」的要求，两者含义不同。

请注意区分多重组合数（多重集的排列数）和多重集的组合数，它们是完全不同的概念。比组合数以及多重集的排列数，我们定义如。

设有多重集 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}，对于整数 r：若 r \le n_i 对所有 i \in [1,k] 成立（这个条件很重要），则从 S 中选择 r 个元素组成一个多重集的方案数就是多重集的组合数。

这个问题等价于求 x_1+x_2+\dots+x_k=r 的非负整数解的数目，可以用插板法解决，答案为：

{r+k-1\choose k-1}

若 r 满足 r < n，其中 n=\sum_{i=1}^k n_i（即没有单个元素的数量限制），则问题可以转化为求解带限制的线性方程：

\forall i\in[1,k],x_i\le n_i,\sum_{i=1}^k x_i=r

这种情况较为复杂，此处不再展开讨论。

圆排列

定义 n 个人全部围成一圈，所有排列数记为 Q(n,n)。

考虑一圈已经排好的人，从不同位置断开会变成不同的队列，因此：

Q(n,n)={A(n,n)\over n}={n!\over n}=(n-1)!

我们继续推广，Q(n,m) 为 n 个人中选 m 个人排成一圈的方案数。考虑先分组再分配的思路：

Q(n,m)=C(n,m)Q(m,m)={C(n,m)A(m,m)\over m}={A(n,m)\over m}

易得：

Q(n,m)={A(n,m)\over m}={n!\over m(n-m)!}

错位排列

错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于 1\sim n 的排列 P，如果满足 P_i\neq i，则称 P 是 n 的错位排列。

例如，三元错位排列有 \{2,3,1\} 和 \{3,1,2\}。四元错位排列有 \{2,1,4,3\}、\{2,3,4,1\}、\{2,4,1,3\}、\{3,1,4,2\}、\{3,4,1,2\}、\{3,4,2,1\}、\{4,1,2,3\}、\{4,3,1,2\} 和 \{4,3,2,1\}。错位排列是没有不动点的排列，即没有长度为 1 的循环。

把错位排列问题具体化，考虑这样一个问题：n 封不同的信，编号分别是 1,2,3,4,5，现在要把这五封信放在编号 1,2,3,4,5 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

假设考虑到第 n 个信封，初始时暂时把第 n 封信放在第 n 个信封中，然后考虑两种情况的递推：

• 前面 n-1 个信封全部装错；
• 前面 n-1 个信封有一个没有装错其余全部装错。

对于第一种情况，前面 n-1 个信封全部装错：因为前面 n-1 个已经全部装错了，所以第 n 封只需要与前面任一一个位置交换即可，总共有 D_{n-1}\times (n-1) 种情况。

对于第二种情况，前面 n-1 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 n-1 个信封中如果有一个没装错，那么把那个没装错的与 n 交换，即可得到一个全错位排列情况。

其他情况，不可能通过一次操作来把它变成一个长度为 n 的错排。

于是可得，错位排列数满足递推关系：

D_n=(n-1)(D_{n-1}+D_{n-2})

这里也给出另一个递推关系：

D_n=nD_{n-1}+{(-1)}^n

错位排列数有一个简单的取整表达式，增长速度与阶乘仅相差常数：

D_n=\left\lfloor\frac{n!}{\mathrm{e}} + \frac{1}{2}\right\rfloor

随着元素数量的增加，形成错位排列的概率 P 接近：

P=\lim_{n\to\infty}\frac{D_n}{n!}=\frac{1}{\mathrm{e}}

D_n 有如下封闭形式：

D_n=n!\sum_{k=0}^n{(-1)^k\over k!}

以及递推式：

D_n=(n-1)(D_{n-1}+D_{n-2})

以下是递推式的一个直观推导：假定第 n 个元素先放在位置 n。

1. 若前面 n-1 个元素已经形成错位排列，那么随便找一个元素与第 n 个交换即可满足要求，方案数为 (n-1)D_{n-1}。

2. 若前面 n-1 个元素中恰好有一个元素未错位，那么与这个元素交换即可满足条件，方案数为 (n-1)D_{n-2}。

因此总方案数为 D_n=(n-1)(D_{n-1}+D_{n-2})。可以证明，不存在其他一步之内的构造方案。

错位排列还有一个关于概率的有趣性质。设 P_n 表示随机排列为错位排列的概率，即：

P_n={D_n\over A(n,n)}={D_n\over n!}

则有：

\lim_{n\to\infty}P_n={1\over e}

等价地表述为：

P=\lim_{n\to\infty}{D_n\over n!}={1\over e}

由此可以得到 D_n 的近似计算公式：

D_n=\left\lfloor{n!\over e}\right\rfloor

卡特兰数

卡特兰数可以表示一类重要的组合问题。

典型情景包括：

• 如上图所示，从左下走到右上，不穿过对角线的方案数。

• 有 n 个元素（编号 1 \sim n），出入栈的方案数。

在上述路径问题中，容易知道不考虑限制的方案数为：

{2n\choose n}

对于不合法的情况（即穿越对角线的路径），我们观察到：把路径从第一次穿越对角线处开始翻折，终点一定落在目标位置的左上角。因此不合法方案数为：

{2n\choose n+1}

总方案数（即卡特兰数）为：

\boxed{C_n={2n\choose n}-{2n\choose n+1}}

我们可以继续推导，得到卡特兰数的经典公式：

\begin{aligned} C_n&={2n\choose n}-{2n\choose n+1}\\ &={(2n)!\over n!n!}-{(2n)!\over (n+1)!(n-1)!}\\ &={(2n)!\over n!n!}-{(2n)!\over n!n!}\cdot{n\over n+1}\\ &={1\over n+1}\cdot{(2n)!\over n!n!}\\ &={1\over n+1}{2n\choose n} \end{aligned}

即经典公式：

\boxed{C_n={1\over n+1}{2n\choose n}}

此外，卡特兰数还满足递推关系：

C_n=C_{n-1}\cdot{4n-2\over n+1}

卡特兰数列的前几项为（A000108 - OEIS）：

1, 1, 2, 5, 14, 42, 132,\dots

表示 2n 步中选择 n 步向上走。

考虑路径计数问题。这是典型的格路计数问题，可以通过反射原理求解。具体到本问题，考虑用总路径数目减去不合法的路径数目。总路径数一共要走 2n 步，其中 n 步向右，所以方案数为 \dbinom{2n}{n}。一条路径不合法，当且仅当它碰到了直线 y = x+1。对于任意一条非法路径，可以找到第一次碰到直线 y = x+1 的位置，并将该位置之后的路径关于直线 y=x+1 做对称。此时，可以发现，一条从 (0,0) 到 (n,n) 的非法路径，变成了一条从 (0,0) 到 (n-1,n+1) 的路径。

由于从 (0,0) 到 (n-1,n+1) 的路径必定要穿过直线 y = x+1，所以每条这样的路径都对应一条从 (0,0) 到 (n,n) 的非法路径。类似总路径数的计算，非法路径数目的总数就是 \dbinom{2n}{n+1}。因此，合法路径的总数为

C_n = \binom{2n}{n} - \binom{2n}{n+1}.

这就是 Catalan 数的表达式。

斯特林数

第二类斯特林数（斯特林子集数）\begin{Bmatrix}n\\ k\end{Bmatrix}，也可记做 S(n,k)，表示将 n 个两两不同的元素，划分为 k 个互不区分的非空子集的方案数。虽然被称作「第二类」，第二类斯特林数却在斯特林的相关著作和具体数学中被首先描述，同时也比第一类斯特林数常用得多。

递推公式：

\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix}

边界是 \begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]。

考虑用组合意义来证明。我们插入一个新元素时，有两种方案：

• 将新元素单独放入一个子集，有 \begin{Bmatrix}n-1\\ k-1\end{Bmatrix} 种方案；
• 将新元素放入一个现有的非空子集，有 k\begin{Bmatrix}n-1\\ k\end{Bmatrix} 种方案。

根据加法原理，将两式相加即可得到递推式。

通项公式：

\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!}

使用容斥原理证明该公式。设将 n 个两两不同的元素，划分到 i 个两两不同的集合（允许空集）的方案数为 G_i，将 n 个两两不同的元素，划分到 i 个两两不同的非空集合（不允许空集）的方案数为 F_i。

显然

\begin{aligned} G_i&=i^n\\ G_i&=\sum\limits_{j=0}^i\binom{i}{j}F_j \end{aligned}

根据二项式反演

\begin{aligned} F_i&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}G_j\\ &=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}j^n\\ &=\sum\limits_{j=0}^{i}\dfrac{i!(-1)^{i-j}j^n}{j!(i-j)!} \end{aligned}

考虑 F_i 与 \begin{Bmatrix}n\\i\end{Bmatrix} 的关系。第二类斯特林数要求集合之间互不区分，因此 F_i 正好就是 \begin{Bmatrix}n\\i\end{Bmatrix} 的 i! 倍。于是

\begin{Bmatrix}n\\m\end{Bmatrix}=\dfrac{F_m}{m!}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!}

第一类斯特林数（斯特林轮换数）\begin{bmatrix}n\\ k\end{bmatrix}，也可记做 s(n,k)，表示将 n 个两两不同的元素，划分为 k 个互不区分的非空轮换的方案数。

一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换 [A,B,C,D]，并且我们认为 [A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]，即，两个可以通过旋转而互相得到的轮换是等价的。注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 [A,B,C,D]\neq[D,C,B,A]。

递推公式：

\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}

边界是 \begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]。

该递推式的证明可以考虑其组合意义。我们插入一个新元素时，有两种方案：

• 将该新元素置于一个单独的轮换中，共有 \begin{bmatrix}n-1\\ k-1\end{bmatrix} 种方案；
• 将该元素插入到任何一个现有的轮换中，共有 (n-1)\begin{bmatrix}n-1\\ k\end{bmatrix} 种方案。

根据加法原理，将两式相加即可得到递推式。

通项公式：第一类斯特林数没有实用的通项公式。

贝尔数

贝尔数 B_n 以埃里克·坦普尔·贝尔命名，是组合数学中的一组整数数列，开首是（OEIS A000110）：

B_0 = 1,B_1 = 1,B_2=2,B_3=5,B_4=15,B_5=52,B_6=203,\dots

B_n 是基数为 n 的集合的划分方法的数目。集合 S 的一个划分是定义为 S 的两两不相交的非空子集的族，它们的并是 S。例如 B_3 = 5 因为 3 个元素的集合 {a, b, c} 有 5 种不同的划分方法：

\begin{aligned} &\{ \{a\},\{b\},\{c\}\} \\ &\{ \{a\},\{b,c\}\} \\ &\{ \{b\},\{a,c\}\} \\ &\{ \{c\},\{a,b\}\} \\ &\{ \{a,b,c\}\} \\ \end{aligned}

B_0 是 1 因为空集正好有 1 种划分方法。

贝尔数适合递推公式：

B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_{k}

证明：

B_{n+1} 是含有 n+1 个元素集合的划分个数，设 B_n 的集合为 \{b_1,b_2,b_3,\dots,b_n\}，B_{n+1} 的集合为 \{b_1,b_2,b_3,\dots,b_n,b_{n+1}\}，那么可以认为 B_{n+1} 是有 B_{n} 增添了一个 b_{n+1} 而产生的，考虑元素 b_{n+1}。

• 假如它被单独分到一类，那么还剩下 n 个元素，这种情况下划分数为 \dbinom{n}{n}B_{n};

• 假如它和某 1 个元素分到一类，那么还剩下 n-1 个元素，这种情况下划分数为 \dbinom{n}{n-1}B_{n-1}；

• 假如它和某 2 个元素分到一类，那么还剩下 n-2 个元素，这种情况下划分数为 \dbinom{n}{n-2}B_{n-2}；

• ……

以此类推就得到了上面的公式。

每个贝尔数都是相应的第二类斯特林数的和。因为第二类斯特林数是把基数为 n 的集合划分为正好 k 个非空集的方法数目。

B_{n} = \sum_{k=0}^n{n\brace k}

用以下方法构造一个三角矩阵（形式类似杨辉三角形）：

• a_{0,0} = 1；
• 对于 n \ge 1，第 n 行首项等于上一行的末项，即 a_{n,0}=a_{n-1,n-1}；
• 对于 m,n \ge 1，第 n 行第 m 项等于它左边和左上角两个数之和，即 a_{n,m}=a_{n,m-1}+a_{n-1,m-1}。

部分结果如下：

\begin{aligned} & 1 \\ & 1\quad\qquad 2 \\ & 2\quad\qquad 3\quad\qquad 5 \\ & 5\quad\qquad 7\quad\qquad 10\,\,\,\qquad 15 \\ & 15\,\,\,\qquad 20\,\,\,\qquad 27\,\,\,\qquad 37\,\,\,\qquad 52 \\ & 52\,\,\,\qquad 67\,\,\,\qquad 87\,\,\,\qquad 114\qquad 151\qquad 203\\ & 203\qquad 255\qquad 322\qquad 409\qquad 523\qquad 674\qquad 877 \\ \end{aligned}

每行的首项是贝尔数。可以利用这个三角形来递推求出贝尔数。

伯努利数

伯努利数 B_n 是一个与数论有密切关联的有理数序列。前几项被发现的伯努利数分别为：

B_0=1,B_1=-\frac{1}{2},B_2=\frac{1}{6},B_3=0,B_4=-\frac{1}{30},\dots

伯努利数是由雅各布·伯努利的名字命名的，他在研究 m 次幂和的公式时发现了奇妙的关系。我们记

S_{m}(n)=\sum_{k=0}^{n-1}k^m=0^m+1^m+\dots+(n-1)^m

伯努利观察了如下一列公式，勾画出一种模式：

\begin{aligned} S_0(n)&=n\\ S_1(n)&=\frac{1}{2}n^2-\frac{1}{2}n\\ S_2(n)&=\frac{1}{3}n^3-\frac{1}{2}n^2+\frac{1}{6}n\\ S_3(n)&=\frac{1}{4}n^4-\frac{1}{2}n^3+\frac{1}{4}n^2\\ S_4(n)&=\frac{1}{5}n^5-\frac{1}{2}n^4+\frac{1}{3}n^3-\frac{1}{30}n \end{aligned}

可以发现，在 S_m(n) 中 n^{m+1} 的系数总是 \frac{1}{m+1}，n^m 的系数总是 -\frac{1}{2}，n^{m-1} 的系数总是 \frac{m}{12}，n^{m-3} 的系数是 -\frac{m(m-1)(m-2)}{720}，n^{m-4} 的系数总是零等。

而 n^{m-k} 的系数总是某个常数乘以 m^{\underline{k}}，m^{\underline{k}} 表示下降阶乘幂，即 \frac{m!}{(m-k)!}。

递推公式：

\begin{aligned} S_m{(n)}&=\frac{1}{m+1}(B_0n^{m+1}+\binom{m+1}{1}B_1 n^m+\dots+\binom{m+1}{m}B_m n) \\ &=\frac{1}{m+1}\sum_{k=0}^{m}\binom{m+1}{k}B_kn^{m+1-k} \end{aligned}

伯努利数由隐含的递推关系定义：

\begin{aligned} \sum_{j=0}^{m}\binom{m+1}{j}B_j&=0,(m>0)\\ B_0&=1 \end{aligned}

例如，\binom{2}{0}B_0+\binom{2}{1}B_1=0，前几个值显然是

证明较为复杂，此处省略。

恩特林格数

恩特林格数（Entringer number，OEIS A008281）E(n,k) 是满足下述条件的 0 到 n 共 n+1 个数的置换数目：

• 首元素是 k；
• 首元素的下一个元素比首元素小，再下一个元素比前一个元素大，再下一个元素比前一个元素小……后面相邻元素的大小关系均满足这样的规则。

恩特林格数的初值有：

E(0,0)=1

E(n,0)=0

有递推关系：

E(n,k)=E(n,k-1)+E(n-1,n-k)

恩特林格数的一个适当排列的数字三角，称为 Seidel–Entringer–Arnold 三角（Seidel–Entringer–Arnold triangle，OEIS A008280）。该三角是按照「牛耕」顺序（ox-plowing order）排列的恩特林格数 E_(n,k)：

\begin{aligned} & E(0,0) \\ & E(1,0) \rightarrow E(1,1) \\ & E(2,2) \leftarrow E(2,1) \leftarrow E(2,0) \\ & E(3,0) \rightarrow E(3,1) \rightarrow E(3,2) \rightarrow E(3,3) \\ & E(4,4) \leftarrow E(4,3) \leftarrow E(4,2) \leftarrow E(4,1) \leftarrow E(4,0) \end{aligned}

即：

\begin{aligned} & 1 \\ & 0 \rightarrow 1 \\ & 1 \leftarrow 1 \leftarrow 0 \\ & 0 \rightarrow 1 \rightarrow 2 \rightarrow 2 \\ & 5 \leftarrow 5 \leftarrow 4 \leftarrow 2 \leftarrow 0 \end{aligned}

按照这种方式排列的恩特林格数的优势是，与它的递推关系 E(n,k)=E(n,k-1)+E(n-1,n-k) 一致，可以方便记忆和理解。

欧拉数

在计算组合中，欧拉数（Eulerian Number）是从 1 到 n 中正好满足 m 个元素大于前一个元素（具有 m 个「上升」的排列）条件的排列 个数。定义为：

A(n, m) = \left\langle \begin{matrix} n\\ m - 1 \end{matrix} \right\rangle

例如，从数字 1 到 3 一共有 4 种排列使得恰好有一个元素比前一个元素大：

所以按照 A(n, m) 定义：如果 n 等于 3，m 等于 1，欧拉数值为 4，表示共有 4 个有 1 个元素大于前一个元素的排列。

对于 n 和 m 值比较小的欧拉数来说，我们可以直接得到结果：

可以通过递推或者递归的方法计算欧拉数。

首先，当 m \ge n 或 n = 0 时，没有满足条件的排列，即此时欧拉数为 0。

其次，当 m = 0 时，只有降序的排列满足条件，即此时欧拉数为 1。

最后，考虑在 n-1 的排列的基础上插入 n 从而得到 n 的排列，由于插入 n 至多使欧拉数增加 1，所以 A(n, m) 可以仅从 A(n-1, m-1) 处和 A(n-1, m) 处转移得到。

考虑 n 插入的位置：当 p_{i-1} < p_{i} 时，若将 n 插到 p_{i} 之前，即将 n 插入到「上升」中，排列的欧拉数不变；此外，将 n 插在排列之前，排列的欧拉数也不变；否则，若将 n 插到其余位置，排列的欧拉数增加 1。

考虑从 A(n-1, m-1) 转移到 A(n, m)，此时需要使欧拉数增加 1，此时不能将 n 插在「上升」中或者排列开头，共有 n - (m-1) - 1 = n-m 种方案。

考虑从 A(n-1, m) 转移到 A(n, m)，此时需要欧拉数保持不变，只能将 n 插在「上升」中或者排列开头，共 m+1 种方案。

综上所述，有

A(n, m) = \begin{cases} 0, & m > n \text{ or } n = 0, \\ 1, & m = 0, \\ (n-m) \cdot A(n-1, m-1) + (m+1) \cdot A(n-1, m), & \text{otherwise}. \end{cases}

分拆数

分拆：将自然数 n 写成递降正整数和的表示。

n=r_1+r_2+\ldots+r_k \quad r_1 \ge r_2 \ge \ldots \ge r_k \ge 1

和式中每个正整数称为一个部分。

分拆数：p_n。自然数 n 的分拆方法数。

自 0 开始的分拆数：

将 n 分成恰有 k 个部分的分拆，称为 k 部分拆数，记作 p(n,k)。

显然，k 部分拆数 p(n,k) 同时也是下面方程的解数：

n-k=y_1+y_2+\ldots+y_k\quad y_1\ge y_2\ge\ldots\ge y_k\ge 0

如果这个方程里面恰有 j 个部分非 0，则恰有 p(n-k,j) 个解。因此有和式：

p(n,k)=\sum_{j=0}^k p(n-k,j)

相邻两个和式作差，得：

p(n,k)=p(n-1,k-1)+p(n-k,k)

如果列出表格，每个格里的数，等于左上方的数，加上该格向上方数，所在列数个格子中的数。

由等比数列求和公式，有：

\frac{1}{1-x^k}=1+x^k+x^{2k}+x^{3k}+\ldots

1+p_1 x+p_2 x^2+p_3 x^3+\ldots=\frac{1}{1-x} \frac{1}{1-x^2} \frac{1}{1-x^3}\ldots

对于 k 部分拆数，生成函数稍微复杂。具体写出如下：

\sum_{n,k=0}^\infty {p(n,k) x^n y^k }=\frac{1}{1-xy} \frac{1}{1-x^2 y} \frac{1}{1-x^3 y}\ldots

互异分拆数：pd_n。自然数 n 的各部分互不相同的分拆方法数。（Different）

同样地，定义互异 k 部分拆数 pd(n,k)，表示最大拆出 k 个部分的互异分拆，是这个方程的解数：

n=r_1+r_2+\ldots+r_k\quad r_1>r_2>\ldots>r_k\ge 1

完全同上，也是这个方程的解数：

n-k=y_1+y_2+\ldots+y_k\quad y_1>y_2>\ldots>y_k\ge 0

这里与上面不同的是，由于互异，新方程中至多只有一个部分为零。有不变的结论：恰有 j 个部分非 0，则恰有 pd(n-k,j) 个解，这里 j 只取 k 或 k-1。因此直接得到递推：

pd(n,k)=pd(n-k,k-1)+pd(n-k,k)

同样像组合数一样列出表格，每个格里的数，等于该格前一列上数，所在列数个格子中的数，加上该格向上方数，所在列数个格子中的数。

组合数大型运算推导

下面我们讨论若干组合恒等式的证明。默认 n 是任意自然数，一般 k\le n。

范德蒙德卷积

范德蒙德卷积是一种合并组合数的式子，主要应用于组合数学的公式推导。

\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}

考虑用二项式定理证明：

\begin{aligned} \sum_{k=0}^{n+m}\binom{n+m}{k}x^k&=(x+1)^{n+m}\\ &=(x+1)^n(x+1)^m\\ &=\sum_{r=0}^n\binom{n}{r}x^r\sum_{s=0}^m\binom{m}{s}x^s\\ &=\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}x^k\\ \end{aligned}

即有：

\binom{n+m}{k}=\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}

若考虑其组合意义证明：

在一个大小为 n+m 的集合中取出 k 个数，可以等于把大小为 n+m 的集合拆成两个集合，大小分别为 n 与 m，然后从 n 中取出 i 个数，从 m 中取出 k-i 个数的方案数。由于我们有了对于 i 的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。

推论 1 及证明：

\sum_{i=-r}^{s}\binom{n}{r+i}\binom{m}{s-i}=\binom{n+m}{r+s}

证明与原公式证明相似。

推论 2 及证明：

\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}

根据基础的组合数学知识推导，有：

\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\sum_{i=0}^{n-1}\binom{n}{i+1}\binom{n}{i}=\sum_{i=0}^{n-1}\binom{n}{n-1-i}\binom{n}{i}=\binom{2n}{n-1}

推论 3 及证明：

\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}

根据基础的组合数学知识推导，有：

\sum_{i=0}^n\binom{n}{i}^2=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\binom{2n}{n}

推论 4 及证明：

\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}

根据基础的组合数学知识推导，有：

\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\sum_{i=0}^m\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}

其中 \dbinom{n+m}{m} 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。

在一张网格图中，从 (0,0) 走到 (n,m) 共走 n+m 步。规定 (0,0) 位于网格图左上角，其中向下走了 n 步，向右走了 m 步，方案数为 \dbinom{n+m}{m}。

换个视角，我们将 n+m 步拆成两部分走，先走 n 步，再走 m 步，那么 n 步中若有 i 步向右，则 m 步中就有 m-i 步向右，故得证。

补充：范德蒙德卷积还可以用母函数来证明，注意到

(1+x)^{n}(1+x)^{m}=(1+x)^{n+m}

等号左边化简成

\begin{aligned} (1+x)^{n}(1+x)^{m}& =\left(\sum _{i=0}^{n}{\binom {n}{i}}x^{i}\right)\left(\sum _{j=0}^{m}{\binom {m}{j}}x^{j}\right)\\ &=\sum _{k=0}^{m+n}\left(\sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}\right)x^{k} \end{aligned}

等号右边则根据定义

(1+x)^{n+m}=\sum _{k=0}^{n+m}{\binom {n+m}{k}}x^{k}

比较 x^{k} 系数，可得

{\binom {n+m}{k}}=\sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}

例题一

证明：

\sum_{i=0}^k(-1)^i{n\choose i}=(-1)^k{n-1\choose k}

其中 n<k，且 n,k 都是正整数。

许多题解使用了数学归纳法，这里我们介绍一种更优雅的方法——扰动法（Perturbation Method）。

我们从恒等式出发，构造一个可以化简的求和式：

\begin{aligned} \sum_{i=0}^k(-1)^i{n\choose i}+(-1)^{k+1}{n\choose k+1}&=1+\sum_{i=0}^k(-1)^{i+1}{n\choose i+1}\\ &=1-\sum_{i=0}^k(-1)^i{n\choose i+1} \end{aligned}

接下来利用帕斯卡公式：

{n\choose i}+{n\choose i+1}={n+1\choose i+1}

将两个求和式合并，移项后得到：

\begin{aligned} \sum_{i=0}^k(-1)^i{n+1\choose i+1}&=1-(-1)^{k+1}{n\choose k+1}\\ \sum_{i=1}^{k+1}(-1)^{i-1}{n+1\choose i}&=1-(-1)^{k+1}{n\choose k+1}\\ \sum_{i=1}^{k+1}(-1)^i{n+1\choose i}&=-1+(-1)^{k+1}{n\choose k+1}\\ \sum_{i=0}^{k+1}(-1)^i{n+1\choose i}&=(-1)^{k+1}{n\choose k+1} \end{aligned}

最后令 n\gets n-1，k\gets k-1，得：

\sum_{i=0}^k(-1)^i{n\choose i}=(-1)^k{n-1\choose k}

得证。

例题二

证明：

\sum_{k=0}^n{1\over k+1}{n\choose k}={1\over n+1}(2^{n+1}-1)

我们首先对求和项进行变形：

{1\over k+1}{n\choose k}={n!\over(k+1)!(n-k)!}={1\over n+1}\cdot{n+1\choose k+1}

因此：

\sum_{k=0}^n{1\over k+1}{n\choose k}={1\over n+1}\sum_{k=0}^n{n+1\choose k+1}

令 t=n+1，右侧变为：

{1\over t}\sum_{k=1}^t{t\choose k}={1\over t}(2^t-1)

代回 t=n+1，即得：

\sum_{k=0}^n{1\over k+1}{n\choose k}={1\over n+1}(2^{n+1}-1)

例题三

证明：

\sum_{k=0}^n{(-1)^k\over k+1}{n\choose k}={1\over n+1}

根据上一题的推导思路，我们有：

\sum_{k=0}^n{(-1)^k\over k+1}{n\choose k}={1\over n+1}\sum_{k=0}^n(-1)^k{n+1\choose k+1}

令 t=n+1，右侧变为：

{1\over t}\sum_{k=1}^t(-1)^{k-1}{t\choose k}={1\over t}\left[\sum_{k=0}^t(-1)^{k-1}{t\choose k}\right]+{1\over t}

由二项式定理：

(a+1)^t=\sum_{k=0}^ta^k{t\choose k}

代入 a=-1，得：

\sum_{k=0}^t(-1)^k{t\choose k}=[t=0]

由于 t=n+1>0，因此上式为 0。于是：

\sum_{k=0}^n{(-1)^k\over k+1}{n\choose k}={1\over n+1}

十二重计数

十二重道

问题 将 n 个球放到 m 个盒子里，求方案数。

根据球和盒子是否可区分、每个盒子是否有容量限制，一共有十二种情况。我们逐一讨论。

I. 球不同，盒子不同，无其他限制

每个球可以放入 m 个盒子中的任意一个，因此答案为：

m^n

II. 球不同，盒子不同，每个盒子至多装一个球

若 n>m，则无解。

否则，相当于在 m 个盒子中选择 n 个来放球，并对球进行排列：

C(m,n)\times A(n,n)=A(m,n)=m^{\underline n}

这也可以理解为：先分组再分配，或者按顺序每个球的可行位置依次递减。

III. 球不同，盒子不同，每个盒子至少装一个球

利用容斥原理。我们先「强令」i 个盒子为空，其余盒子无限制，然后对 i 求和：

\sum_{i=0}^m(-1)^i{m\choose i}(m-i)^n

减去有空盒子的方案时会产生重复，因此需要容斥。

IV. 球不同，盒子相同，无其他限制

这是第二类斯特林数（按行计算），本文不详细讨论。

V. 球不同，盒子相同，每个盒子至多装一个球

答案用艾佛森括号表示为：

[n\le m]

即 n\le m 时答案为 1，否则为 0。

VI. 球不同，盒子相同，每个盒子至少装一个球

这是第二类斯特林数的基本应用，本文不详细讨论。

VII. 球相同，盒子不同，无其他限制

利用插板法，答案为：

{n+m-1\choose m-1}

VIII. 球相同，盒子不同，每个盒子至多装一个球

我们需要选出 n 个盒子来装球，其余盒子空着，答案为：

{m\choose n}

IX. 球相同，盒子不同，每个盒子至少装一个球

利用插板法，答案为：

{n-1\choose m-1}

X. 球相同，盒子相同，无其他限制

这是整数分划问题，本文不详细讨论。

XI. 球相同，盒子相同，每个盒子至多装一个球

与情况 V 相同，答案为：

[n\le m]

XII. 球相同，盒子相同，每个盒子至少装一个球

同为整数分划问题，本文不详细讨论。

球盒模型是组合计数中最经典的模型之一。我们根据球和盒子是否可区分、是否有容量限制等条件，系统地讨论各种情况。

注意：以下讨论默认不考虑无解的情况（即方案数为零时直接跳过）。