回 8-4 分野 8 考え方
包除原理は、和集合の個数を、1 つずつの個数を足し、2 つの重なりを引き、3 つの重なりを足し、というように符号を交互に変えて数える方法です。2 つなら |A ∪ B| = |A| + |B| − |A ∩ B|、3 つなら |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C| です。1 から 1000 で 2 か 3 か 5 で割り切れる数は、500 + 333 + 200 − 166 − 100 − 66 + 33 = 734 個です。重なりの個数は、最小公倍数の倍数として数えます。
重なりを足して引く式を、全部を 1 つずつ数えた答えと照らしながら、2 集合から n 集合まで広げます。
文 ゆめさくコード編集部公開 2026年10月30日更新 2026年10月30日出典を確かめた日 2026年10月30日
1 から 1000 で、2 か 3 か 5 で割り切れる数はいくつか
答えは 734 個です。2 の倍数 500 個、3 の倍数 333 個、5 の倍数 200 個を足すと 1033 個になり、1000 を超えてしまいます。
足しすぎたのは、6 のように 2 でも 3 でも割り切れる数を 2 回数えたからです。重なりの分を引き、引きすぎた分をまた足すと、ちょうど 1 回ずつ数えられます。この足して引く数え方を、包除原理と呼びます。
この回では、包除原理の式を、全部の数を 1 つずつ調べた答えと照らしながら確かめます。
包除原理の式
2 つの集合
集合 A の要素の個数を |A| と書きます。A と B の少なくとも一方に入る要素の集合 (和集合) を A ∪ B、両方に入る要素の集合 (共通部分) を A ∩ B と書きます。
| A | + | B | では、両方に入る要素を 2 回数えています。だから | A ∩ B | を 1 回引きます。ベン図 (2 つの円が重なる図) で、重なった部分を 2 回塗った形を思い浮かべると分かりやすいです。 |
|---|
1 から 100 で 2 か 3 で割り切れる数は、2 の倍数 50 個 + 3 の倍数 33 個 − 6 の倍数 16 個 = 67 個です。
3 つの集合
| A ∪ B ∪ C | = | A | + | B | + | C | − | A ∩ B | − | B ∩ C | − | C ∩ A | + | A ∩ B ∩ C |
|---|
1 から 1000 で、A を 2 の倍数、B を 3 の倍数、C を 5 の倍数とすると、次の表の通りです。
| 項 | 何の倍数 | 個数 | 符号 |
|---|
| 1 つずつ | 2、3、5 | 500、333、200 | 足す |
|---|
| 2 つの重なり | 6、15、10 | 166、66、100 | 引く |
|---|
| 3 つの重なり | 30 | 33 | 足す |
|---|
500 + 333 + 200 − 166 − 66 − 100 + 33 = 734 です。1 から N の中の k の倍数は、N ÷ k の切り捨て (Python では N // k) で数えます。
符号が交互になる理由
和集合の要素 x が、ちょうど m 個の集合に入っているとします。x は「1 つずつ」で m 回、「2 つの重なり」で m 個から 2 個を選ぶ数だけ、「3 つの重なり」で m 個から 3 個を選ぶ数だけ数えられます。符号を交互に付けて足すと、m がいくつでもちょうど 1 になります。二項定理で (1 − 1)^m を展開すると、C(m, 0) − C(m, 1) + C(m, 2) − … = 0 です。C(m, 0) = 1 を移すと、C(m, 1) − C(m, 2) + C(m, 3) − … = 1 で、これが x の数えられる回数です。
たとえば 30 は 3 つ全部に入る (m = 3) ので、3 − 3 + 1 = 1 回です。6 は 2 と 3 に入る (m = 2) ので、2 − 1 = 1 回です。どの要素も 1 回ずつ数えられるのが、式が正しい理由です。
n 個の集合
n 個の集合では、k 個の集合の共通部分を、選び方の全部について足し、k が奇数なら足し、偶数なら引きます。項の数は、n 個の集合から 1 個以上を選ぶ選び方の数で、2^n − 1 個です。集合が 20 個なら約 100 万項になります。
余事象と組み合わせる
「どれにも入らない」個数は、全体から和集合を引いて出します (8-3 の余事象の考え方)。1 から 1000 で、2 でも 3 でも 5 でも割り切れない数は、1000 − 734 = 266 個です。これは 30 と互いに素な (1 以外の公約数を持たない) 数の個数です。1 から n までで n と互いに素な数の個数をオイラーのファイ関数と呼び、n の素因数で包除原理を使うと出せます。
「どれにも入らない」は「A でない、かつ B でない、かつ C でない」で、ド・モルガンの法則で「A または B または C」の余事象と同じです。
動かして確かめる
1 本目は、1 から 1000 を全部調べて数えた答えと、包除原理の式を比べます。ちょうど k 個の数で割り切れる数の内訳も数えます。
動かす 全部数えた答えと式を比べる
実行すると、次の通りに出ます
全部数えた 734
包除原理 734
ちょうど 0 266
ちょうど 1 468
ちょうど 2 233
ちょうど 3 33
全部数えた 734 個と、式の 734 個が一致しました。ちょうど 1 個、2 個、3 個で割り切れる数を足すと、468 + 233 + 33 = 734 です。「少なくとも 2 個」は 233 + 33 = 266 個、「ちょうど 2 個」は 233 個で、別の数です。
「ちょうど 2 個」も式で出せます。2 つの重なりの合計から、3 つ全部に入る数を 3 回引きます (3 つ全部に入る数は、2 つの重なりの 3 つの組の全部で数えられているからです)。166 + 66 + 100 − 3 × 33 = 233 で、全部数えた 233 と合います。
2 本目は、n 個の数でも使える関数です。選んだ数の共通部分の個数は、選んだ数の最小公倍数の倍数の個数です。最小公倍数ではなく積で割ると外れるので、4 と 6 で比べます。
動かす n 個の数で使える包除原理
実行すると、次の通りに出ます
[2, 3, 5] 全部 74
lcm 74 積 74
[4, 6] 全部 33
lcm 33 積 37
[6, 10, 15] 全部 26
lcm 26 積 30
素数どうしなら最小公倍数と積は同じですが、4 と 6 では違います。4 でも 6 でも割り切れる数は 12 の倍数で、24 の倍数ではありません。積で割ると重なりを少なく数え、和集合を多く数えます。
3 本目は、完全順列です。n 人がプレゼントを 1 つずつ持ち寄り、全員が自分以外のプレゼントを受け取る並び方を数えます。「誰かが自分のを受け取る」並びを包除原理で数え、全体から引きます。
動かす 完全順列を数える
実行すると、次の通りに出ます
1 0 0 0.0
2 1 1 0.5
3 2 2 0.3333
4 9 9 0.375
5 44 44 0.3667
6 265 265 0.3681
7 1854 1854 0.3679
決まった k 人が自分のを受け取る並びは、残りの人の並べ方で (n − k)! 通りです。その k 人の選び方は C(n, k) 通りあるので、包除原理の k 個の重なりの項は C(n, k) × (n − k)! です。この項は、何人もが自分のを受け取る並びを重ねて数えているので、それだけでは「誰かが自分のを受け取る並び」の数になりません。符号を交互に付けて全部の項を足して初めて、重なりが打ち消されます。k = 0 から足すと、全部数えた答えと一致しました。4 人なら 9 通りです。右の列は全部の並びのうちの割合で、n が大きくなると約 0.3679 (1/e) に近づきます。
4 本目は、オイラーのファイ関数です。1 から 1000 で 1000 と互いに素な数を、1000 の素因数 2 と 5 で包除原理を使って数え、math.gcd で全部調べた数と比べます。部分集合は、ビット (0 と 1 の並び) で全部回しています。
動かす 1000 と互いに素な数
実行すると、次の通りに出ます
包除原理 400
全部数えた 400
φ(1000) 400
2 の倍数 500 個と 5 の倍数 200 個から 10 の倍数 100 個を引いた 600 個が、1000 と公約数を持つ数です。残りの 400 個が互いに素で、φ(1000) = 1000 × (1 − 1/2) × (1 − 1/5) = 400 とも一致しました。mask の i 番目のビットが 1 なら i 番目の素数を選ぶ、という書き方で、2^k − 1 通りの組を全部回せます。
包除原理で外れる所
重なりを積で数える
2 本目で見た通り、「a でも b でも割り切れる数」は、a と b の最小公倍数の倍数です。a と b が互いに素なら積と同じですが、そうでなければ違います。Python 3.9 から math.lcm が使えます。
「ちょうど」と「少なくとも」を取り違える
包除原理の式で出るのは「少なくとも 1 つに入る」個数です。「ちょうど 2 つに入る」個数は、1 本目の内訳のように別に数えます。問題文の「2 つとも」「ちょうど 2 つ」「少なくとも 2 つ」を、ベン図のどの部分に当たるかで読み分けます。
集合が多いと項が爆発する
項の数は 2^n − 1 です。集合が 30 個なら約 10 億項で、全部を回すのは重くなります。重なりが 0 になる組を途中で打ち切るなどの工夫が要ります。
仕事とコンテストでどう使うか
包除原理で考える場面は、次の通りです。
- 集計。メールを開いた人 1200 人、リンクを押した人 800 人、両方 500 人なら、どちらかをした人は 1200 + 800 − 500 = 1500 人。人数を足すだけで出すと、重なる人を 2 回数える。SQL では、UNION (重なりを除く) と UNION ALL (除かない) の違いに当たる
- テストの網羅。「条件 A か B を満たす入力の数」を、それぞれの数と両方の数から出す
- 数え上げ。競技プログラミングで「どれかの条件を満たす数」「どれも満たさない数」を数えるとき、条件の組をビットで全部回して足し引きする
- 確率。P(A ∪ B) = P(A) + P(B) − P(A ∩ B) は、個数の式を確率に置き換えた形。1 から 100 の札を 1 枚引いて 2 か 3 の倍数が出る確率は、50/100 + 33/100 − 16/100 = 67/100
よくある問い
包除原理とは何ですか
いくつかの集合の少なくとも 1 つに入る要素の個数を、1 つずつの個数を足し、2 つの重なりを引き、3 つの重なりを足し、というように符号を交互に付けて数える方法です。重なりを足しすぎた分と引きすぎた分を直して、どの要素もちょうど 1 回数えます。
3 つの集合の式は、なぜ最後に足すのですか
3 つ全部に入る要素は、1 つずつの所で 3 回足され、2 つの重なりの所で 3 回引かれ、0 回になってしまいます。だから 3 つの重なりを 1 回足して、1 回に戻します。
「a でも b でも割り切れる数」は、どう数えますか
a と b の最小公倍数の倍数を数えます。4 と 6 なら最小公倍数は 12 で、1 から 100 には 8 個です。積の 24 で割ると 4 個になり、外れます。
包除原理と余事象はどう違いますか
余事象は「全体から、反対を引く」考え方で、包除原理は「和集合を、重なりを足し引きして数える」考え方です。「どれにも入らない個数」を出すときは、包除原理で和集合を出してから、余事象として全体から引きます。
確認クイズ
答えだと思う選択肢を押すと、その場で正誤と理由が開きます。3 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。
1 問目
1 から 100 で、3 か 5 で割り切れる数はいくつですか。
2 問目
1 から 120 で、「4 でも 6 でも割り切れる数」はいくつですか。
3 問目
集合 A、B、C について、包除原理で |A ∪ B ∪ C| を出すとき、|A ∩ B ∩ C| の符号はどれですか。
説明課題
「1 から 1000 で 2 か 3 か 5 で割り切れる数が、500 + 333 + 200 = 1033 個にならない理由と、正しい数え方」を、3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
模範解答
自分の説明を書いてから開いて、比べてください。
500 + 333 + 200 では、6 や 10 のように 2 つの数で割り切れる数を 2 回、30 の倍数を 3 回数えている。そこで 6、15、10 の倍数の 166 + 66 + 100 を引くと、30 の倍数は 3 回足して 3 回引かれ 0 回になるので、30 の倍数の 33 を足し戻す。こうして 1033 − 332 + 33 = 734 個と、どの数もちょうど 1 回ずつ数えられる。
「どれかに当てはまる数」を重なりなく数えられると、集計の SQL や、条件の多いテストの組み合わせを数え間違えなくなります。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。
もっと深く
この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。
一次資料
どれも 2026年10月30日に開いて、題と中身を確かめました。
