15.10 組合わせ論的証明

目次

\(n\) 枚の T シャツを持っていて、\(k\) 枚を捨てたいとする。このとき、捨てる \(k\) 枚を選ぶ問題は、取っておく \(n - k\) 枚を選ぶ問題と同一である。よって、\(n\) 枚の T シャツから \(k\) 枚を選ぶ方法の個数と、\(n\) 枚の T シャツから \(n - k\) 枚を選ぶ方法の個数は等しい。ここから次の等式が分かる:

\[ \binom{n}{k} = \binom{n}{n - k} \]

この等式は代数を使っても簡単に証明できる。両辺は次の式に等しい:

\[ \frac{n!}{k! (n-k)!} \]

しかし、証明で代数を使う必要は必要ない: 数え上げの考え方だけで証明は完了する。

15.10.1 Pascal の三角恒等式

「情報科学のための数学」の講義を担当する有名な教員 Zachザック は、シティボクシングチームのトライアウト (新しいメンバーを選ぶコンテスト) に参加することを決断した。彼は少し前にロッキーの映画を見てからというもの鏡の前で不敵な笑みを浮かべて「よぉ、俺とケンカしてぇのか？yo, you wanna piece a' me?」と何時間もブツブツ呟いていたので準備は万端だった。トライアウトには Zach を含めて \(n\) 人が参加し、その中から \(k\) 人が新しいメンバーとして選ばれる。メンバーの座を勝ち取る策略を練るために、彼はトライアウト後のチームに何通りの可能性があるかを計算することにした。彼は二つの場合を分けて考えた:

一つ目の場合が考えるチームには Zach が含まれ、二つ目の場合が考えるチームには Zach が含まれない。よってそれぞれの場合が考えるチームの集合は共通部分を持たない。従って加算則より、考えられる新しいチームの個数が求まる:

\[ \binom{n-1}{k-1} + \binom{n-1}{k} \]

Zach と同程度に有名な教員 Albertアルバート は、それほど強くなさそうな Zach が参加することを知って、自身もトライアウトに参加することにした。彼も Zach と同様に新しいチームに何通りの可能性があるかを計算した。ただ Albert は Zach と異なるアプローチを使った: \(n\) 人から \(k\) 人が選ばれるのだから、その選び方は単純に次の式で表されると彼は考えた:

\[ \binom{n}{k} \]

Albert と Zach は二人とも考えられる新しいチームの個数を正しく計算している。つまり、二つの式は等しい:

補題 15.10.1[Pascalパスカル の三角恒等式 (Pascal's triangle identity)]
\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \tag{15.7}\]

代数を使わずに Pascal の三角恒等式が証明できてしまった！ ここでも、代数の代わりに数え上げの考え方を使った証明が可能だった。

15.10.2 組合せ論的証明

こういった、数え上げの考え方を使った議論で代数的事実を示す証明を組合せ論的証明 (combinatorial proof) と呼ぶ。組合せ論的証明の多くは次の手順を踏む:

  1. 集合 \(S\) を定義する。

  2. 何らかの方法で \(|S| = n\) を示す。

  3. 別の方法で \(|S| = m\) を示す。

  4. \(n = m\) と結論付ける。

先ほどの例では、\(S\) が考えられる新メンバーの集合全体の集合であり、Zach は次の等式を示した:

\[ |S| = \binom{n-1}{k-1} + \binom{n-1}{k} \]

そして、Albert は Zach と別の方法で次の等式を示した:

\[ |S| = \binom{n}{k} \]

二つの式を等号で結べば、Pascal の三角恒等式が得られる。

組合せ論的証明の検証

組合せ論的証明を使うには同じものを異なる方法で数え上げる必要がある。様々な数え上げ手法に慣れていれば問題ないものの、もし自信がないときは全単射と列の数え上げを利用する方法を使って証明を検証できる。

例えば、Pascal の三角恒等式 \(\text{(15.7)}\) の組合せ論的証明を詳しく見てみよう。\(n\) 人の参加者を \(1\), \(2\), \(\ldots\), \(n\) とする。このとき \(S\) は集合 \(\left\{ 1, 2, \ldots, n \right\}\) の \(k\) 要素部分集合全体の集合となる。

Albert は部分集合則を使って \(|S| = \binom{n}{k}\) を得た。これに対して Zach は異なるアプローチを使った。Zach は参加者 \(n\) だと仮定して、次の二つの集合を定義する:

\[ \begin{aligned} \text{Zach-chosen} &::= \{ X \subseteq \left\{ 1, 2, \ldots, n \right\} \; | \; |X| = k - 1 \} \\ \text{Zach-not-chosen} &::= \{ Y \subseteq \left\{ 1, 2, \ldots, n \right\} \; | \; |Y| = k \} \end{aligned} \]

\(\text{Zach-chosen}\) に含まれる任意の集合は \(\text{Zach-not-chosen}\) に含まれる任意の集合より小さいので、\(\text{Zach-chosen}\) と \(\text{Zach-not-chosen}\) は共通部分を持たない。よって次の等式が成り立つ:

\[ | \text{Zach-chosen} \cup \text{Zach-not-chosen} | = | \text{Zach-chosen} | + | \text{Zach-not-chosen} | \]

また、部分集合則からは次の等式が分かる:

\[ \begin{aligned} | \text{Zach-chosen} | &= \binom{n-1}{k-1} \\[10pt] | \text{Zach-not-chosen} | &= \binom{n-1}{k} \end{aligned} \]

後は、次の全単射 \(f\) の存在を示せれば恒等式 \(\text{(15.7)}\) の証明が完了する:

\[ f \colon \text{Zach-chosen} \cup \text{Zach-not-chosen} \to S \]

次の \(f\) が条件を満たす全単射となる:

\[ f(s)::= \begin{cases} s \cup \left\{ n \right\} &\ \ |s| = k - 1 \text{ のとき}\\ s &\ \ |s| = k \text{ のとき}\\ \end{cases} \]

15.10.3 組合せ論的証明の例

組合せ論的証明の中で異なる方法を使って数え上げられる集合は、二人の教員に関するストーリーとは関係のない単純な列や集合である場合が多い。組合せ論的証明の例をさらにもう一つ示す。

定理 15.10.2
\[ \sum_{r=0}^{n} \binom{n}{r} \binom{2n}{n-r} = \binom{3n}{n} \]

証明 組合せ論的証明で示す。\(n\) 枚の異なる赤いカードと \(2n\) 枚の異なる黒いカードからなるデッキからランダムに \(n\) 枚のカードを引いたときに得られるカードの集合全体の集合を \(S\) とする。まず、\(|S|\) は \(3n\) 要素集合の \(n\) 要素部分集合の個数に等しいので、次の等式が分かる:

\[ |S| = \binom{3n}{n} \]

視点を変えると、\(r\) 枚の赤いカードが含まれる \(n\) 枚のカードの引き方は次の個数だけ存在する:

\[ \binom{n}{r} \binom{2n}{n-r} \]

なぜなら、\(r\) 枚の赤いカードの選択肢が \(\binom{n}{r}\) 通り、\(n - r\) 枚の黒いカードの選択肢が \(\binom{2n}{n-r}\) 通りあるからである。手札に含まれる赤いカードの枚数は \(0\) 以上 \(n\) 以下なので、\(n\) 枚の手札の個数 \(|S|\) は次の等式を満たす:

\[ |S| = \sum_{r=0}^{n} \binom{n}{r} \binom{2n}{n-r} \]

\(|S|\) の二つ表現を等号で結べば定理が証明される。 ■

組合せ論的証明の見つけ方

組合せ論的証明は魔法かのように思える。定理 15.10.2 は恐ろしい見た目をしているものの、その証明は代数的式変形を全く使わなかった。組合せ論的証明を作る上で鍵となるのは適切な \(S\) の選択である。これは簡単ではないものの、等式の単純な方の式がヒントとなる場合が多い。例えば、定理 15.10.2 の等式の右辺 \(\binom{3n}{n}\) からは、\(3n\) 要素集合の \(n\) 要素部分集合全体の集合を \(S\) とする選択肢が有望なものとして示唆される。

参考文献

[6], [10], [17]

広告