常用组合恒等式

限制条件在 OI 中基本用不到，就不写了。

$$\begin{align} & \binom{n}{m} = \frac{n!}{m!(n-m)!} \\ & \binom{n}{m} = \binom{n}{n-m} \\ & \binom{n}{m} = \frac{n}{m} \binom{n-1}{m-1} \\ & \binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1} \\ & \binom{n}{m} = (-1)^{m} \binom{m-n-1}{m} \\ & \binom{a}{b}\binom{b}{c} = \binom{a}{c}\binom{a-c}{b-c} \\ & (a+b)^{n} = \sum_{i=0}^{n} \binom{n}{i} a^ib^{n-i} \\ & \sum_{i=0}^{n} \binom{i}{m} = \binom{n+1}{m+1} \\ & \sum_{i} \binom{a}{i} \binom{b}{n-i} = \binom{a+b}{n} \\ & \sum_{\sum i_j = n} \prod \binom{a_i}{i_j} = \binom{\sum a_i}{n} \\ & \begin{Bmatrix} n \\ m \end{Bmatrix} = m\begin{Bmatrix} n-1 \\ m \end{Bmatrix} + \begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix} \\ & n^m = \sum_{i=0}^{m} \begin{Bmatrix} m \\ i \end{Bmatrix} n^{\underline i} \\ & m!\begin{Bmatrix} n \\ m \end{Bmatrix} = \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} i^n \\ & \begin{bmatrix} n \\ m \end{bmatrix} = (n-1)\begin{bmatrix} n-1 \\ m \end{bmatrix} + \begin{bmatrix} n-1 \\ m-1 \end{bmatrix} \\ & x^{\overline n} = \sum_{i=0}^{n} \begin{bmatrix} n \\ i \end{bmatrix} x^i \\ & x^{\underline n} = \sum_{i=0}^{n} (-1)^{n-i} \begin{bmatrix} n \\ i \end{bmatrix} x^i \end{align}$$