组合数学玄学操作

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

组合数相关

\[ 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_{2n}^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^{\overline{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 \]