vandermonde_convolution
<p> 二項係数の性質の一つに以下のような「ヴァンデルモンドの畳み込み」と呼ばれる恒等式がある。 \[ \dbinom{p+q}{m} = \sum_{k=0,\; k\le p}^{m}\dbinom{p}{k}\cdot\dbinom{q}{m-k} \] </p> <p> これは、\(p+q\) 人から \(m\) を選ぶ場合の数は、\(p\) 人から \(k\) 人を選ぶ場合の数と \(q\) 人から残りの \(m-k\) 人選ぶ場合の数の積を \(k=1,\cdots,m\) に渡る総和に等しいことを表している。 </p> <h3>ヴァンデルモンドの畳み込みの導出</h3> <p> 数学的帰納法による証明は他に譲り、ここでは二項定理 \((x+y)^n\) による証明を取り上げる。 </p> <p> 二項定理： \[ (x+y)^n = \sum_{k=0}^{n}\dbinom{n}{k}x^{n-k}y^k \] において、\(x=1, n=p+q\) とすると、 \[ \begin{aligned} (1+y)^{p+q} &= \sum_{k=0}^{p+q}\dbinom{p+q}{k}y^k\\ (1+y)^p(1+y)^q &= \sum_{k=0}^{p+q}\dbinom{p+q}{k}y^k\\ \left(\sum_{i=0}^{p}\dbinom{p}{i}y^i\right)\left(\sum_{j=0}^{q}\dbinom{q}{j}y^j\right) &= \sum_{k=0}^{p+q}\dbinom{p+q}{k}y^k\\ \end{aligned} \] ここで、\(k=m\) となるのは \(m\le p+q,\; j=m-i\) なので、改めて \(i\to k,\; y=1\) とすれば以下のように求まる。 \[ \sum_{k=0,\; k\le p}^{m}\dbinom{p}{k}\cdot\dbinom{q}{m-k} = \dbinom{p+q}{m} \] </p>
Save as is
Save as TeX
Save as MathML
editor on/off
Programmed by Taiji Yamada <taiji@aihara.co.jp> at 2018/7/12.