包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

包除原理のオーバーカウント修正の本質を指標関数を使って証明します．完全順列の数え上げや競プロ典型問題への応用，メビウス反転公式への発展も解説します．

2026年2月27日

包除原理は「足して引いてまた足して…」という一見不思議な操作で正しい数え上げを行います．2集合のベン図なら直感的に理解できますが，集合が3つ，4つ，…と増えるとなぜ交互の符号が正しい結果を与えるのか，その本質はどこにあるのでしょうか？

1 2集合の場合 ― ベン図の直感

定理 1 (包除原理（2集合）).

有限集合

A, B

に対して，

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

これはベン図を描けば一目瞭然です． $∣ A ∣ + ∣ B ∣$ では $A \cap B$ の部分が2回数えられるので，1回分を引いて修正します．

2 一般の定式化

定理 2 (包除原理（一般）).

有限集合

A_{1}, A_{2}, \dots, A_{n}

に対して，

i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k + 1} ∣ S ∣ = k \sum i \in S ⋂ A_{i}

ここで

S

は

{1, 2, \dots, n}

の空でない部分集合を動きます．

展開すると，

i = 1 ⋃ n A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < k \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots + (- 1)^{n + 1} ∣ A_{1} \cap \dots \cap A_{n} ∣

です．

3 指標関数による証明

証明.

要素

x \in ⋃_{i = 1}^{n} A_{i}

を任意に固定します．

x

がちょうど

m

個の集合

A_{i_{1}}, \dots, A_{i_{m}}

に属しているとしましょう（

m \geq 1

）．

右辺で

x

が何回カウントされるか計算します．

k

個の集合の交差

⋂_{i \in S} A_{i}

に

x

が属するためには，

S \subseteq {i_{1}, \dots, i_{m}}

でなければなりません．そのような

∣ S ∣ = k

の

S

は

(k m)

個あります．

したがって，右辺で

x

がカウントされる回数は

k = 1 \sum m (- 1)^{k + 1} (k m) = 1 - k = 0 \sum m (- 1)^{k} (k m) = 1 - (1 - 1)^{m} = 1

です（二項定理を使いました）．どの要素もちょうど1回カウントされるので，等式が成り立ちます． □

注意 3.

証明の核心は

(1 - 1)^{m} = 0

（

m \geq 1

）です．二項定理の特殊値がオーバーカウントの完全な相殺を保証しています．これが包除原理の本質です．

4 完全順列（攪乱順列）

定義 4 (完全順列).

{1, 2, \dots, n}

の順列

σ

で，すべての

i

に対して

σ (i) \neq = i

を満たすものを完全順列（derangement）と呼び，その個数を

D_{n}

と書きます．

定理 5.

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}

証明.

A_{i} = {σ \in S_{n} ∣ σ (i) = i}

（

i

が動かない順列の集合）とおくと，

D_{n} = n! - ∣ A_{1} \cup A_{2} \cup \dots \cup A_{n} ∣

です．

∣ S ∣ = k

のとき

∣ ⋂_{i \in S} A_{i} ∣ = (n - k)!

（

S

に属する要素を固定し，残りを自由に並べる）です．

包除原理より，

∣ A_{1} \cup \dots \cup A_{n} ∣ = k = 1 \sum n (- 1)^{k + 1} (k n) (n - k)!

したがって，

D_{n} = n! - k = 1 \sum n (- 1)^{k + 1} (k n) (n - k)! = k = 0 \sum n (- 1)^{k} (k n) (n - k)! = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}

□

注意 6.

n

が大きいとき

D_{n} / n! \to 1/ e \approx 0.3679

に収束します．つまり，ランダムな順列が完全順列である確率は約

36.8%

で，

n

によらずほぼ一定です．

5 競プロ典型問題 ― $n$ 以下で互いに素な数

例 7 (

n

以下で

p_{1}, \dots, p_{k}

のいずれでも割り切れない数の個数).

A_{i} = {m ∣ 1 \leq m \leq n, p_{i} ∣ m}

とおくと

∣ A_{i} ∣ = ⌊ n / p_{i} ⌋

です．

p_{i}

が互いに異なる素数なら

∣ ⋂_{i \in S} A_{i} ∣ = ⌊ n / \prod_{i \in S} p_{i} ⌋

です．

包除原理より，

p_{1}, \dots, p_{k}

のいずれでも割り切れない

1 \leq m \leq n

の個数は

n - i = 1 ⋃ k A_{i} = n - k = 1 \sum n (- 1)^{k + 1} ∣ S ∣ = k \sum ⌊ \frac{n}{\prod _{i \in S} p _{i}} ⌋

です．これはオイラーのトーシェント関数

φ (n)

の計算にも使われます．

注意 8.

k

個の素因数に対して

2^{k}

通りの部分集合を列挙する必要があります．

k \leq 20

程度なら

2^{20} \approx 1 0^{6}

で十分高速ですが，素因数の数が多い場合は別のアプローチが必要です．

6 メビウス反転公式への伏線

注意 9.

包除原理は実はメビウス反転公式の特殊な場合です．半順序集合

(P, \leq)

上の関数

f, g

が

g (x) = \sum_{y \leq x} f (y)

を満たすとき，メビウス関数

μ

を用いて

f (x) = \sum_{y \leq x} μ (x, y) g (y)

と反転できます．ブール束（べき集合の包含関係）上のメビウス関数は

μ (S, T) = (- 1)^{∣ S ∖ T ∣}

であり，これがまさに包除原理の交互符号を生み出しています．

7 まとめ

包除原理は「各要素がちょうど1回数えられる」ことを二項定理 $(1 - 1)^{m} = 0$ で保証します
完全順列 $D_{n}$ は包除原理の美しい応用で， $D_{n} / n! \to 1/ e$ です
競プロでは $n$ 以下で条件を満たす数の個数を求める典型パターンがあります
包除原理はメビウス反転の特殊ケースであり，より一般的な反転公式に拡張されます

次の記事では，数列を「関数」に変換して見通しをよくする母関数のアイデアを紹介します．

組合せ論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

1 2集合の場合 ― ベン図の直感

2 一般の定式化

3 指標関数による証明

4 完全順列（攪乱順列）

5 競プロ典型問題 ― $n$ 以下で互いに素な数

6 メビウス反転公式への伏線

7 まとめ

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

素数の分布 ― 素数定理への道

1 2集合の場合 ― ベン図の直感

2 一般の定式化

3 指標関数による証明

4 完全順列（攪乱順列）

5 競プロ典型問題 ―n以下で互いに素な数

6 メビウス反転公式への伏線

7 まとめ

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

素数の分布 ― 素数定理への道

5 競プロ典型問題 ― $n$ 以下で互いに素な数