范德蒙恒等式

             

预备知识 二项式定理

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

\begin{equation} \begin{pmatrix}a + b\\ n\end{pmatrix} = \sum_i \begin{pmatrix}a\\ i\end{pmatrix} \begin{pmatrix}b\\ n-i\end{pmatrix} = \sum\limits_i \begin{pmatrix}a\\n-i\end{pmatrix} \begin{pmatrix}b\\i\end{pmatrix} \end{equation}
其中求和是对所有使得表达式有意义的非负整数 $i$ 进行的.

1. 证明 1

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

   方法 1:根据定义,有 $N = \begin{pmatrix}a+b\\n\end{pmatrix} $ 种情况.

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

   由于这个问题只有一个答案,所以有 $ \begin{pmatrix}a+b\\n\end{pmatrix} = \sum_i \begin{pmatrix}a\\i\end{pmatrix} \begin{pmatrix}b\\n-i\end{pmatrix} $.

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

   证毕.

2. 证明 2

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

\begin{equation} \begin{aligned} (1 + x)^{m+n} &= \sum_{r=0}^{m+n} \begin{pmatrix}m+n\\r\end{pmatrix} x^r\\ &=(1+x)^m (1+x)^n\\ &=\sum_0^m \begin{pmatrix}m\\i\end{pmatrix} x^i \sum_{j=0}^n \begin{pmatrix}n\\j\end{pmatrix} x^j\\ &=\sum_{r=0}^{m+n} \sum_{k=0}^r \begin{pmatrix}m\\k\end{pmatrix} \begin{pmatrix}n\\r-k\end{pmatrix} x^r \end{aligned} \end{equation}


1. ^ 参考 Wikipedia 相关页面

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

广告位

投放详情

         

© 小时科技 保留一切权利