二項定理

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

二項係数の有名公式を紹介し,それぞれ代数的な方法と組み合わせ的な方法で導きます。

特に3つ目の公式は整数問題にも応用することができる重要な公式です。

なお,二項定理の基本的な話題については二項定理の意味と2通りの証明を参照して下さい。

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

連続するn個の整数の積と二項係数

整数論の有名な公式:

連続する nn 個の整数の積は n!n! の倍数である。

上記の公式について,3通りの証明を紹介します。

→ 連続するn個の整数の積と二項係数

包除原理の2通りの証明

包除原理:

AB=A+BAB|A\cup B|=|A|+|B|-|A\cap B|

ABC=A+B+CABBCCA+ABC|A\cup B\cup C|\\ =|A|+|B|+|C|\\ -|A\cap B|-|B\cap C|-|C\cap A|\\ +|A\cap B\cap C|

より一般に,

A1A2An|A_1\cup A_2\cup\cdots\cup A_n|

=k=1n(1)k1=\displaystyle\sum_{k=1}^n(-1)^{k-1}kk個の「かつ」の総和)

=iAii<jAiAj=\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cap A_j|

+i<j<kAiAjAk+\sum_{i < j < k}|A_i\cap A_j\cap A_k|

+(1)n1A1An-\cdots +(-1)^{n-1}|A_1\cap\cdots\cap A_n|

上の2つの式は教科書でもおなじみの公式ですね。しかし,初めて包除原理を知った人にとっては最後の式は意味不明でしょう。

この記事では包除原理の意味と,2通りの証明を紹介します。

証明1.意味を考えつつ二項定理を用いる方法

証明2.数学的帰納法を用いてゴリゴリ計算していく方法

→ 包除原理の2通りの証明

ヴァンデルモンドの畳み込みの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

ただし,p<kp < k のとき pCk=0{}_p\mathrm{C}_k=0 と約束する。

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

  • 某有名予備校の模試でそのまんま出題されたことがあります。
  • 2014千葉大後期数学科で似たような問題が出題されたらしいです。

二項係数の関係式を導く問題のよい例となっているのでおさえておきましょう。

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