\[\dbinom{n}{m}=\dbinom{n}{n-m}

\]

选出补集的方案数等于选出原集合的方案数，即把补集去掉就是原集合

\[\dbinom{n}{m}=\dfrac{n}{m}\dbinom{n-1}{m-1}

\]

用通项式直接代入可得，吸收恒等式

\[\sum\limits_{i=0}^n\dbinom{n}{i}=2^n

\]

等号左面可以看做枚举子集的大小再枚举这个大小的子集个数，等号的右面则是直接枚举子集，故相等

当然可以看成二项式定理的特殊情况

\[\dbinom{m+n}{m}=\sum\limits_{i=0}^m\dbinom ni\dbinom m{m-i}(n\ge m)

\]

看作有两个集合 \(A\) 和 \(B\)，\(A\) 有 \(n\) 个元素，\(B\) 有 \(m\) 个元素

左面即从 \(A,B\) 中共选出 \(m\) 个元素的方案数，右面即枚举 \(A\) 集合中选多少个数，剩下的数在 \(B\) 集合中选

\[\dbinom{2n}{n}=\sum\limits_{i=0}^n\dbinom ni^2

\]

上式的特殊情况

\[\sum\limits_{i=0}^n\dbinom i{m}=\dbinom{n+1}{m+1}

\]

这里给出一种有趣的组合解释：从 \(0,1,\cdots,n\) 中选出 \(m+1\) 个数，选出的数中最大为 \(i\) 的方案数为 \(\dbinom im\)

\[\dbinom{n}{m}\dbinom{m}{k}=\dbinom{n}{k}\dbinom{n-k}{m-k}

\]

左侧为从 \(n\) 个数选出 \(m\) 个数字，再从 \(m\) 个数字中选出 \(k\) 个

我们可以直接从 \(n\) 个数中选出 \(k\) 个，再从剩下 \(n-k\) 个数中选出 \(m-k\) 个在第二轮淘汰的数

\[\sum\limits_{i=0}^{n}\dbinom{n-i}{i}=F_{n+1}

\]

\(F\) 表示斐波那契数列，展示出了斐波那契数列和组合数之间的关系，真奇妙

设 \(G_n=\sum\limits_{i=0}^{n}\dbinom{n-i}i\)，显然有 \(G_0=F_1=1,G_0=F_2=1\)

我们只需要证明 \(G\) 满足斐波那契的递推式即可，即证明：\(G_{n+2}=G_{n+1}+G_{n}\)

\[\begin{aligned}

G_n+G_{n+1}&=\sum\limits_{i=0}^n\dbinom {n-i}i+\sum\limits_{i=0}^{n+1}\dbinom{n-i+1}{i}\\

&=\sum\limits_{i=0}^n\dbinom {n-i}i+\sum\limits_{i=-1}^{n}\dbinom{n-i}{i+1}\\

&=\sum\limits_{i=0}^n\dbinom {n-i}i+\sum\limits_{i=0}^{n}\dbinom{n-i}{i+1}+1\\

&=\sum\limits_{i=0}^n\left(\dbinom {n-i}i+\dbinom{n-i}{i+1}\right)+1\\

&=\sum\limits_{i=0}^n\dbinom {n-i+1}{i+1}+1=\sum\limits_{i=1}^{n+1}\dbinom {n-i+2}{i}+1\\

&=\sum\limits_{i=0}^{n+1}\dbinom {n-i+2}{i}=\sum\limits_{i=0}^{n+2}\dbinom {n-i+2}{i}=G_{n+2}

\end{aligned}\]