范德蒙恒等式
范德蒙恒等式
这篇博客比较水,因为这个东西实在是没什么好讲的。
等式如下:
Cn+mk=∑i=0kCni×Cmk−iC_{n+m}^k=\sum_{i=0}^k C_n^i \times C_m^{k-i} Cn+mk=i=0∑kCni×Cmk−i
证明也很简单:
考虑右边的柿子的意义——从 nnn 里面拿 iii,再从 mmm 里面拿 k−ik-ik−i 个物品,那么得到的总物品数恒定为 kkk,但是从 nnn 和 mmm 那里拿的数目不固定,所以这个问题等价于:从 n+mn+mn+m 个物品中选 kkk 个物品的方案数。