组合恒等式学习笔记

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


(nm)=(n1m)+(n1m1)\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}

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


i=0n(ni)=2n\sum\limits_{i=0}^n\binom{n}{i}=2^n

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


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

二项式定理:

(1+1)n=i=0n(1)i1i(ni)=i=0n(1)i(ni)=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


i=nm(in)=(m+1n+1)\sum\limits_{i=n}^m\binom{i}{n}=\binom{m+1}{n+1}

考虑杨辉三角:


i=0m(n+ii)=(m+1n+m)\sum\limits_{i=0}^m\binom{n+i}{i}=\binom{m+1}{n+m}

依旧是考虑杨辉三角:


(nm)=nm+1m(nm1)\binom{n}{m}=\frac{n-m+1}{m}\binom{n}{m-1}

(nm)=k(nm1)\binom{n}{m}=k\binom{n}{m-1}

k=(nm)(nm1)=n!m!(nm)!n!(m1)!(nm+1)!=(m1)!(nm+1)!m!(nm)!=nm+1mk=\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}


i=0k(ni)(mki)=(n+mk)\sum\limits_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}

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


xy=(x+y2)(x2)(y2)xy=\binom{x+y}{2}-\binom{x}{2}-\binom{y}{2}

xx 个各不相同的小球中选出一个,再从 yy 个各不相同的小球中选出一个的方案数,等于从这 x+yx+y 个小球中选出 22 个的方案数减去两个球都是从某一边选出的方案数。


i=kn2ni(m+im+k)=i=m+k+1m+n+1(m+n+1i)\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}