范德蒙恒等式

作者: ffacs 分类: 总结 发布时间: 2020-08-27 18:30

范德蒙恒等式

$$
\sum_{i=0}^kC_n^iC_m^{k-i}=C_{n+m}^k
$$

证明:

组合意义

右边式子的组合意义为从 $n+m$ 个物品中取出总共 $k$ 个的方案数。左边式子和右边式子组合意义相同。

生成函数

$$
\begin{align}
(1+x)^n\cdot(1+x)^m&=(1+x)^{n+m} \\
\sum_{i=0}^nC_n^ix^i\cdot \sum_{j=0}^mC_m^jx^j&=\sum_{k=0}^{n+m}C_{n+m}^kx^k \\
\sum_{k=0}^{n+m}\left(\sum_{i=0}^kC_n^iC_m^{k-i}\right)x^k&=\sum_{k=0}^{n+m}C_{n+m}^kx^k
\end{align}
$$

所以得到式 $(1)$

变形

将式子中的 $k$ 用 $m$ 替换即得到
$$
\sum_{i=0}^{m}C_n^iC_m^i=C_{n+m}^m
$$
用 $n$ 替换式 $(5)$ 中的 $m$ 即可得到
$$
\sum_{i=0}^n\left(C_n^i\right)^2=C_{2n}^n
$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注