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

更新日時 2021/07/30
  • 二項係数の有名公式を紹介していきます。
  • 二項係数の関係式を証明するための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{}_n\mathrm{C}_r =nCnr{}_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{}_n\mathrm{C}_r =n1Cr{}_{n-1}\mathrm{C}_r +n1Cr1{}_{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

rnCrr{}_n\mathrm{C}_r = nn1Cr1n{}_{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

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

1つの公式を複数の観点で理解することで,応用の幅が広がります。