二項係数の定義を確認しておこう。

二項係数の定義

nCk=n!/{k!*(n-k)!}

ここから、容易に次のことがわかる。

二項係数の関係式

nCk=nC(n-k)

証明

定義より明らか。

つぎに、二項係数をより扱いやすくするために、漸化式を求めよう。これにより、パスカルの三角形が二項係数を表示していることが得られる。

パスカルの公式

nCk+nC(k+1)=(n+1)C(k+1)

証明

n!/{k!(n-k)!}+n!/{(k+1)!(n-k-1)!}=(k+1)n!/{(k+1)!(n-k)!}+(n-k)n!/{(k+1)!(n-k)!}=(n+1)!/{(k+1)!(n-k)!}=(n+1)C(k+1)

ここから、二項定理が証明できる。

二項定理

(1+x)^n=Σ(k=0→n) nCkx^k

証明

数学的帰納法で示そう。n=0、1の時は正しい。nの時正しいとして、n+1の時を示そう。(1+x)^(n+1)

=(1+x)(1+x)^n

=(1+x)Σ(k=0→n)nCk x^k

=Σ(k=0→n)nCk x^k + Σ(k=0→n)nCk x^(k+1)

=Σ(k=0→n)nCk x^k+Σ(k=1→n+1)nC(k-1) x^k

=1+Σ(k=1→n)nCk x^k+Σ(k=1→n)nC(k-1) x^k +x^(n+1)

=1+Σ(k=1→n)(n+1)Ck x^k +x^(n+1)

=Σ(k=0→n+1)(n+1)Ck x^k

よって示せた。

Σの取り扱いになれていればかなり簡単な証明だった。だが、この二項定理からわかる恒等式もたくさん存在する。

二項係数の和

Σ(k=0→n)nCk=2^n

証明

二項定理にx=1を代入せよ。

二項係数の交対和

Σ(k=0→n)(-1)^k nCk=0

証明

二項定理にx=-1を代入せよ。

二項係数の公式の多くは組み合わせからでも導出することができる。組み合わせは問題が思いつけば簡単だが、問題を思いつくのが難しい。

ヴァルデルモンドのたたみ込み

(p+q)Cn=Σ(k=0→n)pCk qC(n-k)

証明

(p+q)人からn人を選ぶときの組み合わせを考える。定義よりこれは、(p+q)Cn。

p人の中からi人選び、q人の中から(n-i)人選ぶとき、その組み合わせは、pCi qC(n-i)。これを、i=0→nまで足し合わせればよい。

二項係数の二乗和

Σ(k=0→n)nCk^2=2nCn

証明

ヴァルデルモンドのたたみ込みにおいて、p=q=nとおいてしまえばよい。

Dixonの恒等式

Σ(k=-a→a)(-1)^k (a+b)C(a+k) (b+c)C(b+k) (c+a)C(c+k)=(a+b+c)!/{a!b!c!}、ただし、a、b、cは非負整数。

証明

m、rを非負の整数として、xを実数変数とする。xCr={x(x-1)(x-2)......(x-r+1)}/r!と定義する。

P(x)=Σ(k=0→2r)(-1)^k (m+2r)C(m+k) xCk (x+m)C(m+2r-k)と定義する。

P(x)が-m-r、-m-r+1、-m-r+2......r-1を根とする多項式であることを示そう。

x=0、1......r-1のときを示す。k=0→2rであることに気をつける。0≦x＜kのときxCk=0、k≦xのとき、x+k≦2x＜2rよって、x+m＜x+2r-kが導け、(x+m)C(m+2r-k)=0が導けた。

x=-m、-m+1......-1のとき、x+k＜2rが成り立ち、P(x)=0。

x=-m-r、-m-r+1......-m-1の時、x=-p-1とおくことで、p=m,m+1,m+2......m+r-1とができて、

P(-p-1)

=Σ(k=0→2r)(-1)^k(m+2r)C(m+k) (-p-1)Ck (-p-1+m)C(m+2r-k)

=Σ(k=0→2r)(-1)^k(m+2r)C(m+k) (-1)^k(p+k)Ck (-1)^(m-k)(p+2r-k)C(m+2r-k)

m≦p＜m+r-1を固定する。このとき、-m≦k＜0では、(p+k)Ck=0であるので、

Σ(k=-m→2r)(-1)^(k-m) (m+2r)C(m+k) (p+k)Ck (p+2r-k)C(m+2r-k)

=Σ(k=0→2r+m)(-1)^k (m+2r)Ck (p+k-m)C(k-m) (p+2r-k+m)C(2m+2r-k)

=Σ(k=0→2r+m)(-1)^k (m+2r)Ck (p+k-m)Cp (p+2r-k+m)C(p-m)

(p+k-m)Cp (p+2r-k+m)C(p-m)はkについての2p-m次多項式と思える。2p-m＜2(m+r)-m=m+2rであるので、(p+k-m)Cp (p+2r-k+m)C(p-m)はΣ(i=0→m+2r-1)a_i k^iと書けて、これを、Σ(k=0→2r+m)(-1)^k (m+2r)Ck (p+k-m)Cp (p+2r-k+m)C(p-m)に代入すると、

Σ(k=0→2r+m){(-1)^k (m+2r)CkΣ(i=0→m+2r-1)a_i k^i}

=Σ(i=0→2r-m-1)a_iΣ(k→2r-m)(-1)^k (2r-m)Ck k^i

ここで左辺は、Σ(k→2r-m)(-1)^k (2r-m)Ck k^iは有名な等式、Σ(k=0→n)(-1)^k nCk k^r=0（0≦r＜n）より、0となる。この等式は、二項定理により、(1+x)^nを展開して、r回微分することにより得られる。ここまでの議論により、示したいことは示せた。ここで、Q(x)=(-1)^r xCr (x+m+r)C(m+r)とする。この多項式は、x=-m-r、-m-r+1、-m-r+2......r-1を根とする多項式を成す。なぜなら、xCrはx=0,1......r-1を根とする多項式を成し、(x+m+r)C(m+r)はx=-1,-2......-m-rを根とする多項式を成すからだ。

多項式では、次数よりも一つ多い点で値が等しければ、多項式自体が等しいという定理が成り立つ。ここで、

P(r)=Q(r)を示す。P(r)=Σ(k=0→2r)(-1)^k (m+2r)C(m+k) rCk (r+m)C(m+2r-k)

r＜kでは、rCk=0、k＜rではm+2r-k＞m+rより、(r+m)C(m+2r-k)=0なので、k=rのときにしか非零項は出てこない。つまり、P(r)=(-1)^r (m+2r)C(m+r)。Q(r)は簡単にわかるとおり、(-1)^r (m+2r)C(m+r)となるので、P(r)=Q(r)。P(x)とQ(x)は次数より一つ多い点で重なっているので、P(x)=Q(x)。

Dixonの恒等式はこの等式で、x=c+a、m=b-a、r=aとしたときに出てくる。

二項係数の三乗の交代式

Σ(k=-n→n)(-1)^k {2nC(n+k)}^3=(3n)!/{(n!)^3}

証明

Dixonの恒等式で、a=b=c=nとすると出る。