場合の数

トランプ52枚から5枚を選ぶ選び方が何通りあるか知りたいとします。このような問題をあつかうのが、場合の数（組合せ論）です。場合の数には、和の法則と積の法則という2つの基本的な法則があります。ほかのすべての方法は、これらの基本的な考え方を広げたものにすぎません。

和の法則

和の法則はとても簡単です。共通の要素をもたない集合 A, B があるとき、和集合 A ∪ B から要素を1つ選ぶ選び方の総数は |A| + |B|、つまり要素の個数の和に等しくなります。

簡単な例から始めましょう。赤い玉が6個、青い玉が8個あります。これらの玉を1つの箱に入れます。玉を1個引くとき、全部で何通りの引き方があるでしょうか。赤い玉の集合を A、青い玉の集合を B とします。これらの集合は共通部分をもたない、つまり同じ玉を含んでいません。玉を1個引くので、全部で |A| + |B| = 6 + 8 = 14 通りあります。

積の法則

今度も2つの集合 Z と M があります。集合 Z には女性が3人、集合 M には男性が4人含まれています。これらの集合から、男性–女性 の組は何通りつくれるでしょうか。考え方としては、女性を1人選び、その人に男性を1人組み合わせます。組の総数は次のように数えます。まず女性の1人、さくらさんを選び、その人に男性を順に全員組み合わせます。さくらさんには全部で4人の男性を組み合わせられるので、4通りの組ができます。残りの2人の女性についても同じことをすると、それぞれ4通りずつの組ができます。したがって、組は全部で 4 + 4 + 4 = 12 通りです。

実際には何をしたのでしょうか。2つの集合の要素の個数をかけたのです。女性が3人、男性が4人なので、組の総数は 3 · 4 = 12 です。これが積の法則です。つまり、2つの集合から組をつくるときは、一方の集合の要素の個数に、もう一方の集合の要素の個数をかければよいのです。

本当にそうなっているか、確かめてみましょう。3人の女性と4人の男性からつくれるすべての組を、次に示します。各行が1人の女性についての組、各列が1人の男性についての組です。3行4列なので、全部で 行の数 · 列の数 通りです。

$$\begin{array}{rcl}& & (Z_1,M_1),(Z_1,M_2),(Z_1,M_3),(Z_1,M_4),\\ & & (Z_2,M_1),(Z_2,M_2),(Z_2,M_3),(Z_2,M_4),\\ & & (Z_3,M_1),(Z_3,M_2),(Z_3,M_3),(Z_3,M_4)\end{array}$$

例題

1. 2けたの数は何個あるでしょうか。2けたの数はどんな形をしているでしょうか。十の位には 1, …, 9 のどれか、一の位には0も加えた 0, …, 9 のどれかがきます。つまり、1つ目の集合には数字が9個、2つ目の集合には10個あります。積の法則を使うと、答えは 9 · 10 = 90 です。

• 同じ数字を2回使わない3けたの数は何個あるでしょうか。百の位には、やはり9個の数字がきます。数は0から始められないからです。十の位には0も含めたすべての数字がきますが、百の位の数字は使えないので、候補は10個から1個減って9個です（たとえば3けたの数が4から始まるなら、十の位には4はこられません。数全体に4が2回出てきてしまうからです）。一の位にも、やはりすべての数字がきますが、百の位や十の位の数字は使えません。理由は同じです。百の位が4、十の位が7なら、一の位には {0, …, 9} ∖ {4, 7} のどれか1つの数字を入れられます。候補は10個から2個減って8個です。あとは 9 · 9 · 8 = 648 を計算するだけです。したがって、このような数は全部で648個あります。
• ふつうのさいころを2回続けてふります。目の出方は何通りあるでしょうか。1回目には、さいころの目は6通り出ます。2回目も同じなので、全部で 6 · 6 = 36 通りです。
• さいころを2回続けてふります。1回目に偶数の目が出たとき、目の出方は何通りあるでしょうか。1回目は偶数、つまり 2, 4, 6 のどれかなので、3通りです。2回目はどの目が出てもよいので、全部で 3 · 6 = 18 通りです。