1. 高校数学の美しい物語
  2. ヴァンデルモンドの畳み込みの3通りの証明

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

更新日時 2021/03/07
ヴァンデルモンドの畳み込み

任意の非負整数 p,q,np,q,n に対して,

k=0npCkqCnk=p+qCn\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n

という恒等式が成立する。これをヴァンデルモンドの畳み込みと言う。 ただし,p<kp < k のとき pCk=0{}_p\mathrm{C}_k=0 と約束する。

目次
  • ヴァンデルモンドの畳み込みについて

  • 二項定理を用いた証明

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

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

ヴァンデルモンドの畳み込みについて

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

例えば,p=3,q=2,n=2p=3,q=2,n=2 としてみると,

  • 左辺は 3C02C2+3C12C1+3C22C0=1+6+3=10{}_3\mathrm{C}_0\cdot {}_2\mathrm{C}_2+{}_3\mathrm{C}_1\cdot {}_2\mathrm{C}_1+{}_3\mathrm{C}_2\cdot {}_2\mathrm{C}_0=1+6+3=10
  • 右辺は 5C2=10{}_5\mathrm{C}_2=10

となり確かに等しい。

  • p=q=np=q=n としてみると,k=0nnCknCnk=2nCn\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k\cdot {}_n\mathrm{C}_{n-k}={}_{2n}\mathrm{C}_n となります。さらに nCk=nCnk{}_n\mathrm{C}_k={}_n\mathrm{C}_{n-k} を使うと,k=0n(nCk)2=2nCn\displaystyle\sum_{k=0}^n({}_n\mathrm{C}_k)^2={}_{2n}\mathrm{C}_n となります。これは,二項係数の和,二乗和,三乗和でも紹介した有名な式です。

  • 以下では,ヴァンデルモンドの畳み込みを3通りの方法で証明します! 二項係数の関係式を導く良い例題です。

二項定理を用いた証明

方針

二項係数の関係式を証明する問題の多くは,二項定理をうまく利用すると解けます。式の形を見てうまく適用する必要があるので,鍛錬と少しの発想力が必要です。

証明

ヴァンデルモンドの畳み込みの右辺 p+qCn{}_{p+q}\mathrm{C}_n(x+1)p+q(x+1)^{p+q} を展開したときの xnx^n の係数である。

この係数をもう1つ別の方法で求める。

(x+1)p+q=(x+1)p(x+1)q=k1=0ppCk1xk1k2=0qqCk2xk2(x+1)^{p+q}\\ =(x+1)^p(x+1)^q\\ =\displaystyle\sum_{k_1=0}^p{}_{p}\mathrm{C}_{k_1}x^{k_1}\displaystyle\sum_{k_2=0}^q{}_{q}\mathrm{C}_{k_2}x^{k_2}

xnx^n の係数は k1+k2=nk_1+k_2=n となる k1,k2k_1,k_2 に対応する項から出てくるので以下のように表される:

k1=0npCk1qCnk1\displaystyle\sum_{k_1=0}^n{}_p\mathrm{C}_{k_1}\cdot{}_{q}\mathrm{C}_{n-k_1}

これは,ヴァンデルモンドの畳み込みの左辺なので,証明完了。

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

以下のような証明方法もあります。

証明

pp 人,女 qq 人,合計 p+qp+q 人の中から nn 人選ぶ場合の数を考える。

  • 全体 p+qp+q 人から一挙に nn 人選ぶと p+qCn{}_{p+q}\mathrm{C}_n 通りで, 右辺の式になる。

  • 男を何人選ぶかで場合分けして足し上げると左辺の式になる。具体的には,男が kk 人で女が nkn-k 人,を k=0,1,,nk=0,1,\dots,n まで足し上げると k=0npCkqCnk\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}

さらに,ここでは省略しますが最短経路の数に意味づけて証明することもできます。

二項係数の関係式を証明するテクニックに関しては二項係数の有名公式一覧と2つの証明方針も参考にしてみてください。

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

方針

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

証明

畳み込みの証明

q,nq,n に関する数学的帰納法で証明する。 n=0n=0 のときは 1=11=1 より成立。

q=0q=0 のときは,左辺も右辺も pCn{}_{p}\mathrm{C}_n となり成立。

(q1,n)(q-1,n) 及び (q1,n+1)(q-1,n+1) で成立すると仮定して (q,n+1)(q,n+1) の場合を考える。

k=0n+1pCkqCn+1k=k=0n+1pCkq1Cn+1k+k=0n+1pCkq1Cnk=k=0n+1pCkq1Cn+1k+k=0npCkq1Cnk=p+q1Cn+1+p+q1Cn=p+qCn+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行目への変形で帰納法の仮定を用いた。

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

なお,2014千葉大後期数学科で,ヴァンデルモンドの畳み込みと似たような問題が出題されたらしいです。

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

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

人気記事
  1. 高校数学の美しい物語
  2. ヴァンデルモンドの畳み込みの3通りの証明