場合の数、数え上げの方法

1 場合の数、数え上げ

階乗（かいじょう、ファクトリアル）の記号とは n! = n(n − 1)(n − 2) ⋯ 3 · 2 · 1(n ≧ 1), 0! = 1 とする。「r 種類の箱に n 個のボールの中から選んで入れること」が場合の数を計算するための基本のことがらです。 \underline{順列}「区別のある箱」に「区別のあるボール」を入れる重複順列「重複を許してひとつの箱に何個入れてもよい場合」という条件で取り出された場合の数。

n^{r} = \overbrace{n × n × ⋯ n}^{r}  (1)

順列(permutation) 「重複は許さずにひとつの箱には高々ひとつしか入れない場合」という条件で取り出された場合の数。

\overbrace{n(n − 1)(n − 2) ⋯ (n − (r − 1))}^{r} = (n)_{r} = \frac{n!}{(n − r)!}  (2)

\underline{組合せ}「区別のある箱」に「区別のないボール」を入れる重複組合せ「重複を許してひとつの箱に何個入れてもよい場合」という条件。

\frac{n(n + 1)(n + 2) ⋯ (n + (r − 1))}{r!} = \binom{n + r − 1}{r} = \binom{n + r − 1}{n − 1}  (3)

組合せ(combination) 「重複は許さずにひとつの箱には高々ひとつしか入れない場合」という条件。

\frac{n(n − 1)(n − 2) ⋯ (n − (r − 1))}{r!} = \frac{(n)_{r}}{r!} = \binom{n}{r} = \binom{n}{n − r}  (4)

問 1.1 箱とボールがそれぞれ n = 5, r = 2 のとき、重複順列、順列、重複組合せ、組合せについてすべての場合を書き並べてみなさい。そして答えが一致していることを確かめよ。たとえば 5 個のボールを a, b, c, d, e としてそれぞれ書き上げてみなさい。

2 パスカル三角形

数式 (a + b)^{3} を展開してみれば、

(a + b)^{3} = a^{3} + 3a^{2}b + 3ab^{2} + b^{3}

となることは知られている。ここでそれぞれの係数をみると、 1, 3, 3, 1 となっている。 (a + b)^{3} = (a + b) × (a + b) × (a + b) であるから、たとえば 3a^{2}b という項は第 1 項から a, 第 2 項から a, 第 3 項から b としたときには a^{2}b が得られ、これを他の取り出しかた、第 1 項から a, 第 2 項から b, 第 3 項から a ととしても同じ a^{2}b を得る。もうひとつの取り出し、第 1 項から b, 第 2 項から a, 第 3 項から a として、これらの 3 通りがすべて a^{2}b になるから、結局 a^{2}b の係数は 3 で、 3a^{2}b となることがわかる。つまり次のような塊りとしてくくることで理解できるでしょう。

(a + b)^{3} = aaa \begin{matrix}+aab \\ +aba \\ +baa \end{matrix} \begin{matrix}+abb \\ +bab \\ +bba \end{matrix} + bbb

いくつかの項を計算してみます。最初の０次（ゼロ乗）が 0 となるのは計算ではなく、このように定めると考えていてください。順次に計算していけることがつぎの定理にある命題に結びついてくるはずです。

(a + b)^{0} · · · · · · 1
(a + b)^{1} · · · · · · 1 1
(a + b)^{2} · · · · · · 1 2 1
(a + b)^{3} · · · · · · 1 3 3 1
(a + b)^{4} · · · · · · 1 4 6 4 1
(a + b)^{5} · · · · · · 1 5 10 10 5 1
(a + b)^{6} · · · · · · 1 6 15 20 15 6 1

三角形に並べられてこの表をパスカル三角形とよびます。パスカルは確率論ではよく出てきますが、日本の有名な江戸時代の数学者、関孝和もこの関係式を導いています。２項係数をもちいれば、

(a + b)^{0} · · · · · · \binom{0}{k}
(a + b)^{1} · · · · · · \binom{1}{0} \binom{1}{1}
(a + b)^{2} · · · · · · \binom{2}{0} \binom{2}{1} \binom{2}{2}
(a + b)^{3} · · · · · · \binom{3}{0} \binom{3}{1} \binom{3}{2} \binom{3}{3}
(a + b)^{4} · · · · · · \binom{4}{0} \binom{4}{1} \binom{4}{2} \binom{4}{3} \binom{4}{4}
(a + b)^{5} · · · · · · \binom{5}{0} \binom{5}{1} \binom{5}{2} \binom{5}{3} \binom{5}{4} \binom{5}{5}
(a + b)^{6} · · · · · · \binom{6}{0} \binom{6}{1} \binom{6}{2} \binom{6}{3} \binom{6}{4} \binom{6}{5} \binom{6}{6}

となります。

3 ２項係数

ここで２項係数とはある自然数 n に対して k = 0, 1, 2, ⋯, n について

\binom{n}{k} = \frac{n(n − 1)(n − 2) ⋯ (n − k + 1)}{k!}

と表したものです。したがって一般式では

(a + b)^{n} = \binom{n}{0}a^{n}b^{0} + \binom{n}{1}a^{n−1}b^{1} + \binom{n}{2}a^{n−2}b^{2} + ⋯ + \binom{n}{k}a^{n−k}b^{k} + ⋯ + \binom{n}{n}a^{0}b^{n}

と表現できます。なぜ２項という理由は、 (a+b) の２つの項を展開しているからで、 (a+b+c) とか (a+b+c+d) などの３項、４項もあって当然です。もし興味があれば、調べてみることもよいでしょう。

定理つぎの関係式が成り立つ； ; 1. \binom{n}{r} = \binom{n − 1}{n − r} + \binom{n − 1}{r} · · · · · · · · · （加法性） ; 2. \binom{n}{r} = \binom{n}{n − r} · · · · · · · · · （対称性）

問 3.1 加法性\binom{n}{r} = \binom{n − 1}{n − r} + \binom{n − 1}{r} が成り立つことを確かめ、さらにこの式は、どういうことを意味しているか、パスカル三角形の表で考えなさい。問 3.2 つぎの式は定義に代入して計算すれば得られますが、パスカル三角形の表から考えてみなさい。さらに積和の計算式, ∑_{k=1}^{n} k(k + 1) などとの関係を考えてみなさい。

\binom{n}{r} = \binom{n − 1}{r − 1} + \binom{n − 2}{r − 1} + ⋯ + \binom{r − 1}{r − 1}

問 3.3 定義の式を代入して計算してみて確かめなさい。

1. \binom{m}{0}\binom{n − m}{r} + \binom{m}{1}\binom{n − m}{r − 1} + ⋯ + \binom{m}{r}\binom{n − m}{0} = \binom{n}{r}

2. 1 − \binom{n}{1} + \binom{n}{2} + ⋯ + (−1)^{n}\binom{n}{n} = 0

3. \binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + ⋯ + n\binom{n}{n} = n2^{n−1}

問 3.4 トランプ 52 枚から 5 枚を選ぶポーカーで、場合の数を考えなさい。 (1) すべての場合は何通りか？答え\binom{52}{5} 約 259 万通り

(2) ローヤルフラッシュ（同じ種類の絵札、 (10,J,Q,K,A））

(3) フォーカード（4 枚が同じ数、 x ≠ y, (x, x, x, x, y)）、答え 13 · 12 · 4

(4) ストレート（種類を無視して、続きの番号）答え 9 · 4^{5}

(5) スリーカード（3 枚が同じ数, (x, x, x, y, z)）答え 13\binom{12}{2}4 · 4^{2}

(6) ツーペア（2 組の同じ数, (x, x, y, y, z)）答え\binom{13}{2}11 · 6 · 6 · 4

(7) ワンペア（2 枚のみ同じ数で残りはバラバラ, (x, x, y, z, w)）答え 13\binom{12}{3}6 · 4^{3}

(補足) とくに見かけは大したことがないような\binom{52}{5} の値が驚くほどの約 259 万通り (正確には 2598960) にも大きな数になりますが、この概算の計算を試みてみます。スターリングの公式

n! ∼ n^{n}e^{−n}\sqrt{2πn}

では 52! = 80658175170943878571660636856403766975289505440883277824000000000000 ∼ 8.05290203838866 ∗ 10^{67}

このようなたいへんな計算もパソコンのレベルでも計算できます。

問 3.5 いままで 2 項係数の表し方は_{n}C_{k}, C_{k}^{n} とも表したかもしれませんが、同じものです。しかしこれを拡張した意味を上の式ではこめているのです。たとえば、自然数 n のかわりに実数 α としても意味をもちます。

\binom{α}{k} = \frac{α(α − 1)(α − 2) ⋯ (α − k + 1)}{k!} k = 0, 1, 2, 3, ⋯

これをもちいて、 k = 0, 1, 2, 3, ⋯ に対して\binom{−1}{k}, \binom{−2}{k} などを計算してみなさい。どんなことが気づきますか？パスカル三角形と関係があるのです。