组合数学

组合数相关

$\tbinom n m$
表示$n$个元素中不考虑顺序选$m$个元素的方案数

$\tbinom n m=\tbinom{n}{n-m}$
$n$个里选$m$个等价于$n$个里不选$n-m$个

$\sum_{i=0}^n\tbinom n i=2^n$
$n$个里随意选即$2^n$

$\sum_{i=0}^n\tbinom n i[2|i]=\sum_{i=0}^n\tbinom n i[2|(i+1)]=2^{n-1}$
考虑左式
在$n-1$个中随意选，选出来是奇数个就选第$n$个，否则不选第$n$个
右式同理

$\sum_{i=1}^mx_i=n$的正整数解与非负正数解个数
考虑插板法
有$n$个球，$n-1$个空档，在$n-1$个空档中插$m-1$个板子将球分为$m$段
$i$挡板与$i-1$挡板之间的一段的球个数对应正整数$x_i$，$m-1$挡板后面的对应$x_m$
故方案数$\tbinom{n-1}{m-1}$
非负整数加$m$个球即可
方案数$\tbinom{n+m-1}{m-1}$

$\sum_{i=0}^m\tbinom{n+i} n=\tbinom{n+m+1}{m+1}$
考虑第一象限上$n\times m$的网格图
左式表示在网格图中只能往上往右走走到第$n$列的方案数和
右边表示走到点$(n,m+1)$的方案数
可以发现，每一个走到第$n$列的方案都唯一对应一个到$(n,m+1)$的方案（定义该位置为该方案方案最后在第$n$列的位置）
等式成立

$\sum_{i=m}^n\tbinom i m=\tbinom{n+1}{m+1}$
本质与前式相同

$\tbinom n m \tbinom m k=\tbinom n k\tbinom{n-k}{m-k}$
左式是从$n$中选$m$个再从$m$中选$k$个
右式是从$n$中直接选$k$个再在$n-k$个中选出$m-k$个

$\sum_{i=0}^k\tbinom n i\tbinom m{k-i}=\tbinom{n+m} k$
从$n$个中选$i$个再从$m$个中选$k-i$个等价从$n+m$个直接选$k$个

一个牛B式子 $\tbinom{i+j}{2}-\tbinom{i}{2}-\tbinom{j}{2}=ij$ 从代数意义上易证

斯特林数相关

$\begin{Bmatrix}n\\k\end{Bmatrix}$读作$n$子集$k$，表示$n$个元素放入$k$个非空集合的方案数

$\begin{bmatrix}n\\k\end{bmatrix}$读作$n$轮换$k$，表示$n$个元素放入$k$个轮换的方案数

$\begin{Bmatrix}n\\k\end{Bmatrix}=k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix}$
$n$个元素放入$k$个非空集合，讨论第$n$个元素的两种情况，与前者共用集合和单独开辟集合
前$n-1$个放入$k$个非空集，第$n$个元素随意进哪一个集合
前$n-1$个放入$k-1$个非空集，第$n$个元素单独开辟一个集合

$\begin{bmatrix}n\\k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}+\begin{bmatrix}n-1\\k-1\end{bmatrix}$
同上，讨论$n$的归属

下降幂$n^{\underline i}=n(n-1)(n-2)...(n-i+1)$
上升幂$n^{\overline i}=n(n+1)(n+2)...(n+i-1)$

$n^m=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}n^{\underline i}$
考虑组合意义
$m$个格子，$n$种颜色填格子的方案数（不一定要用所有颜色）
枚举使用了$i$种颜色，$\tbinom n i$种可能
将$m$个格子涂上$i$种颜色且每种必须涂即$\begin{Bmatrix}m\\i\end{Bmatrix}i!$种方案
$i!$是因为颜色之间有区别
故$n^m=\sum_{i=0}^n\tbinom n i\begin{Bmatrix}m\\i\end{Bmatrix}i!=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}n^{\underline i}$
这是普通幂转下降幂的重要式子