组合计数常用公式技巧总结（持续更新）

· · 个人记录

这里给出一些作者个人认为在 OI 中比较有用的组合计数公式和技巧。

Part 0：约定

$2:C_n^m$ 表示组合数，即从 $n$ 个不同元素中取 $m$ 个元素（不考虑顺序， $n,m$ 为整数）的方案数，若无特殊说明，有 $C_n^m=\begin{cases}\frac{n!}{m!(n-m)!}&,0 \le m \le n\\0&,else\end{cases}$ 。 $3:s_n^m$ 表示第二类斯特林数，即将 $n$ 个不同元素分到 $m$ 个集合中（要求每个集合至少有 $1$ 个元素，且 $n,m$ 为整数）的方案数。 ## Part 1：组合数 $1:C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}$ 。在递推的时候很有用。证明即考虑第 $n$ 个数取与不取或使用杨辉三角。 $2:\sum_{i=0}^nx^iy^{n-i}C_n^i=(x+y)^n$ 。可以化简一些形如左边的式子，也可以拆开一些形如右边的式子。证明即考虑右边取了多少个 $x$ 。 $3:\sum_{i\le n}C_i^m=C_{n+1}^{m+1}$ 。可以化简形如左边的式子。证明即考虑加上 $C_m^{m+1}$ 后一直使用公式 $1$ 。 $4:\sum_{i\le n}C_{m+i}^i=C_{m+n+1}^n$ 。可以化简形如左边的式子，证明即考虑加上 $C_m^{-1}$ 后一直使用公式 $1$ 。 $5:\sum_{i\le k}C_n^iC_m^{k-i}=C_{n+m}^k$ 。可以使用此式迅速计算卷积，右边为在 $n$ 个 $A$ 类球和 $m$ 个 $B$ 类球（球两两不同）中选出 $k$ 个球的方案数，左边即枚举 $A$ 类球选了多少个。 $6:f_n=\sum_{i=0}^nC_n^ig_i \iff g_n=\sum_{i=0}^n(-1)^{n-i}C_n^if_i$ 。二项式反演常用形式，可以在“钦定若干个的方案数”和“恰好若干个的方案数”之间转换。 $7:C_n^k=\frac{n}{k}C_{n-1}^{k-1},k>0$ 。可以用来吸收/提取项，整合系数方便计算。利用定义式即可证明。 ## Part 2：第二类斯特林数 $1:s_n^m=m\cdot s_{n-1}^m+s_{n-1}^{m-1}$ ，用于递推，考虑第 $n$ 个元素，如果他自成一个集合的话贡献就是第二项，否则删去他集合个数不减，仍然为 $m$ ，而它加入每一个集合都对应一种不同情况，所以贡献是第一项。 $2:s_n^m=\sum_{i=0}^m\dfrac{(m-i)^n(-1)^i}{(m-i)!i!}$ 。利用此式可 $O(m)$ 求出 $s_n^m$ 的值或配合卷积 $O(klogk)$ 求出所有满足 $0 \le m \le k$ 的 $s_n^m$ 的值。 证明见[https://www.luogu.com.cn/blog/wohaocaia/zu-ge-shuo-xue-di-yi-suo-xiao-zhi-shi-zong-jie-wei-wan-post](https://www.luogu.com.cn/blog/wohaocaia/zu-ge-shuo-xue-di-yi-suo-xiao-zhi-shi-zong-jie-wei-wan-post) （注：引文将 $n,m$ 对换，最后一步是将 $i$ 换为 $n-i$ ）