首先别犯一些脑残的定义错误：\(\binom{n}{m}=C_n^m\)
-
对称恒等式：\(\binom{n}{m}=\binom{n}{n-m}\)
-
吸收恒等式：\(m\binom{n}{m}=n\binom{n-1}{m-1}\)
\(\text{Catalan}\) 数列
\[H_n = \dfrac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})
\]
\(\text{Lucas}\) 定理
\[\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p
\]
第二类 \(\text{Stirling Number}\)
\(\begin{Bmatrix}n\\ k\end{Bmatrix}\) 表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空子集的方案数。
递推式：
\[\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix}
\]
通项公式
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!}
\]
范德蒙德卷积
\[\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}
\]
证明：
可以用二项式定理证明：
\[\begin{aligned}
\sum_{k=0}^{n+m}\binom{n+m}{k}x^k&=(x+1)^{n+m}\\
&=(x+1)^n(x+1)^m\\
&=\sum_{r=0}^n\binom{n}{r}x^r\sum_{s=0}^m\binom{m}{s}x^s\\
&=\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}x^k\\
\end{aligned}
\]
同时可以考虑他的组合意义：在一个大小为 \(n+m\) 的集合中取出 \(k\) 个数，等价于将 \(n+m\) 的集合拆成大小分别为 \(n\) 与 \(m\) 的两个集合，然后从 \(n\) 中取出 \(i\) 个数，从 \(m\) 中取出 \(k-i\) 个数的方案数。
几个推论：
\[\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}
\]
\[\sum_{i=-r}^{s}\binom{n}{r+i}\binom{m}{s-i}=\binom{n+m}{r+s}
\]
\[\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}
\]
\[\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}
\]