組合せ論
組合せ論（combinatorics）は、有限または可算な対象の数え上げ、配置、選択、構造を研究する数学の分野である。
数え上げ
順列、組合せ、二項係数などを用いて、条件を満たす配置や選択の総数を求める。
鳩の巣原理
n個より多い対象をn個の箱へ入れれば、少なくとも1つの箱には2個以上入る。この単純な原理から強い結論が得られる場合がある。
確率との関係
有限標本空間の確率計算では、場合の数を正しく数えることが重要である。そのため確率論と密接に結び付く。
順列と組合せを使い分ける
n個から異なるr個を順に選ぶなら、最初はn通り、次はn−1通りとなり、順列の数はn!/(n−r)!である。順序を区別しないとき、同じr個がr!回ずつ数えられているので、その分だけ割る。重複を許すか、順序を区別するかを最初に決めると、公式の取り違えを防げる。
C(n,r) = n! / {r!(n−r)!}
例：重なりを引いて数える
1から30までの整数のうち2または3で割り切れるものを数える。2の倍数は15個、3の倍数は10個だが、6の倍数5個が二重に含まれている。よって15+10−5=20個になる。これは包除原理の最も基本的な形である。
|A∪B| = |A| + |B| − |A∩B|
数え方を変えて証明する
二項係数の関係C(n,r)=C(n−1,r)+C(n−1,r−1)は、特定の一人を選ばない場合と選ぶ場合に分ければ分かる。同じ対象を二通りに数える方法を二重計数という。公式を代数的に変形するだけでなく、「何を一度ずつ数えたか」を説明することが証明になる。無作為抽出の確率を計算するときも、各結果の等確率性は別に確認する。
確認問題
5人から委員2人を選ぶ場合と、委員長・副委員長を選ぶ場合はそれぞれ何通りか。
解答と考え方を見る
委員2人はC(5,2)=10通り。役職を区別すると5×4=20通り。同じ二人でも役職の割当てが2通りある。
参考資料・次に読む資料
- MIT OpenCourseWare: Mathematics for Computer Science定義・証明・集合・数え上げ・離散確率を学ぶ講義資料。
資料確認日：2026-10-12。