组合数公式
$ C_n^m $ 在组合数学中的意义：在 n 个元素选 m 个元素的方案数。
公式
公式 1
\[ C_n^m = \frac{n!}{m! * (n-m)!} \]
组合数的通项公式。
当要求组合数模一般模数时 ，通项公式的分母可能没有逆元导致不可行。
公式 2
\[ C_n^m = C_n^{n-m} \]
基本性质，可以由通项公式得出。
公式 3
\[ C_n^m * C_m^k = C_n^k * C_{n-k}^{m-k} \]
公式 4
\[ C_n^m = C_{n-1}^{m-1} + C_{n-1}^m \]
组合数的基本递推式。
当要求组合数模一般模数时 ，常用这种方法预处理组合数。
公式 5
\[ \sum_{i=0}^n C_n^i = 2^n \]
组合意义： n 个元素选任意元素的方案数。 每个数都可以选或不选，所以方案数为 $ 2^n $ 。
同样可以由二项式定理： $ (x + 1)^n = _{i=0}^n C_n^i * x^i $ 得出。
公式 6
\[ \sum_{i=0}^n (C_n^i)^2 = C_{2n}^n \]
公式 7
\[ C_{n+m}^k = \sum_{i=0}^k C_n^i * C_m^{k-i} \]
从组合数学上的定义出发，在 n + m 个元素中选 k 个， 相当于先在前 n 个元素中选 i 个再在后 m 个元素中选 k - i 个。 枚举这个 i 把方案数相加就能得到最终方案数。
公式 8
\[ \sum_{i=0}^n C_{k+i}^k = C_{k+n+1}^n \]
进一步可以得到下式：
\[ \sum_{i=0}^n \sum_{j=0}^m C_{i+j}^i = C_{n+m+2}^{m+1} - 1 \]
类似的还有：
\[ \sum_{i=0}^n C_{i}^k = C_{n+1}^{k+1} \]
Lucas 定理
\[ C_n^m \% p = C_{n/p}^{m/p} * C_{n \% p}^{m \% p} \% p \]
常用于模数较小的组合数取模。