组合数学再基础
之前好像写过「组合数学基础」，在这里再来堆点柿子。
1 Stirling 数
1.1 定义
众所周知，Stirling 数有两类，分别是：
$$ \begin{align} \begin{bmatrix}n\newline m \end{bmatrix} = \begin{bmatrix}n-1\newline m-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1\newline m \end{bmatrix} \newline \begin{Bmatrix}n\newline m \end{Bmatrix}=\begin{Bmatrix}n-1\newline m-1\end{Bmatrix}+m \begin{Bmatrix}n-1\newline m \end{Bmatrix} \end{align} \tag1 $$
其中 $n,m\in \mathbb N$，它们的边界均是 $S(0,0)=S(1,1)=1,S(1,0)=0$。
接下来介绍 Stirling 数的性质。
1.2 常幂展开
一个组合意义显然的柿子：
$$ \begin{align} n^m &= \sum\limits_{k=0}^m \begin{Bmatrix}m\newline k \end{Bmatrix}k! \dbinom{n}{k} \tag2 \newline &= \sum\limits_{k=0}^m \begin{Bmatrix}m\newline k\end{Bmatrix} n^{\underline{k}} \tag{3} \end{align} $$
其中 $n,m\in\mathbb N$，$(3)$ 式通常被称为 常幂展开。
1.3 Stirling 反演
$$ f(n) = \sum\limits_{k=0}^n \begin{Bmatrix}n\newline k\end{Bmatrix} g(k) \Leftrightarrow g(n) = \sum\limits_{k=0}^n (-1)^{n - k} \begin{bmatrix}n\newline k\end{bmatrix} f(k) \tag{4} $$
其中 $n\in \mathbb N$，$(4)$ 式通常被称为 Stirling 反演公式。
1.4 阶乘幂展开
对 $(3)$ 应用 $(4)$ 式得：
$$ n^{\underline m}= \sum\limits_{k=0}^m (-1)^{m-k} \begin{bmatrix}m\newline k\end{bmatrix} n^k \tag{5} $$
可以证明有：
$$ n^{\overline m}= \sum\limits_{k=0}^m \begin{bmatrix}m\newline k\end{bmatrix} n^k \tag{6} $$
其中 $n,m\in\mathbb N$，$(5),(6)$ 两式被称作阶乘幂展开。
2 组合数
2.1 定义
小葱同学擅长计算的组合数定义为：
$$\dbinom{n}{m}=\begin{cases} 0, \text{ }m>n\text{ or }m<0\newline \dfrac{n^{\underline m}}{m!},\text{ otherwise} \end{cases}$$
其中 $n\in \mathbb R,m\in \mathbb Z$。当 $n,m$ 均是非负整数且 $m\le n$ 时，它满足递推式：
$$\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1}$$
2.2 二项式定理
$$(x+y)^k = \sum\limits_i \dbinom{k}{i} x^i y^{k-i} \tag{7}$$
其中 $k\in \mathbb R$，$(7)$ 式被称作二项式定理。
2.3 组合恒等式
组合恒等式 I
在 $(7)$ 式中令 $x=y=1$ ，得：
$$\sum\limits_i \dbinom{k}{i} = 2^k \tag{8}$$
其中 $k\in \mathbb R$。
组合恒等式 II
$$\sum\limits_i \dbinom{k}{i}[2|i] =\sum\limits_i \dbinom{k}{i}[2\nmid i] = 2^{k-1} \tag9$$
其中 $k\in \mathbb R$，证明显然。
组合恒等式 III
$$\dbinom{n}{k}\dbinom{k}{j} = \dbinom{n}{j} \dbinom{n-j}{k-j} \tag{10}$$
其中 $n,k,j\in \mathbb Z$，证明显然。
吸收公式
$$ \begin{align} \dfrac{n}{m}\dbinom{n-1}{m-1}&=\dbinom{n}{m}\tag {11}\newline \newline (n-m)\dbinom{n}{m}&=n\dbinom{n-1}{m}\tag {12}\end{align} $$
其中 $n,m\in \mathbb Z$，证明显然。$(11),(12)$ 式被称作吸收公式。
范德蒙德卷积
$$ \sum\limits_i \dbinom{A}{i}\dbinom{B}{C-i}=\dbinom{A+B}{C} \tag{13}$$
其中 $A,B,C\in\mathbb N$，$(13)$ 式被称作范德蒙德卷积。注意它可以简单推广到多元形式。
上指标求和
$$\begin{align} \sum\limits_{i=m}^n \dbinom{i}{m} &= \dbinom{n+1}{m+1} \tag{14} \newline
\sum\limits_{i=0}^n \dbinom{m+i}{i} &= \dbinom{n+m+1}{n} \tag{15} \end{align}$$
其中 $n,m\in\mathbb N$，证明显然。$(14),(15)$ 式被称作上指标求和公式，$(15)$ 式又被称作平行求和公式。
上指标反转
$$\begin{align} \dbinom{n}{m}&=(-1)^m \dbinom{m-n-1}{m} \tag {16}\newline \dbinom{-1}{m}&=(-1)^m\dbinom{m}{m}=(-1)^m \tag {17}\end{align}$$
其中 $n,m\in\mathbb Z$。证明只需要考虑把 $-1$ 的系数均摊到分子下降幂上。$(16)$ 式被称作上指标反转，$(17)$ 式是 $(16)$ 式对于 $n=-1$ 的特殊情况。
$(8)\text{~}(17)$ 式通常被称作组合恒等式。
2.4 二项式反演
形式 I
$$ f(n) = \sum\limits_{k=0}^n (-1)^k\dbinom{n}{k} g(k) \Leftrightarrow g(n) = \sum\limits_{k=0}^n (-1)^k \dbinom{n}{k} f(k) \tag{18} $$
形式 II
$$ f(n) = \sum\limits_{k=0}^n\dbinom{n}{k} g(k) \Leftrightarrow g(n) = \sum\limits_{k=0}^n (-1)^{n-k} \dbinom{n}{k} f(k) \tag{19} $$
形式 III
$$ f(n) = \sum\limits_{k=n}^m\dbinom{k}{n} g(k) \Leftrightarrow g(n) = \sum\limits_{k=n}^m (-1)^{k-n} \dbinom{k}{n} f(k) \tag{20} $$
其中 $n,m\in\mathbb N$，$(18),(19),(20)$ 式被称作二项式反演公式。
2.5 第二类 Stirling 数通项
对 $(2)$ 式应用 $(19)$ 式得：
$$ \begin{Bmatrix}n\newline m \end{Bmatrix}m! = \sum\limits_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n \tag{21} $$
其中 $n,m\in\mathbb N$，$(21)$ 式被称为第二类 Stirling 数通项公式。
3 相关题目
「bzoj2839」集合计数
「bzoj3622」已经没有什么好害怕的了
「CF932E」 Team Work
「2018 雅礼集训」方阵
「TJOI / HEOI2016」求和
「LOJ #6716.」 自然数幂之和
「2020联考A卷」组合数问题
「各种数数题」…