コンテンツへスキップ
Topos Uranos
日本語

初等的な組合せ論と二項定理

要約

この課では、有限集合の要素を一つずつ列挙することなく数えるための初等的な技法を学ぶ。有限集合の要素の個数を全単射によって定義し、その定義から和の法則と積の法則を証明し、そこから全部を並べる順列、一部を取って並べる順列、組合せの個数を導き、二項係数を定義して、その対称性とパスカルの法則を数え上げと計算の両方で証明する。続いてそれらの係数をパスカルの三角形に並べ、乗法公式を一般化する二項定理を帰納法で証明し、累乗の展開、係数の求め方、数値の近似に応用する。自然数を扱う単元で内容を学ぶ最後の課であり、この単元はまとめと挑戦課題の課で締めくくられる。

学習目標

  1. 和の法則と積の法則を用いて列挙せずに数え、選択の条件が互いに干渉するときは場合分けをする。
  2. 全部を並べる順列、一部を取って並べる順列、組合せを区別し、階乗を用いてそれらの個数を計算する。
  3. 二項係数の性質を数え上げと計算によって証明し、それを用いてパスカルの三角形を作る。
  4. 二項定理を証明し、累乗の展開、係数の計算、累乗の近似に応用する。

数え上げの原理

有限集合の要素を数えることは、その集合を要素ごとにたどれる間は、算術でもっとも基本的な操作である。しかし、要素が複合的な選択を行う方法であるとき、たとえば十冊の本を棚に並べたり、三十人の中から三人の代表を選んだりする場合には、列挙は実行不可能になり、個数は選択をいくつかの部分や段階に分解することで求められる。初等的な組合せ論の全体は二つの原理に基づいており、それらは「数える」とは何を意味するかの正確な定義から証明される。

集合の要素を数えるとは、要素に番号を付けること、すなわち 11 から nn までの各数に要素を一つずつ、重複も漏れもなく割り当てることである。集合 AA がnn 個の要素をもつ（nn は自然数）とは、集合 {1,2,…,n}\{1, 2, \ldots, n\} から AA への全単射、すなわち異なる数を異なる要素に移し、AA のすべての要素に到達する関数が存在することをいう。空集合は 00 個の要素をもち、集合が有限であるとは、空であるか、nn 個の要素をもつ（nn はある自然数）ことをいう。全単射、その合成、その逆関数は集合・関係・関数の課で学ぶ。

証明なしに認める事実（要素の個数）。有限集合の要素の個数がきちんと定まることを、証明なしに認める。すなわち、一つの集合が mm 個の要素と nn 個の要素を同時にもつことは、m≠nm \neq n ならばありえない。また、有限集合の部分集合はすべて有限であることも認める。

どちらの事実も nn についての帰納法で証明される。第一の事実は本質的には鳩の巣原理であり、それによれば、n+1n + 1 個の数（{1,…,n+1}\{1, \ldots, n + 1\} の数）を {1,…,n}\{1, \ldots, n\} の互いに異なる数に移す関数は存在しない。これらの証明は長く、後で使う考え方ももたらさないので、ここでは認めることにする。第一の事実がなければ「要素の個数」という表現は意味をもたず、同じ集合を二通りに数える組合せ論的証明は、二つの結果が等しいと結論できない。

命題和の法則

AA が mm 個の要素をもち、BB が nn 個の要素をもち、AA と BB が共通の要素をもたないならば、A∪BA \cup B は m+nm + n 個の要素をもつ。図は m=3m = 3、n=2n = 2 の場合に証明をたどる。

証明

  1. A={f(1),…,f(m)},B={g(1),…,g(n)}A = \{f(1), \ldots, f(m)\}, \quad B = \{g(1), \ldots, g(n)\}

    仮定により、全単射 ff（{1,…,m}\{1, \ldots, m\} から AA への）と、もう一つの全単射 gg（{1,…,n}\{1, \ldots, n\} から BB への）がある。各集合の要素は重複なく番号付けされている。

  2. i≤m ∨ i=m+j,1≤j≤n\dato{p}{i \leq m \ \vee \ i = m + j, \quad 1 \leq j \leq n}

    三分律により、各数 ii（11 から m+nm + n まで）は i≤mi \leq m または i>mi > m を満たす。後者の場合、順序の定義により、i=m+ji = m + j となる自然数 jj があり、加法の簡約法則によりそれはただ一つで、加法の単調性により j≤nj \leq n である。

  3. h(i)=f(i),h(m+j)=g(j)\dato{h}{h(i) = f(i), \quad h(m + j) = g(j)}

    hh を {1,…,m+n}\{1, \ldots, m + n\} 上で定義する。最初の mm 個の数は ff と同じように番号付けし、それに続く nn 個の数は gg と同じように番号付けする。

  4. A∩B=∅→f(i)≠g(j)A \cap B = \emptyset \rightarrow \resaltar{f(i) \neq g(j)}

    関数 hh は異なる数を異なる要素に移す。同じ部分の二つの数については ff と gg がそうするからであり、別々の部分の二つの数については、一方は AA の要素に、他方は BB の要素に移り、両者は共通の要素をもたないからである。

  5. A∪B={h(1),…,h(m),h(m+1),…,h(m+n)}A \cup B = \{h(1), \ldots, h(m), h(m + 1), \ldots, h(m + n)\}

    関数 hh は和集合のすべての要素に到達する。AA の要素は ff の値であり、BB の要素は gg の値である。

  6. h:{1,…,m+n}→A∪Bh : \{1, \ldots, \resaltar{m + n}\} \to A \cup B

    したがって、hh は {1,…,m+n}\{1, \ldots, m + n\} から A∪BA \cup B への全単射であり、和集合は m+nm + n 個の要素をもつ。一方の集合が空であれば、主張は明らかである。

部分の個数についての帰納法により、この原理は、どの二つも共通の要素をもたない任意の有限個の集合に拡張される。A1,…,ArA_1, \ldots, A_r の和集合は、それぞれ n1,…,nrn_1, \ldots, n_r 個の要素をもつとき、n1+⋯+nrn_1 + \cdots + n_r 個の要素をもつ。最初の r+1r + 1 個の和集合は、最初の rr 個の和集合と最後の一つとの和集合であり、最後の一つはそれらと共通の要素をもたないからである。この原理から、段階を追って行う選択を数える第二の原理が導かれる。

命題積の法則

ある選択が二つの段階で行われ、第一段階が mm 通り、第二段階が第一段階の結果によらず nn 通りで行えるならば、選択全体は m⋅nm \cdot n 通りで行える。図は n=4n = 4 として、各選択全体を、その第一段階の行に置いた点として描く。

証明

  1. E=E1∪E2∪⋯∪EmE = E_1 \cup E_2 \cup \cdots \cup E_m

    選択全体を第一段階によって分類する。共通の要素をもたない mm 個の類 E1,…,EmE_1, \ldots, E_m があり、各類は nn 個の要素、すなわちその第一段階の選択を完成させる nn 通りの方法をもつ。

  2. 1⋅n=n1 \cdot n = n

    類の個数 mm についての帰納法で進める。初段：m=1m = 1 ならば、すべての選択は E1E_1 に属し、それは nn 個の要素をもつ。

  3. E1∪⋯∪Ek,k⋅n\dato{h}{E_1 \cup \cdots \cup E_k}, \quad k \cdot n

    帰納段階：共通の要素をもたない kk 個の類（各類は nn 個の要素をもつ）の和集合が k⋅nk \cdot n 個の要素をもつと仮定する。

  4. (E1∪⋯∪Ek)∪Ek+1,k⋅n+n(E_1 \cup \cdots \cup E_k) \cup \resaltar{E_{k + 1}}, \quad k \cdot n + \resaltar{n}

    k+1k + 1 個の類の和集合は、最初の kk 個の類の和集合と最後の類との和集合であり、最後の類はそれらと共通の要素をもたない。和の法則により、それは k⋅n+nk \cdot n + n 個の要素をもつ。

  5. k⋅n+n=(k+1)⋅nk \cdot n + n = \resaltar{(k + 1) \cdot n}

    演算の課で積の交換法則を証明する際に示した補題 S(k)⋅n=k⋅n+nS(k) \cdot n = k \cdot n + n により、この数は (k+1)⋅n(k + 1) \cdot n である。

  6. E1∪⋯∪Em,m⋅nE_1 \cup \cdots \cup E_m, \quad \resaltar{m \cdot n}

    数学的帰納法の原理により、mm 個の類の和集合は m⋅nm \cdot n 個の要素をもつ。すなわち選択全体は m⋅nm \cdot n 通りで行える。図では 3⋅4=123 \cdot 4 = 12 である。

同様に、段階の個数についての帰納法により、積の法則は任意の有限個の段階に拡張される。rr 段階からなる選択で、各段階がそれぞれ n1,n2,…,nrn_1, n_2, \ldots, n_r 通りで行えるものは、n1n2⋯nrn_1 n_2 \cdots n_r 通りで行える。たとえば、位取り記数法の課で学んだ十進法では、三桁の数は 9⋅10⋅10=9009 \cdot 10 \cdot 10 = 900 個ある。最初の桁は 00 にはなれず、残りの二桁は自由だからである。注意すべきは、積の法則が要求するのは各段階の選択肢の個数がそれ以前の選び方によらないことであり、選択肢そのものは依存してよいという点である。この条件が成り立たないときは、条件が成り立つ場合に分け、それらの結果を和の法則で足し合わせる。

選択の相次ぐ段階は樹形図で表される。根と呼ぶ始点から、第一段階の選択肢の数だけ枝が出て、各枝の先から第二段階の選択肢の数だけ枝が出る、というように続いていく。根から最終的な先端、すなわち葉までの各道筋が一つの選択全体であり、積の法則は葉を描かずにその数を数える。

例数字 11、22、33 でできる三桁の数

数字 11、22、33 を重複なく使って書ける三桁の数を数え、重複を許した場合に得られる数と比べよ。

証明

  1. 3\resaltar{3}

    最初の桁は三つの数字のどれでもよい。根から三本の枝が出る。

  2. 3⋅2=63 \cdot \resaltar{2} = \resaltar{6}

    最初の桁を選ぶと、それが何であっても二番目の桁には二つの数字が残る。各枝は二つに分かれ、積の法則により、可能な始まり方は六通りある。

  3. 3⋅2⋅1=6\dato{p}{3 \cdot 2 \cdot \resaltar{1} = \resaltar{6}}

    三番目の桁には一つの可能性しか残らないので、各始まり方はただ一通りに完成する。

  4. 123, 132, 213, 231, 312, 321123, \ 132, \ 213, \ 231, \ 312, \ 321

    根から読んだ木の葉が求める六つの数であり、小さい順に並んでいる。

  5. 3⋅3⋅3=27\resaltar{3 \cdot 3 \cdot 3} = \resaltar{27}

    数字の重複を許すと、各段階の選択肢は三つになり、木の葉は重複なしの場合よりはるかに多くなる。