包除原理・余事象で数える
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
数えにくいものを直接数えないという判断が、数え上げの実力を最も分ける。『少なくとも1つ』は余事象、『A または B』は包除原理。包除原理の本質は、重複して数えた分を引き、引きすぎた分を足す、という交互の補正である。集合が3つなら、単独の和 − 2つの共通部分の和 + 3つすべての共通部分、という形になる。符号を間違えないための最も確実な方法は、ベン図を描いて各領域が何回数えられているかを確認することである。
こんなときに使う
- 『少なくとも1つ』『1つ以上』→ まず余事象を検討する
- 『A または B』『どちらかを満たす』→ 包除原理
- 『どれも満たさない』→ 全体から包除原理の結果を引く
- 条件が3つ以上 → 符号に注意（ベン図で確認）
- 『誰も自分のものを受け取らない』（完全順列）→ 包除原理の典型
- 直接数えると場合分けが爆発する → 包除に切り替える合図
手順
- 1. 直接数えるのと余事象を数えるのとで、どちらが楽か比べる
- 2. 余事象を使うなら、全体の個数を確定させてから引く
- 3. 包除原理は |A∪B| = |A| + |B| − |A∩B|
- 4. 3つなら |A∪B∪C| = (単独の和) − (2つの共通の和) + |A∩B∩C|
- 5. ベン図で、各領域がちょうど1回ずつ数えられているか確認する
例題
1 から 100 までの整数のうち、2 でも 3 でも割り切れないものは何個か。
解答
- A を 2 の倍数の集合、B を 3 の倍数の集合とする。
- |A| = ⌊100/2⌋ = 50
- |B| = ⌊100/3⌋ = 33
- |A∩B| = 6 の倍数の個数 = ⌊100/6⌋ = 16
- |A∪B| = 50 + 33 − 16 = 67 （2 または 3 で割り切れるもの）
- 求めるのはその余事象なので
- 100 − 67 = 33 個
- 【なぜ 16 を引くのか】
- 6 の倍数は A でも B でも数えられており、2回数えられている。
- 1回分を引いて、ちょうど1回になるように補正している。
- 検算：100以下で 2 でも 3 でも割り切れない数は、6 で割った余りが 1 または 5 のもの。
- 1〜96 に 16 周期ぶんで各2個 = 32 個、97〜100 では 97 と 100 のうち 97 のみ（97 = 6·16+1）。
- 32 + 1 = 33 ○
別解・ほかの見方
- 余事象を取る（『少なくとも1つ』は 1 − 『1つもない』）
- 3つ以上の集合への一般化（符号が交互に入れ替わる）
- 完全順列（撹乱順列）の個数を包除原理で求める
- 確率でも同じ形が成り立つ：P(A∪B) = P(A) + P(B) − P(A∩B)
落とし穴
- 3つ以上のとき符号を間違える（引きすぎ・足しすぎ）
- 余事象を取ったのに、元の条件のまま計算を続ける
- 『または』を排反だと思い込んで単純に足す
- 全体の個数を確定させないまま引き算を始める
- 3つ以上の集合で符号を間違える
なぜ大事か
「直接数えない」判断。完全順列や東大の色分け問題の主武器
東大での出方
東大では、色の塗り分けや条件つきの数え上げで使う。直接数えると場合分けが爆発する設定をわざと作ってあり、包除原理や余事象に切り替えられるかどうかで所要時間が数倍変わる。
確認問題
- 1 から 100 までで、2, 3, 5 のいずれでも割り切れない整数は何個か
- 4人が自分の帽子を1つずつ持ち寄り、ランダムに1つずつ取るとき、全員が自分以外の帽子を取る場合は何通りか
- 3種類の文字 a, b, c を使って長さ4の文字列を作るとき、3種類すべてが現れるものは何通りか
発展
包除原理を確率で使う形（P(A∪B∪C) の展開）。さらに、条件が n 個ある場合の一般形と、そこから完全順列の個数が n!·Σ(−1)^k/k! と表せることを追ってみると、極限 1/e との関係まで見えてくる。
前提になるノード
「場合の数」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。