组合恒等式学习笔记

组合恒等式的推导证明一般可以考虑等号两边的组合意义、杨辉三角、二项式定理或者直接硬上组合定义式。

$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$

考虑最后一个元素有没有选。

$\sum\limits_{i=0}^n\binom{n}{i}=2^n$

枚举在 $n$ 个元素的集合中选多少个元素，再枚举选出的是那些元素，等于枚举每个元素有没有选。

$\sum\limits_{i=0}^n(-1)^i\binom{n}{i}=0$

二项式定理：

$(-1+1)^n=\sum\limits_{i=0}^n(-1)^i1^i\binom{n}{i}=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}=0$

$\sum\limits_{i=n}^m\binom{i}{n}=\binom{m+1}{n+1}$

考虑杨辉三角：

$\sum\limits_{i=0}^m\binom{n+i}{i}=\binom{m+1}{n+m}$

依旧是考虑杨辉三角：

$\binom{n}{m}=\frac{n-m+1}{m}\binom{n}{m-1}$

$\binom{n}{m}=k\binom{n}{m-1}$

$k=\frac{\binom{n}{m}}{\binom{n}{m-1}}=\frac{\frac{n!}{m!(n-m)!}}{\frac{n!}{(m-1)!(n-m+1)!}}=\frac{(m-1)!(n-m+1)!}{m!(n-m)!}=\frac{n-m+1}{m}$

$\sum\limits_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$

著名的范德蒙德卷积，组合意义是从两个没有重复元素的集合中选择 $k$ 个元素可以通过枚举每个集合中选了几个来计算。

$xy=\binom{x+y}{2}-\binom{x}{2}-\binom{y}{2}$

从 $x$ 个各不相同的小球中选出一个，再从 $y$ 个各不相同的小球中选出一个的方案数，等于从这 $x+y$ 个小球中选出 $2$ 个的方案数减去两个球都是从某一边选出的方案数。

$\sum\limits_{i=k}^n 2^{n-i}\binom{m+i}{m+k}=\sum\limits_{i=m+k+1}^{m+n+1}\binom{m+n+1}{i}$