2015/11/07

二項係数の和,二乗和,三乗和

分野: 場合の数  レベル: 最難関大学

二項係数の総和,二乗和,三乗和に関する美しい公式を解説します。
$n$ は $0$ 以上の任意の整数とします。

二項係数の和

$\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k=2^n$
$\displaystyle\sum_{k=0}^n(-1)^k{}_n\mathrm{C}_k=0$

例えば $n=4$ のとき,
${}_4\mathrm{C}_0+{}_4\mathrm{C}_1+{}_4\mathrm{C}_2+{}_4\mathrm{C}_3+{}_4\mathrm{C}_4=1+4+6+4+1=2^4$
${}_4\mathrm{C}_0-{}_4\mathrm{C}_1+{}_4\mathrm{C}_2-{}_4\mathrm{C}_3+{}_4\mathrm{C}_4=1-4+6-4+1=0$
となっています。

証明は二項定理を使うだけで簡単にできます。

証明

二項定理より
$2^n=(1+1)^n=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k1^k1^{n-k}=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k$
$0=(-1+1)^n=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k(-1)^k1^{n-k}=\displaystyle\sum_{k=0}^n(-1)^k{}_n\mathrm{C}_k$

二項係数の二乗和

$\displaystyle\sum_{k=0}^n({}_n\mathrm{C}_k)^2={}_{2n}\mathrm{C}_n$

例えば $n=3$ のとき,${}_6\mathrm{C}_3=20$,
$({}_3\mathrm{C}_0)^2+({}_3\mathrm{C}_1)^2+({}_3\mathrm{C}_2)^2+({}_3\mathrm{C}_3)^2=1^2+3^2+3^2+1^2=20$
となり一致しています。2通りの証明を紹介します。

証明1

二項係数の二乗和

図のような格子状の道において,$(0,0)$ から$(n,n)$ までの最短経路の数を2通りの方法で数える。

  • $n$ 個の「右」と $n$ 個の「上」を並べる場合の数に等しいので,${}_{2n}\mathrm{C}_n$ 通り。
  • 途中で$(0,n),(1,n-1),\cdots, (n,0)$ を必ず1つだけ通る。そして,$(k,n-k)$ を通る最短経路の数は,$({}_n\mathrm{C}_k)^2$ である。($(k,n-k)$ まで行く方法が${}_n\mathrm{C}_k$ 通り,そこから$(n,n)$ まで行く方法も${}_n\mathrm{C}_k$ 通り)

よって,目標の式は示された。

証明2

ヴァンデルモンドの畳み込みで証明した式:
$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k{}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$
において,$p=n,q=n$ とすると,
$\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k{}_n\mathrm{C}_{n-k}={}_{2n}\mathrm{C}_n$
を得る。これと${}_n\mathrm{C}_{n-k}={}_n\mathrm{C}_k$ より目標の式を得る。

二項係数の三乗和

Dixonの恒等式:
$\displaystyle\sum_{k=-n}^n(-1)^k({}_{2n}\mathrm{C}_{n+k})^3=\dfrac{(3n)!}{(n!)^3}$

例えば $n=2$ のとき,
$({}_4\mathrm{C}_0)^3-({}_4\mathrm{C}_1)^3+({}_4\mathrm{C}_2)^3-({}_4\mathrm{C}_3)^3+({}_4\mathrm{C}_4)^3\\=1-64+216-64+1=90$
$\dfrac{6!}{(2!)^3}=90$
となり一致しています。

証明は難しいようです(少なくとも僕は簡単な証明を知りません,ご存知の方はご一報ください)。

シンプルで非自明な恒等式が大好きです。

Tag: 数列の和を計算するための公式まとめ

分野: 場合の数  レベル: 最難関大学