排列组合
从 $n$ 个互不相同的球里选出 $m$ 个，顺序有影响则称为排列，没有影响则称为组合。
$P_n^m$ 表示排列的方案数，$C_n^m$ 表示组合的方案数。其中 $C_{n}^m$ 也可表示为 $\binom nm$，$P_n^m$ 在数值上与 $n^{\underline m}$（下降幂）相等。
-
我们以下认为 $P_n^m$ 用阶乘表示，下降幂用连乘表示。此外，组合数只考虑整数域。
-
由于 $m\ge n$ 时 $C_n^m=0$，所以涉及组合数的求和可以不写边界。
求 $P_n^m$ 是简单乘法原理：第一步可以取 $m$ 种，第二步可以取 $m-1$ 种 $\dots$。所以 $Pm_n=\prod\limits_{i=n-m+1}n i$。乘除同补，得到 $P_{n}m=n=\frac{n!}{(n-m)!}$。
考虑求 $C_n^m$，唯一的区别在于顺序无关，所以取出的 $m!$ 种顺序视为一种方案。因此 $C_n^m=\frac{n!}{m!(n-m)!}$。
更一般的，$\binom nm=\frac{n^{\underline m}}{m!}$。
不过，方便起见，认为 $m\ge 0$，且 $n,m$ 均为整数。
二项式定理
$\large(x+y)n=\sum\limits_{i=0}n\binom nixiy$。
感性理解，就相当于 $n$ 个 $(x+y)$，从中取 $0\dots n$ 个 $x$，其余的取 $y$。对于负指系数的情况，在生成函数那里有，不做赘述。值得注意的是其矩阵表示。
$$
(x+y)n=\begin{bmatrix}a0&a1&\dots&an\end{bmatrix}\begin{bmatrix}\binom n0\&\ddots\&&\binom nn\end{bmatrix}\begin{bmatrix}&&1\&\dots\1\end{bmatrix}\begin{bmatrix}b0\b1\\vdots\b^n\end{bmatrix}
$$
头尾两个矩阵很好理解。中间有一个组合数式矩阵也很好。第三项是单位矩阵反过来，相当于乘法中的 $-1$ 项，作用是将 $a$ 翻转一遍，使得 $a_i$ 与 $b_{n-i}$ 而非 $b_i$ 匹配。
二项式反演
容斥原理
很简单，不多说。最经典的就是求一堆集合的并，一加两减 $\dots$。
更进一步的，假设对于集合 $S$，$S_{ans}=|S|$，记 $f(n)$ 表示 $n$ 个集合补集的交集大小，$g(n)$ 表示原集交集大小，有：
- $f(n)=\sum\limits_{i=0}(-1)^i\binom ni g(i)\iff g(n)=\sum\limits_{i=0}(-1)^i\binom nif(i)$。
从这个式子开始延伸。证明太长的话就不写了。
-
$f(n)=\sum\binom nig(i)\iff g(n)=\sum(-1)^{n-i}\binom nif(i)$。令 $g(n)=(-1)^ng(n)$ 带回原始式得证。
-
$f(n)=\sum\limits_{i=n}^m\binom ing(i)⇔g(n)=\sum\limits_{i=n}m(−1)\binom inf(i)$。左右互带得证。
我们考虑的过程中，都是从组合意义出发。从钦定 $k$ 个的方案容斥出恰好 $k$ 个，二项式系数在其中作用就是决定钦定的是哪 $k$ 个。
组合数的神奇式子
杨辉三角
首先我们要知道组合递推式：$C_{n}m=C_{n-1}+C_{n-1}^m$。从 dp 角度考虑，就是我们第 $n$ 个物品选与不选的决策。将数组中非零的项左对齐写下来，得到的三角形即杨辉三角。
-
$C_{n}m=C_{n}$。选原集和选补集的方案等价。
-
$C_{n}m=C_{n-1}m+C_{n-1}^{m-1}$。在组合数两维均不大的时候，我们可以直接利用这个预处理，常数极小。
-
$(n+1)C_nm=(m+1)C_{n+1}$。把 $n+1$ 乘进 $n!$，分母强凑组合数。
-
$C_{n}^m=\frac nmC_{n-1}^{m-1}$。利用上一个式子得到的结果。
-
$\sum C_{n}i=2n$。从组合数定义上考虑，共有 $2^n$ 种集合。用二项式定理证，是 $(1+1)^n$ 的展开形式。
-
$\sum C_{n}^{2i}=\sum C_{n}^{2i+1}(n\neq 0)$。两侧相减，变成二项式定理 $(1-1)^n$ 的展开形式。特例是 $x^0=1$。
-
$C_{n}^m\times C_{m}k=C_{n}k\times C_{n-k}^{m-k}$。代数式依旧暴力拆开，组合意义上，我们先选出 $m$ 个，从中挑出 $k$ 个等价于先挑出 $k$ 个，再从剩下的选出 $m-k$ 个。
-
$\sum\limits_{i=0}^k C_ni=C_{n+1}$。从杨辉三角的递推上看，每个位置都会对右下总体产生贡献，其中等于总贡献的就是右下一格的位置。
-
$\sum\limits_{i=0}^k \binom ni\binom m{k-i}=C_{n+m}^k$。从组合意义上考虑，相当于从 $n$,$m$ 两堆共取 $k$ 个物品，枚举其中一堆取了多少个。
这个式子配合 $\binom ni=\binom n{n-i}$ 食用，可以得到一些非常有趣的式子：
- $C_{2n}^{n+1}=\sum\binom ni\binom n{i+1}$。将其中一个变一下就是了。
- $C_{2n}^n=\sum\binom ni^2$。（和上一个相减就是卡特兰数）
- $\sum\binom ni\binom mi=C_{n+m}^m$。
第二类斯特林数（Stirling）
在讲述这个问题前，我们先看八个古老的问题，均要求方案数：
- 将 $n$ 个不同的球放入 $m$ 个不同盒子，可以为空。
每个球相互独立，$n^m$。
- 将 $n$ 个不同的球放入 $m$ 个不同盒子，不能为空。
钦定 $k$ 个盒子为空，拿上一问结论容斥即可。但还有一种策略，稍后讲。
- 将 $n$ 个相同的球放入 $m$ 个不同盒子，不能为空。
等价于 $a_1+\dots+a_m=n$ 的正整数解，插板即可。也可以生成函数+二项式定理推，结果一样。
- 将 $n$ 个相同的球放入 $m$ 个不同盒子，可以为空。
等价于上一问的自然数解。
- 将 $n$ 个相同的球放入 $m$ 个相同盒子，可以为空。
显然可以 dp，做法略。另一种思路是对每个盒子构造生成函数。类似于代码拍卖会，我们一层一层放，即前 $m$ 个盒子放入 $0\ldots n$ 个球，前 $m-1$ 个盒子再放入 $0\ldots n$，以此类推。最后答案就是 $x^n$ 项系数。等比求和后是分式的形式，多项式乘法逆解决。
- 将 $n$ 个相同的球放入 $m$ 个相同盒子，不能为空。
先在每个盒子各放一个球，转化为 $(n-m,m)$ 的上一问。
-
将 $n$ 个不同的球放入 $m$ 个相同盒子，可以为空。
-
将 $n$ 个不同的球放入 $m$ 个相同盒子，不能为空。
这两问统一处理。$dp_{i,j}$ 表示已经用了 $i$ 个球、$j$ 个盒子的方案数。新增一个球可以放进之前的盒子，也可以另开一个盒子。所以 $dp_{i,j}=dp_{i-1,j-1}+j\times dp_{i-1,j}$。
对于第 8 问，答案即为 $dp_{n,m}$，对于第 7 问，答案为 $dp_{n,0\dots m}$ 之和。
此外，我们发现，第二问本质上是 $dp_{n,m}\times m!$。（盒子有无编号区别）
第八问的结果也称为第二类斯特林数，记作 $S_n^m$，也可以记作 $n\brace m$（第一类斯特林数是 $n\brack m$）。
第二类斯特林的递推公式 $S_nm=S_{n-1}+mS_{n-1}^m$。
根据第二问的结果容斥形式列出等式：
$$m!S_{n}m=\sum_{k=0}m(-1)^k\binom mk(m-k)^n$$
看到 $(-1)^k\binom mk$，可以猜出这东西能反演。不过暂时长的不像反演形式，我们继续推。
$$=\sum_{k=0}m(-1)k\binom m{m-k}(m-k)n\=\sum_{k=0}m(-1)^{m-k}\binom m{k}k^n$$
记 $f(x)=x!S_nx,g(x)=xn$。
$$f(m)=\sum_{k=0}m(-1)\binom mkg(k)$$
回看二项式反演形式一：
$$f(n)=\sum\binom nig(i)\iff g(n)=\sum(-1)^{m-i}\binom nif(i)$$
所以 $g(m)=\sum \binom mif(i)=\sum \binom mi{n\brace i}i!=m^n$。
所以我们得到第二类斯特林数一个很重要的式子：
$$
m^n=\sum
\binom mi{n\brace i }i!
$$
以及它的通项公式
$$
S_n^m=\frac 1{m!}\sum(-1)^{m-k}\binom mkkn\=\sum_{k=0}m\frac{(-1){m-k}}{(m-k)!}\frac{kn}{k!}
$$