2020-11-18 16:58 已编辑天津大学 C++

关注

组合数学和斯特林数

写在前面的

本博客基本不会讲解如何运用组合数和斯特林数，应该偏向于数学证明，各类恒等式，我先咕一咕。

更新日志

11.17 基本的组合恒等式。
11.18 反演原理（很多反演放在后面讲解）。
11.18 第一类斯特林数。
11.18 第二类斯特林数。
11.18 二项式反演，斯特林反演。

定义

在未作特殊说明下。

$\delta(i,j)$ 在 $i=j$ 时，函数值为 $1$ ，其它的所有时候函数值都为 $0$ 。
${n\choose m}$ 表示组合数。
$\begin{Bmatrix}n\\m \end{Bmatrix}$ 表示第二类斯特林数。
$\begin{bmatrix}n\\m \end{bmatrix}$ 表示第一类斯特林数。
$x^{\overline{n}}$ 表示 $x$ 的 $n$ 阶上升幂，等价于 $x\times (x+1)\times ...\times (x+n-1)$ 。
$x^{\underline{n}}$ 表示 $x$ 的 $n$ 阶下降幂，等价于 $x\times (x-1)\times ...\times (x-n+1)$ 。
$\begin{Bmatrix}n\\m \end{Bmatrix}$ 表示第二类斯特林数。

组合数

${n \choose m}$ 表示从 $n$ 个有标号的元素中选出 $m$ 个物品， $m$ 个物品没有先后顺序。

${n\choose m} = {n\choose n-m}$ 全集中选择补集和直接选取的方案是等价的。
${n\choose m} = \frac{n!}{m!(n-m)!}$ 组合数的最基本的等式。考虑 $n$ 个元素的全排列，为 $n!$ ，我们固定选取前面的 $m$ 个，那么除以重复的排列，前面重复的次数为 $m!$ ，后面重复的次数为 $(n-m)!$ 。所以原式子得证。
${n\choose m} = {n - 1\choose m -1}+{n-1\choose m}$ 非常重要的等式，可以考虑组合意义。对于 ${n\choose m}$ 是 $n$ 选 $m$ 那么我们考虑第 $n$ 个元素是否选择，那么选择的方案为 $n-1$ 中选 $m-1$ 。不选的方案为 $n-1$ 中选 $m$ 个。
$(x+y)^n = \sum_{i=0}^n {n\choose i} x^i y^{n-i}$ 二项式定理。可以考虑数学归纳法证明。
- $n = 0$ 或 $n = 1$ 时，显然成立。
- $n>1$ 时
  $\begin{aligned}(x+y)^n &=(x+y)^{n-1}(x+y)\\&=(x+y)\sum_{i= 0}^{n-1}{n-1\choose i}x^{i}y^{n-1-i} \\&= \sum_{i=0}^{n-1}{n-1\choose i}x^{i+1}y^{n-i-1}+\sum_{i=0}^{n-1}{n-1\choose i}x^iy^{n-i}\end{aligned}$
- 然后我们把 $x^i$ 项合并，得到 $x^i$ 项的系数为 ${n-1\choose i-1}+{n-1\choose i}={n\choose i}$ 得证。
$\sum_{i=0}^{n}{n \choose i}=2^n$ 根据二项式定理就可以得到，取 $x=1,y=1$ 。
$\sum_{i=0}^{n}(-1)^i{n\choose i}=0$ 根据二项式定理就可以得到，取 $x=1,y=-1$ 。
$\sum_{i=0}^{n}{r\choose i}{s\choose n-i}={r+s\choose n}$ 范德蒙德卷积，按照组合意义是非常明确的，左边选 $x$ 个，右边选择 $n - x$ 个，其实等价于在总共中选择 $n$ 个。
这里考虑用二项式定理来证明。
$\begin{aligned} \sum_{n=0}^{r+s}{r + s \choose n} x^n&=(x+1)^{r+s} \\&= (x+1)^s(x+1)^r \\ &=\sum_{n=0}^{r+s}(\sum_{i=0}^r {r\choose i}{ s \choose n - i})x^n \end{aligned}$
然后系数相同就好了。
$\sum_{i=0}^n{n\choose i}^2 = {2n\choose n}$ 根据范德蒙德卷积。 $r=n,s=n$ 就好了。
$\sum_{i=0}^{n}i {n\choose i} = n\times 2^{n-1}$ 。这个可以通过组合意义证明，这个的组合意义为选取 $i$ 个元素，贡献为集合大小，那么我们考虑一个数的贡献为 $2^{n-1}$ 一共 $n$ 个数，所以答案为 $n\times 2^{n-1}$ 。
$\sum_{i=0}^{i}i^2 {n\choose i}= n(n+1)2^{n-2}$ 。证明方法很多，可以通过 $i^2={i\choose 2}2+i$ 再结合上式就可以做。或者直接考虑组合意义，贡献就是有顺序的选择两个数的方案，那么如果我们选择的两个数为 $a,b$ 。当 $a\not = b$ 贡献为 $(n-1)n$ ，如果 $a=b$ 则贡献为 $n$ ，两个相加 $n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}$ 。
$\sum_{i=0}^m{n+i\choose n}={n+m+1\choose n+1}$ 非常好用的公式，画图非常好理解。我们认为 ${n+m\choose n}$ 是从 $(0,0)$ 只能向右或者向上走一步，最后到 $(m,n)$ 的方案。而 $\sum_{i=0}^m{n+i\choose n}$ 这些点在坐标轴中画出来，是一条平行于 $y$ 轴的直线，那么串过这个直线的方案显然是等价于到达 $(m,n+1)$ 的方案，也就是 ${n+m+1\choose n+1}$ 。
${n\choose r}{r\choose m}={n\choose m}{n-m\choose r-m}$ 这个组合意义也比较显然，因为从 $n$ 个中选择 $r$ 个，再从 $r$ 中选 $m$ 个，等同于在 $n$ 中选 $m$ ，再在剩下中选 $r-m$ 个。证明可以暴力展开组合数。

$\begin{aligned}{n\choose r}{r\choose m}&=\frac{n!}{r!(n-r)!}\times \frac{r!}{m!(r-m)!}\\&= \frac{n!}{m!(n-m)!}\times\frac{(n-m)!}{(n-r)!(r-m)!}\\&={n\choose m}{n-m\choose r-m}\end{aligned}$

第一类斯特林数

$\begin{bmatrix}n\\m \end{bmatrix}$ 意义为， $n$ 个元素构成 $m$ 个环的方案数。

$\begin{bmatrix}n\\m \end{bmatrix}=\begin{bmatrix}n-1\\m-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m \end{bmatrix}$ 比较好理解的递推式。考虑第 $n$ 个元素是加入以前的环中，还是自己单独成一个环。
$n!=\sum_{i=0}^n\begin{bmatrix}n\\i \end{bmatrix}$ 组合意义还是比较明显的一个排列可以拆除一个置换，而 $\sum_{i=0}\begin{bmatrix}n\\i \end{bmatrix}$ 就表示了所有置换方案。考虑证明，还是通过数学归纳证明。
- $n=1$ 时，式子显然成立。
- $n>1$ 时。

$\begin{aligned}n!&=(n-1)!n \\&= n\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\i \end{bmatrix}\\&=\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\i \end{bmatrix} +(n-1)\sum_{i=1}^{n}\begin{bmatrix}n-1\\i-1 \end{bmatrix}\\&=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}\end{aligned}$

$x^{\underline{n}}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i} x^{i}$ 比较常见的式子，一般幂转下降幂。比较容易证明，还是考虑数学归纳法。
- 当 $n=1$ 时，显然成立。
- 当 $n>1$ 时，考虑归纳。

$\begin{aligned}x^{\underline{n+1}}&=x^{\underline{n}}(x-n)\\&=(\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^{i+1})-(n\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i)\\&= \sum_{i=1}^{n+1}(\begin{bmatrix}n\\i-1\end{bmatrix}+n\begin{bmatrix}n\\i \end{bmatrix})(-1)^{n-i+1}x^{i}\\&=\sum_{i=1}^{n+1}\begin{bmatrix}n+1\\i \end{bmatrix}(-1)^{n-i+1}x^i\end{aligned}$

第二类斯特林数

$\begin{Bmatrix}n\\m \end{Bmatrix}$ 表示 $n$ 个数中选出 $m$ 个非空集合的方案数。
$\begin{Bmatrix}n\\m \end{Bmatrix}=\begin{Bmatrix}n-1\\m-1 \end{Bmatrix}+m\begin{Bmatrix}n-1\\m \end{Bmatrix}$ 可以根据定义来理解。考虑第 $n$ 个数，要么加入 $m$ 个集合中的某一个，要么自己再开一个集合。
$n^m = \sum_{k=0}^m \begin{Bmatrix}m\\k\end{Bmatrix}{n\choose k}k!=\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}n^{\underline{k}}$ 。这个式子的组合意义比较明显。考虑 $m$ 个有标号的球放入有标号的 $n$ 个盒子中，那么总方案为 $n^m$ 。那么现在枚举一下不是空的的盒子。那么左右的方案数应该是一样的。所以上式子成立，如果不组合分析，我们可以考虑归纳法证明
- 当 $m=1$ 时显然成立。
- 当 $m>1$ 时

$\begin{aligned}\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}n^{\underline{k}} &=\sum_{k=0}^{m}\begin{Bmatrix}m-1\\k-1\end{Bmatrix}n^{\underline{k}}+\sum_{k=0}^{m}\begin{Bmatrix}m-1\\k \end{Bmatrix}kn^{\underline{k}}\\ &=\sum_{k=0}^{m-1}\begin{Bmatrix}m-1\\k\end{Bmatrix}n^{\underline{k+1}}+\sum_{k=0}^{m-1}\begin{Bmatrix}m-1\\k \end{Bmatrix}kn^{\underline{k}}\\ &= \sum_{k=0}^{m-1}(n-k)\begin{Bmatrix}m-1\\k\end{Bmatrix}n^{\underline{k}}+\sum_{k=0}^{m-1}\begin{Bmatrix}m-1\\k \end{Bmatrix}kn^{\underline{k}}\\ &= n^m \end{aligned}$

$\begin{Bmatrix}n\\m \end{Bmatrix} = \frac{1}{m!}\sum_{i=0}^{m} (-1)^i{m\choose i}(m-i)^n$ 。组合意义比较清晰，我们可以考虑容斥。枚举空盒子，剩下的球随便选择盒子，然后考虑选哪些就好了。如果要证明的话，通过上面的恒等式，结合二项式反演就可以了（大雾）。

反演

反演原理

我们现在有 $g(n)=\sum_{i=0}a(n,i)f(i)$ 。那么我们考虑要满足 $f(n)=\sum_{i=0}b(n,i)g(i)$ 。则 $b(n,i)$ 要满足什么条件。

$\begin{aligned}f(n)&=\sum_{i=0}^{n}b(n,i)g(i)\\&=\sum_{i=0}^nb(n,i)\sum_{j=0}^ia(i,j)f(j)\\&=\sum_{i=0}^nf(i)\sum_{j=i}^nb(n,j)a(j,i)\end{aligned}$

那么对于上式只要满足 $\sum_{j=i}^nb(n,j)a(j,i)=\delta (n,i)$ 即可。基本所有的反演都是基于这个性质的，同理只要某一个函数满足上式，就可以直接套用反演公式。

二项式反演

我们来证明一个东西。 $\sum_{i=m}^n (-1)^{i+m}{n\choose i}{i\choose m}=\delta(m,n)$ 。下面的推导用到了上面的组合恒等式和二项式定理。

$\begin{aligned}\sum_{i=m}^n (-1)^{i+m}{n\choose i}{i\choose m}&=\sum_{i=m}^n(-1)^{i+m}{n -m\choose i-m}{n\choose m}\\ &=\sum_{i=m}^n(-1)^{i+m}{n-m \choose n-i}{n\choose m}\\ &={n\choose m}(-1)^m \sum_{i=m}^{n}(-1)^i{n-m\choose n-i}\\ &={n\choose m}(-1)^{m}\sum_{i=0}^{n-m}(-1)^{n-i}{n-m\choose i}\\ &={n\choose m}(-1)^{n+m}\sum_{i=0}^{n-m}{n-m\choose i}(-1)^i 1^{n-m-i}\\ &={n\choose m}(-1)^{n+m}(1-1)^{n-m}\\ &= \delta(n,m) \end{aligned}$

那么喜闻乐见的，我们可以把这个式子代入反演公式，可以得到。

$f(n)=\sum_{i=0}^n(-1)^i{n\choose i} g(i)\Leftrightarrow g(n)=\sum_{i=0}(-1)^i{n\choose i}f(i)$

可能这个式子不太常见，我们把 $(-1)^ig(i)$ 做为 $g'(n)$ 代入就可以得到。

$f(n)=\sum_{i=0}^n{n\choose i}g(i)\Leftrightarrow g(i)=\sum_{i=0}^n(-1)^{n-i}f(i)$

这个形式就比较常见了。再稍稍变一下形式，本质上还是由于 $\sum_{i=n}^m(-1)^{i-n}{m\choose i}{i\choose n} =\delta(n,m)$ 。这也是比较常用的三种反演公式了。

$f(n)=\sum_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(i)=\sum_{i=n}^m(-1)^{i-n}{i\choose n}f(i)$

来个小例题，错位排序问题。我们定义 $f(i)$ 满足有 $i$ 个元素满足 $a_i\not =i$ 的排列数。那么我们根据全排列公式有 $n!=\sum_{i=0}^n {n\choose i}f(i)$ 那么套用二项式反演， $f(n) = \sum_{i=0}^n(-1)^{i-n}{n\choose i} i!$ 。化简之后得到 $f(n) = n!\sum_{i=0}^n\frac{(-1)^i}{i!}$ 这个和容斥分析出来的答案其实是一样的。而二项式反演的本质其实就是容斥。
集合计数
- 题意：一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$ ，求取法的方案数。
- 分析：我们可以先得到选 $i$ 个交集中元素的方案为 $f(i) = {n\choose i}(2^{2^{n-k}} - 1)$ 。那么我们定义 $g(i)$ 为集合的交集的元素恰好为 $i$ 的方案数，那么 $f(k)=\sum_{i=k}^n{i\choose k}g(i)$ ，还是套用二项式反演。 $g(i) = \sum_{i=n}^{m}(-1)^{i-n}{i\choose n} f(i)$ 。

斯特林反演

引理

$x^{\underline{n}} = (-1)^n(-x)^{\overline{n}}$ 。暴力展开式子左式子为 $x(x-1)(x-2)...(x-n+1)$ 。而右式子为 $(-1)^n (-x)(-x+1)(-x+2)...(-x+n-1)$ 。然后容易发现左式等于右式。
$x^{\overline{n}} = (-1)^n(-x)^{\underline{n}}$ 。证明同上。
$\sum_{i=n}^m(-1)^{n-i}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\n\end{bmatrix}=\delta(n,m)$ 反转公式。
$\begin{aligned} n^m &= \sum_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}n^{\underline{i}}\\ &= \sum_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}\sum_{j=0}^{n}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j} n^j\\ &= \sum_{j=0}^nn^{j}\sum_{i=j}^m(-1)^{i-j}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix} \end{aligned}$

由于多项式同类项系数相同，所以 $j=n$ 时后面才会为 $1$ 。也就是 $\sum_{i=n}^m(-1)^{n-i}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\n\end{bmatrix}=\delta(n,m)$ 由此得证。

同理我们还可以得到另一个反转公式 $\sum_{i=n}^m(-1)^{n-i}\begin{bmatrix}m\\i\end{bmatrix}\begin{Bmatrix}i\\n\end{Bmatrix}=\delta(n,m)$ 。
将得到的反转公式代入反演公式我就可以得到，斯特林反演的公式，为