范德蒙恒等式

维基百科,自由的百科全书
跳转至: 导航搜索

范德蒙恒等式组合数的二阶求和公式。

\sum_{i=0}^k \binom ni \binom m{k-i}=\binom {n+m}k

证明[编辑]

组合方法[编辑]

甲班有m个同学,乙班有n个同学,从两个班中选出k名有\binom {n+m}k种方法。

从甲班选k-i名,从乙班选i名有\binom ni \binom m{k-i}种方法,考虑所有情况i=0,1,...,k,从两个班中选出k名有\sum_{i=0}^k \binom ni \binom m{k-i}种方法。[1]

母函数方法[编辑]

(1+x)^n (1+x)^m=(1+x)^{n+m}

(1+x)^n (1+x)^m=(\sum_{i=0}^n C_n^i x^i)(\sum_{i=0}^m C_m^i x^i)=\sum_{k=0}^{m+n} (\sum_{i=0}^k C_n^i C_m^{k-i})x^k

(1+x)^{n+m}=\sum_{k=0}^{n+m} C_{n+m}^k x^k

\sum_{i=0}^k C_n^i C_m^{k-i}=C_{n+m}^k[1]

参考资料[编辑]