这一章主要讲解各种组合恒等式。
但是事实上，有很大一部分都能用有限微积分、OGF、EGF 之类的武器轻松搞定。
组合恒等式
组合数定义
朴素定义：
\[\binom n m = \dfrac {n!} {m! (n-m)!} \]下降幂定义：
\[\binom n m = \dfrac {n^{\underline m}} {m!} \]组合数递推式（Pascal's Identity）
\[\binom n m = \binom {n-1} m + \binom {n-1} {m-1} \]组合意义
从 \(n\) 个元素中选 \(m\) 个：
- 若最后一个元素不选，则方案数为 \(\binom {n-1} m\)。
- 若最后一个元素选，则方案数为 \(\binom {n-1} {m-1}\)。
二项式定理（The Binomial Theorem）
\[(x+y)^n = \sum\limits_{i=0}^n \binom n i x^i y^{n-i} \]组合意义
\(x\) 的次数为 \(i\) 的项，\(y\) 的次数必为 \(n-i\)。
从 \(n\) 个 \((x+y)\) 中选出 \(i\) 个 \(x\) 的方案数为 \(\binom n i\)。
代数证明
用数学归纳法。EGF 也可行有一种儿子推出爸爸的美。
补充
有利用多重组合数的多项式定理（The Multinomial Theorem）。
三项式版恒等式
\[\binom n k \binom k m = \binom n m \binom {n-m} {k-m} = \binom n {n-k,k-m,m} \]平行求和
\[\sum\limits_{i=0}^n \binom {m+i} i = \sum\limits_{i=0}^n \binom {m+i} m = \binom {n+m+1} n \]代数证明
利用 \(\binom {n+x} n = \Delta \binom {n+x} {n+1}\)：
\[\begin{aligned} & \sum\limits_{i=0}^n \binom {m+i} m \\ =& \sum\limits_{0}^{n+1} \binom {m+x} m \delta x \\ =& \binom {n+m+1} {m+1} - \binom m {m+1} \\ =& \binom {n+m+1} n \end{aligned}\]类似证明
上指标求和公式：
\[\sum\limits_{i=0}^n \binom i m = \binom {n+1} {m+1} \]这个公式利用的是 \(\binom x n = \Delta \binom x {n+1}\)。
范德蒙德卷积（Vandermonde's Identity）
\[\sum\limits_{i=0}^n \binom a i \binom b {n-i} = \binom {a+b} n \]组合意义
两侧均为从 \(a+b\) 个元素中取出 \(n\) 个元素的方案数。
代数证明
使用 OGF：
\[\begin{aligned} & \sum\limits_{i=0}^n \binom a i \binom b {n-i} \\ =& \sum\limits_{i=0}^n \left([x^i](x+1)^a\right) \left([x^{n-i}](x+1)^b\right) \\ =& [x^n](x+1)^{a+b} \\ =& \binom {a+b} n \end{aligned}\]