组合数学玄学操作

发表于 2020-01-02 更新于 2020-12-22 分类于整理阅读次数： 112

以下公式均不给出证明，目的是为了让结论一目了然。

组合数相关

$C_{n}^{m} C_{m}^{k} = C_{n}^{k} C_{n - k}^{m - k}$

基本递推式 $C_{n}^{m} = C_{n - 1}^{m - 1} + C_{n - 1}^{m}$

二项式定理 $(a + b)^{n} = \sum_{i = 0}^{n} C_{n}^{i} a^{i} b^{n - i}$

$\sum_{i = 0}^{n} (C_{n}^{i})^{2} = C_{2 n}^{n}$

$C_{n + m}^{k} = \sum_{i = 0}^{k} C_{n}^{i} C_{m}^{k - i}$

卢卡斯定理（要求 $p$ 是质数） $C_{n}^{m} % p = C_{n / p}^{m / p} C_{n % p}^{m % p} % p$

上指标反转 $(\binom{n}{m}) = (- 1)^{m} (\binom{m - n - 1}{m})$

$s_{n}^{m} = s_{n - 1}^{m - 1} + (n - 1) s_{n - 1}^{m}$

$x^{\overset{―}{n}} = \sum_{m} s_{n}^{m} x^{m}$

$S_{n}^{m} = S_{n - 1}^{m - 1} + m S_{n - 1}^{m}$

$n^{m} = \sum_{k = 0}^{m} S_{m}^{k} C_{n}^{k} k!$

上式的二项式反演，组合数拆开后可转换为卷积形式 $S_{n}^{m} = \frac{1}{m!} \sum_{k = 0}^{m} (- 1)^{m - k} C_{m}^{k} k^{n}$