基础组合数学
组合数
\[\binom{n}{m} = \frac{n ^ {\underline{m}}}{m!} \]性质
加法恒等式:
\[\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1} \]提取吸收恒等式：
\[\binom{n}{m} = \frac{n}{m} \binom{n - 1}{m - 1} \]二项式定理
\[(a + b) ^ n = \sum_{k = 0} ^ \infty \binom{n}{k} a ^ {n - k} b ^ k \]当 \(k \geq n\) 时，\(\binom{n}{k} = 0\)，因此原式子同样可以改写为：
\[(a + b) ^ n = \sum_{k = 0} ^ n \binom{n}{k} a ^ {n - k} b ^ k \]推论
当 \(a = 1, b = -1\) 时：
\[[n = 0] = \sum_{k = 0} ^ \infty (-1) ^ k \binom{n}{k} \]当 \(a = b = 1\) 时：
\[2 ^ n = \sum_{k = 0} ^ \infty \binom{n}{k} \]当 \(a = 1\) 时：
\[(1 + x) ^ n = \sum_{k = 0} ^ \infty \binom{n}{k} x ^ k \]如果对上式的左式取倒数：
\[\frac{1}{(1 + x) ^ n} = \sum_{k = 0} ^ \infty \binom{k + n - 1}{n - 1} x ^ k \]证明的方法可以参考普通生成函数（OGF）。
如果把 \(n\) 推广到复数域就得到了牛顿二项式定理：
\[(1 + x) ^ \alpha = \sum_{k = 0} ^ \infty \binom{\alpha}{k} x ^ k \quad (\alpha \in \mathbb{C}) \]事实上，二项式定理就是牛顿二项式定理的一个特例。
范德蒙德卷积：
\[\binom{n + m}{c} = \sum_{k = 0} ^ c \binom{n}{k} \binom{m}{c - k} \]二项式反演
定义 \(f(x)\) 为选取恰好 \(x\) 个元素的方案数，\(g(x)\) 为选取不超过 \(x\) 个元素的方案数，则有：
\[\begin{aligned} g(n) &= \sum_{k = 0} ^ n \binom{n}{k} f(k) \\ \Leftrightarrow f(n) &= \sum_{k = 0} ^ n (-1) ^ {n - k} \binom{n}{i} g(k) \end{aligned} \]另一种形式的二项式反演（标号颠倒）：
\[\begin{aligned} g(n) &= \sum_{m \leq k \leq n} \binom{n - m}{k - m} f(k) \\ \Leftrightarrow f(n) &= \sum_{m \leq k \leq n} (-1) ^ {k - m} \binom{n - m}{k - m} g(k) \end{aligned} \]卡特兰数
卡特兰数是一个特殊的数列，例如：
- \(n\) 个元素进栈序列为：\(1,2,3, \dots n\)，求有多少种出栈序列。
卡特兰数 \(C_n\) 就是指出栈序列的个数。