第1章 場合の数
入門
1.1 「数える」とは
組合せ論は「数える」数学である。しかし、単に1, 2, 3, ...と数えるのではなく、効率的に、もれなく、重複なく数える方法を考える。
例えば、次のような問題を考えてみよう。
例：サイコロを2回振るとき、目の出方は全部で何通りあるか。
すべての場合を書き出すこともできるが、それでは効率が悪い。そこで、法則を使って計算する方法を学ぶ。
1.2 和の法則
まず、最も基本的な「和の法則」を学ぶ。
和の法則（加法原理）
事象 $A$ の起こり方が $m$ 通り、事象 $B$ の起こり方が $n$ 通りあり、$A$ と $B$ が同時に起こらない（排反である）とき、$A$ または $B$ が起こる場合の数は
$$m + n \text{ 通り}$$これは直感的に理解できる。$A$ と $B$ に重なりがなければ、単純に足し合わせればよい。
例1：1から10までの整数から1つ選ぶとき、3の倍数または5の倍数である場合の数を求めよ。
解答：
まず、それぞれの場合を数える。
- 3の倍数：3, 6, 9 → 3通り
- 5の倍数：5, 10 → 2通り
ここで、3の倍数と5の倍数に共通する数があるか確認する。1から10の範囲で15の倍数はないため、これらは排反である。
したがって、和の法則より：
$$3 + 2 = 5 \text{ 通り}$$注意：和の法則を使う前に、必ず「排反かどうか」を確認すること。排反でない場合は、後で学ぶ「包除原理」を使う必要がある。
1.3 積の法則
次に、「積の法則」を学ぶ。これは連続した選択を扱う場合に使う。
積の法則（乗法原理）
操作 $A$ の方法が $m$ 通り、その各々に対して操作 $B$ の方法が $n$ 通りあるとき、$A$ と $B$ を続けて行う方法は
$$m \times n \text{ 通り}$$なぜ掛け算になるのか、図で考えてみよう。
例2：サイコロを2回振るとき、目の出方は何通りあるか。
解答：
これを段階的に考える。
ステップ1：1回目のサイコロの目の出方
1から6までの6通りである。
ステップ2：2回目のサイコロの目の出方
1回目の結果に関係なく、やはり1から6までの6通りである。
ステップ3：積の法則を適用
1回目の各目に対して、2回目は6通りずつあるので：
$$6 \times 6 = 36 \text{ 通り}$$例3：A, B, C, D, Eの5人から委員長と副委員長を選ぶ方法は何通りあるか（兼任不可）。
解答：
段階的に考える。
ステップ1：委員長の選び方
5人の中から1人を選ぶので、5通りである。
ステップ2：副委員長の選び方
委員長に選ばれた人は除くので、残り4人から選ぶ。4通りである。
ステップ3：積の法則を適用
$$5 \times 4 = 20 \text{ 通り}$$この例では、「委員長が誰であっても、副委員長の選択肢は常に4通り」という点が重要である。積の法則は、各段階の選択肢の数が前の段階の結果によらず一定である場合に使える。
1.4 樹形図
場合の数を視覚的に整理する方法として、樹形図（じゅけいず）がある。
樹形図とは、選択の各段階を木の枝のように描いた図である。すべての場合をもれなく・重複なく書き出すことができる。
例4：コインを3回投げるとき、表（H）と裏（T）の出方をすべて求めよ。
樹形図から、場合の数は 8通り であることがわかる。これは積の法則でも確認できる：
$$2 \times 2 \times 2 = 2^3 = 8 \text{ 通り}$$樹形図の利点
- すべての場合を視覚的に確認できる
- もれや重複がないことを確認しやすい
- 条件付きの問題にも対応できる
樹形図の欠点
- 場合の数が多いと描ききれない
- 時間がかかる
1.5 和と積の組み合わせ
実際の問題では、和の法則と積の法則を組み合わせて使うことが多い。
例5：1から100までの整数のうち、2で割り切れるか、または5で割り切れる数は何個あるか。
解答：
これは単純に和の法則を使うと間違える。2の倍数と5の倍数には重なり（10の倍数）があるからである。
ステップ1：各集合の要素数を数える
- 2の倍数：$\lfloor 100/2 \rfloor = 50$ 個
- 5の倍数：$\lfloor 100/5 \rfloor = 20$ 個
- 10の倍数（重複部分）：$\lfloor 100/10 \rfloor = 10$ 個
ステップ2：包除原理を適用
重複を引いて：
$$50 + 20 - 10 = 60 \text{ 個}$$包除原理（2集合の場合）
$$|A \cup B| = |A| + |B| - |A \cap B|$$ここで $|X|$ は集合 $X$ の要素数を表す。
1.6 補集合を使った数え上げ
「〜でない」という条件がある場合、補集合を使うと簡単に計算できることがある。
補集合を使った数え上げ
「条件Aを満たさない」場合の数 = 全体の場合の数 − 「条件Aを満たす」場合の数
$$|\overline{A}| = |U| - |A|$$例6：サイコロを2回振るとき、少なくとも1回は1が出る場合の数を求めよ。
解答：
「少なくとも1回は1が出る」を直接数えるのは面倒である。補集合を使おう。
ステップ1：全体の場合の数
$$6 \times 6 = 36 \text{ 通り}$$ステップ2：「1が1回も出ない」場合の数
各回で1以外の目（2, 3, 4, 5, 6）が出ればよいので：
$$5 \times 5 = 25 \text{ 通り}$$ステップ3：補集合を使って計算
$$36 - 25 = 11 \text{ 通り}$$1.7 この章のまとめ
| 法則 | 使う場面 | 公式 |
|---|---|---|
| 和の法則 | 「AまたはB」（排反な場合） | $m + n$ |
| 積の法則 | 「AしてからB」 | $m \times n$ |
| 包除原理 | 「AまたはB」（排反でない場合） | $|A| + |B| - |A \cap B|$ |
| 補集合 | 「〜でない」 | $|U| - |A|$ |
練習問題
問題1
A市からB市へ行く道が3本、B市からC市へ行く道が4本ある。A市からB市を経由してC市へ行く方法は何通りあるか。
問題2
1から20までの整数のうち、3の倍数または4の倍数である数は何個ありますか。
問題3
0, 1, 2, 3, 4の5つの数字を使って3桁の整数を作る。同じ数字を繰り返し使ってもよいとき、何通りの整数が作れるか。（ただし、百の位が0であるものは3桁の整数とは見なさない。）
問題4
コインを4回投げるとき、少なくとも1回は表が出る場合は何通りあるか。
解答
問題1の解答
積の法則より：$3 \times 4 = 12$ 通り
問題2の解答
3の倍数：3, 6, 9, 12, 15, 18 → 6個
4の倍数：4, 8, 12, 16, 20 → 5個
12の倍数（重複）：12 → 1個
包除原理より：$6 + 5 - 1 = 10$ 個
問題3の解答
百の位：0以外の4通り（1, 2, 3, 4）
十の位：5通り（0, 1, 2, 3, 4）
一の位：5通り
積の法則より：$4 \times 5 \times 5 = 100$ 通り
問題4の解答
全体：$2^4 = 16$ 通り
表が1回も出ない（全部裏）：1通り
補集合を使って：$16 - 1 = 15$ 通り
よくある質問
和の法則と積の法則はどう使い分けますか？
和の法則は「AまたはB」のように互いに排反な事象を合わせる場合に使い、場合の数を足し合わせます。積の法則は「AしてからB」のように連続した独立な操作を行う場合に使い、場合の数を掛け合わせます。例えばサイコロ1個で偶数か奇数が出る場合は和の法則、サイコロ2個を振って両方の目を考える場合は積の法則を使います。
包除原理とは何ですか？
2つの集合 $A$ と $B$ の和集合の要素数を求める公式 $|A \cup B| = |A| + |B| - |A \cap B|$ のことです。和の法則は $A$ と $B$ が排反な場合の特別な形で、排反でない（重なりがある）場合は重複部分 $|A \cap B|$ を引く必要があります。3集合以上にも一般化できます。
補集合を使った数え上げが有効なのはどんな場合ですか？
「少なくとも1回〜」「〜でない」のような条件で、直接数えると場合分けが多くなる問題に有効です。全体の場合の数から「条件を満たさない」場合の数を引く方が簡単になります。例: サイコロを2回振るとき少なくとも1回は1が出る場合の数 = $36 - 25 = 11$ 通り。