范德蒙恒等式

                     

贡献者: addis

预备知识 二项式定理

  1范德蒙恒等式(Vandermonde's identity)是指

\begin{equation} C_{a + b}^n = \sum_i C_a^i C_b^{n-i} = \sum\limits_i C_a^{n-i}C_b^i~. \end{equation}
其中求和是对所有使得表达式有意义的非负整数 $i$ 进行的,即
\begin{equation} \max \left\{0,\, n-b \right\} \leqslant i \leqslant \min \left\{a,\, n \right\} ~, \end{equation}
当 $a, b \geqslant n$ 时化简为
\begin{equation} 0 \leqslant i \leqslant n~. \end{equation}

1. 证明 1

   假设有编了号的 $a+b$ 个小球。不分顺序抓取 $n$ 个,求总共有几种情况(用 $N$ 表示)。

   方法 1:根据定义,有 $N = C_{a+b}^n$ 种情况。

   方法 2:先把球分成 $A$, $B$ 两组,分别有 $a$ 个和 $b$ 个。如果在 $A$ 组中抽取 $i$ 个球(有 $C_a^i$ 种情况),在 $B$ 组中只能抽取 $n - i$ 个(有 $C_b^{n-i}$ 种情况),所以一个 $i$ 对应 $C_a^i C_b^{n-i}$ 种情况。所有可能的 $i$ 一共有 $N = \sum_i C_a^i C_b^{n-i}$ 种情况。

   由于这个问题只有一个答案,所以有 $C_{a+b}^n = \sum_i C_a^i C_b^{n-i}$。

   但 $i$ 的范围具体从多少取到多少,由 $a$, $b$ 是否大于 $n$ 来决定。当 $a,b$ 都大于 $n$ 时,$i$ 可以从 0 取到 $n$, 如果其中至少有一个小于 $n$, 那么 $i$ 的取值不能使 $C$ 的上标大于下标。

   证毕。

2. 证明 2

   我们也可以通过二项式定理来证明

\begin{equation} \begin{aligned} (1 + x)^{a+b} &= \sum_{n=0}^{a+b} C_{a+b}^n x^n\\ &=(1+x)^a (1+x)^b\\ &=\sum_{i=0}^a C_a^i x^i \sum_{j=0}^b C_b^j x^j\\ &=\sum_{n=0}^{a+b} \sum_{i} C_a^i C_b^{n-i} x^n~. \end{aligned} \end{equation}
最后两步可以看作对一个表格求和,第 $i$ 行第 $j$ 列的值为 $C_a^i C_b^j x^{i+j}$,求和的方式有两种,一种是每行每列求和,另一种是延斜线求和,每条斜线 $n = i+j$ 的值相同。注意每条斜线中 $i$ 的范围未必相同,满足式 2

   由于多项式中每项的系数必须相同,就有式 1 ,证毕。


1. ^ 参考 Wikipedia 相关页面


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利