二項係数の有名公式一覧と2つの証明方針

  • 二項係数の有名公式を紹介していきます。
  • 二項係数の関係式を証明するための2通りのアプローチを紹介します。

二項係数とは

  • nn 個のものから rr 個を(順番を考慮せず)選ぶ組合せの数です。
  • nCr{}_n\mathrm{C}_r と書きます。(nr)\dbinom{n}{r} と書くこともあります。
  • 具体的には,nCr=n!r!(nr)!{}_n\mathrm{C}_r=\dfrac{n!}{r!(n-r)!}です。
  • このページでは,nn は正の整数,rr00 以上 nn 以下の整数とします。

二項係数の基本的な公式

二項係数の基本的な公式を2つ紹介します。それぞれ2通りの証明を解説します。

性質1

nCr=nCnr{}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}

「パスカルの三角形は左右対称」という意味の式です。

組み合わせの意味を考える証明

nn 個のものから rr 個のものを選ぶ組み合わせの数は,nrn-r 個の「選ばないものを選ぶ」組み合わせの数に等しい。

計算による証明

nCr=n!r!(nr)!=n!(nr)!{n(nr)}!=nCnr{}_n\mathrm{C}_r=\dfrac{n!}{r!(n-r)!}\\ =\dfrac{n!}{(n-r)!\{n-(n-r)\}!}\\ ={}_n\mathrm{C}_{n-r}

次は,パスカルの三角形で「上の2つの数字の和が下と等しい」という性質です。

性質2(パスカルの法則)

nCr=n1Cr+n1Cr1{}_n\mathrm{C}_r={}_{n-1}\mathrm{C}_r+{}_{n-1}\mathrm{C}_{r-1}

組み合わせの意味を考える証明

(特定のものAを含む)nn 個のものから rr 個のものを選ぶ組み合わせの数は

「Aを選ばず残り n1n-1 個の中から rr 個のものを選ぶ組み合わせの数」
+「Aを選び残り n1n-1 個の中から r1r-1 個のものを選ぶ組み合わせの数」

に等しい。

計算による証明

右辺を変形していく。

n1Cr+n1Cr1=(n1)!r!(n1r)!+(n1)!(r1)!(nr)!=(n1)!(r1)!(n1r)!(1r+1nr)=n!r!(nr)!=nCr{}_{n-1}\mathrm{C}_r+{}_{n-1}\mathrm{C}_{r-1}\\ =\dfrac{(n-1)!}{r!(n-1-r)!}+\dfrac{(n-1)!}{(r-1)!(n-r)!}\\ =\dfrac{(n-1)!}{(r-1)!(n-1-r)!}\left(\dfrac{1}{r}+\dfrac{1}{n-r}\right)\\ =\dfrac{n!}{r!(n-r)!}\\ ={}_n\mathrm{C}_r

二項係数の関係式の証明方針

上の2つの公式の証明で見たように,二項係数の関係式は多くの場合,組み合わせの意味を考える方法でも nCr=n!r!(nr)!{}_n\mathrm{C}_r=\dfrac{n!}{r!(n-r)!} という定義式を使って計算する方法でも証明できます。

  • 組み合わせの意味を考える方法は,ひらめきが必要になりますが,美しい場合が多く気合いも必要ないです。
  • 定義式を使って計算する方法は,公式の組み合わせ的な意味を忘れて計算していきます。機械的な計算で証明できることが多いですが,複雑な公式の証明では計算が大変で気合いが必要です。

重要なのは,同じ公式を代数的にも組み合わせ的にも捉えることができる,ということです。代数的によくわからなくて覚えづらい公式も組み合わせ的な意味を考えればスッキリすることがあるし,逆もまた然りです。

また,二項係数の和に関する等式は二項定理を使って証明することも多いです。

整数問題に応用できる公式

性質3

rnCr=nn1Cr1r{}_n\mathrm{C}_r=n{}_{n-1}\mathrm{C}_{r-1}

組み合わせの意味を考える証明

nn 人から rr 人採り,1人をリーダーにする組み合わせの数を2通りの方法で考える。

nn 人の中から rr 人選んでそのグループのリーダーを選ぶ組み合わせの数」
=「nn 人の中から1人リーダーを選んで残り n1n-1 人から r1r-1 人選ぶ組み合わせの数」

計算による証明

rnCr=rn!r!(nr)!=n(n1)!(r1)!(nr)!=nn1Cr1r{}_{n}\mathrm{C}_r\\ =r\dfrac{n!}{r!(n-r)!}\\ =n\dfrac{(n-1)!}{(r-1)!(n-r)!}\\ =n{}_{n-1}\mathrm{C}_{r-1}

性質3より,以下がわかります。
nn が素数で 1rn11\leq r\leq n-1 のとき nCr{}_n\mathrm{C}_rnn の倍数となる」

この事実は,難関大学の入試や数学オリンピックで役立つことがあるので頭の片隅にとどめておくとよいでしょう。

より複雑な関係式

  • k=0nnCk=2n\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_k=2^n
  • k=0n(1)knCk=0\displaystyle\sum_{k=0}^n(-1)^k{}_n\mathrm{C}_k=0
  • k=0n(nCk)2=2nCn\displaystyle\sum_{k=0}^n({}_n\mathrm{C}_k)^2={}_{2n}\mathrm{C}_n
  • k=nn(1)k(2nCn+k)3=(3n)!(n!)3\displaystyle\sum_{k=-n}^n(-1)^k({}_{2n}\mathrm{C}_{n+k})^3=\dfrac{(3n)!}{(n!)^3}

→証明は 二項係数の和,二乗和,三乗和

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

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

k=1nkn(1)n+knCkn!=1\displaystyle\sum_{k=1}^n\dfrac{k^n(-1)^{n+k}{}_n\mathrm{C}_k}{n!}=1

証明の概要

3通りの証明方法を紹介する。

  1. (1+x)n=k=0nnCkxk(1+x)^n=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_kx^k
    に対して「両辺微分して xx をかける」ことを nn 回繰り返す。その結果に x=1x=-1 を代入すると,右辺は k=1nkn(1)knCk\displaystyle\sum_{k=1}^nk^n(-1)^k{}_n\mathrm{C}_k になる。左辺は n!(1)nn!(-1)^n になる。
    (左辺について微分をきちんと計算するのはしんどいが,(1+x)(1+x) を含む項は x=1x=-1 を代入して消えることに注意すると x=1x=-1 を代入した結果ならわりと簡単に計算できる)

  2. 包除原理を使って「11 から nn が全て現れる長さ nn の数列の個数」を数えることでも k=1nkn(1)nknCk=n!\displaystyle\sum_{k=1}^nk^n(-1)^{n-k}{}_n\mathrm{C}_k=n! が導出できる。

  3. 2と全く同じことだが,全射の個数の公式k=nk=n とすることでも同じ式を得る。

二項係数の上界・下界
  • (nk)knCk(nke)k\left(\dfrac{n}{k}\right)^k\leqq {}_n\mathrm{C}_k\leqq\left( \dfrac{n}{k}e\right)^k

  • 1n+12nH(kn)nCk2nH(kn)\dfrac{1}{n+1}2^{nH(\frac{k}{n})}\leqq{}_n\mathrm{C}_k\leqq2^{nH(\frac{k}{n})}

→証明は 二項係数の上界・下界を与える4つの不等式

ホッケースティック恒等式

nr0n\geqq r\geqq 0 に対して,

k=rnkCr=n+1Cr+1\displaystyle\sum_{k=r}^n{}_k\mathrm{C}_r={}_{n+1}\mathrm{C}_{r+1}

名前がおもしろいです。性質2(パスカルの法則)を繰り返し使えば簡単に証明できます。わかりにくければパスカルの三角形を書いてみてください。

1つの公式を複数の観点で理解することで,応用の幅が広がります。他にもおもしろい二項係数の等式があればぜひ教えてください。