2014/03/26

ヴァンデルモンドの畳み込みの証明

分野: 場合の数  レベル: マニアック

ヴァンデルモンドの畳み込み:
以下の恒等式が成立する:
$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$
ただし,$p < k$ のとき${}_p\mathrm{C}_k=0$ と約束する。

この恒等式はヴァンデルモンドの畳み込み(Vandermonde’s convolution),ヴァンデルモンドの恒等式(Vandermonde’s identity)などと呼ばれる有名な恒等式です。

  • 某有名予備校の模試でそのまんま出題されたことがあります。
  • 2014千葉大後期数学科で似たような問題が出題されたらしいです。

二項係数の関係式を導く問題のよい例となっているのでおさえておきましょう。

数学的帰納法を用いた証明

方針:二項係数の関係式を証明する問題の多くは数学的帰納法を用いれば大抵クリアできます。パスカルの三角形の性質を用います。

畳み込みの証明

証明

$q,n$ に関する数学的帰納法で証明する。 $n=0$ のときは $1=1$ より成立。
$q=0$ のときは,左辺も右辺も${}_{p}\mathrm{C}_n$ となり成立。
$(q-1,n)$ 及び$(q-1,n+1)$ で成立すると仮定して$(q,n+1)$ の場合を考える。
$\displaystyle\sum_{k=0}^{n+1}{}_{p}\mathrm{C}_{k}\cdot{}_{q}\mathrm{C}_{n+1-k}\\
=\displaystyle\sum_{k=0}^{n+1}{}_{p}\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n+1-k}+\displaystyle\sum_{k=0}^{n+1}{}_{p}\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n-k}\\
=\displaystyle\sum_{k=0}^{n+1}{}_p\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n+1-k}+\displaystyle\sum_{k=0}^{n}{}_{p}\mathrm{C}_{k}\cdot{}_{q-1}\mathrm{C}_{n-k}\\
={}_{p+q-1}\mathrm{C}_{n+1}+{}_{p+q-1}\mathrm{C}_{n}\\
={}_{p+q}\mathrm{C}_{n+1}$
ここで,1行目から2行目への変形と,最終行への変形で二項係数の関係式(パスカルの三角形の性質)を用いた。3行目から4行目への変形で帰納法の仮定を用いた。

このように,パスカルの三角形の性質を用いて $n$ の小さい場合に帰着させて帰納法で証明する手法は頻出なのでおさえておきましょう!

二項定理を用いたエレガントな証明

方針:二項係数の関係式を証明する問題の多くは二項定理をうまく利用してやるとクリアできます。式の形を見てうまく適用する必要があるので鍛錬と少しの発想力が必要です。

証明

${}_{p+q}\mathrm{C}_n$ は$(x+1)^{p+q}$ を展開したときの $x^n$ の係数である。
この係数をもう1つ別の方法で求める。
$(x+1)^{p+q}=$$(x+1)^p$ $(x+1)^q$
= $\displaystyle\sum_{k_1=1}^p{}_{p}\mathrm{C}_{k_1}x^{k_1}$ $\displaystyle\sum_{k_2=1}^q{}_{q}\mathrm{C}_{k_2}x^{k_2}$
$x^n$ の係数は $k_1+k_2=n$ となる $k_1,k_2$ に対応する項から出てくるので以下のように表される:
$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_{k_1}\cdot{}_{q}\mathrm{C}_{n-k_1}$
以上からヴァンデルモンドの畳み込みが証明された。

場合の数を2通りの方法で考える証明

少々テクニカルですがこんな方法もあります。

証明

男 $p$ 人,女 $q$ 人,合計 $p+q$ 人の中から $n$ 人選ぶ場合の数を考える。
男を何人選ぶかで場合分けして$(k=0,1,2,\cdots, n)$ 足し上げると左辺の式になり,全体 $p+q$ 人から一挙に $n$ 人選ぶと右辺の式になる。

さらにさらに,ここでは省略しますが最短経路の数に意味づけて証明することもできます。
二項係数の関係式を証明するテクニックに関しては二項係数の有名公式を2つの方法で導くも参考にしてみてください。

二項係数の関係式は代数的にも証明できるし場合の数の意味を考えても証明できることが多い,いろいろな方法を試してみよう

Tag: 数学的帰納法のパターンまとめ

分野: 場合の数  レベル: マニアック