包除原理 ― 交互和による数え上げ

包除原理の証明から完全順列$D_n$，オイラーの$\varphi$関数の導出，全射と第二種スターリング数，メビウスの反転公式までを解説する．

2026年2月27日

1 包除原理

定理 1 (包除原理).

有限集合

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

に対して

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

が成り立つ．

証明.

任意の元

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

が右辺に寄与する回数を計算する．

x

がちょうど

m

個の集合

A_{i_{1}}, \dots, A_{i_{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

である（

m \geq 1

なので

(1 - 1)^{m} = 0

）．よって各元はちょうど

1

回数えられる． □

2 完全順列

定義 2 (完全順列（攪乱順列）).

{1, 2, \dots, n}

の順列

σ

で

σ (i) \neq = i

（

1 \leq i \leq n

）を満たすものを完全順列（derangement）という．その個数を

D_{n}

と書く．

定理 3.

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

証明.

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

とおくと，

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

．

∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣ = (n - k)!

であるから，包除原理より

∣ 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 !}

□

系 4.

D_{n}

は

n! / e

に最も近い整数である．すなわち

D_{n} = ⌊ n! / e + 1/2 ⌋

．

3 オイラーの $φ$ 関数

定理 5.

正整数

n

の素因数分解を

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}

とすると，

φ (n) = n i = 1 \prod k (1 - \frac{1}{p _{i}})

証明.

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

とおく．

φ (n) = n - ∣ A_{1} \cup \dots \cup A_{k} ∣

．

∣ A_{i_{1}} \cap \dots \cap A_{i_{j}} ∣ = n / (p_{i_{1}} \dots p_{i_{j}})

であるから，包除原理より

φ (n) = n - i \sum \frac{n}{p _{i}} + i < j \sum \frac{n}{p _{i} p _{j}} - \dots = n i = 1 \prod k (1 - \frac{1}{p _{i}})

□

4 全射と第二種スターリング数

定義 6 (第二種スターリング数).

n

元集合を

k

個の空でない部分集合に分割する方法の数を第二種スターリング数（Stirling number of the second kind）といい，

S (n, k)

または

{\frac{n}{k}}

と書く．

定理 7.

S (n, k) = \frac{1}{k !} j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n}

証明.

n

元集合

A

から

k

元集合

B

への全射の数は

\sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}

である（前回の結果）．全射

f : A \to B

は

A

の

k

分割に

B

のラベルを付けたものに対応し，ラベルの付け方は

k!

通り．よって

S (n, k) = (全射の数) / k!

． □

5 メビウスの反転公式

定義 8 (メビウス関数).

μ : Z_{> 0} \to {- 1, 0, 1}

を

μ (n) = ⎩ ⎨ ⎧ 1 (- 1)^{k} 0 n = 1 n = p_{1} p_{2} \dots p_{k} （相異なる素数の積） それ以外（平方因子を持つ）

で定める．

定理 9 (メビウスの反転公式).

数論的関数

f, g

に対して，

g (n) = d ∣ n \sum f (d) ⟺ f (n) = d ∣ n \sum μ (n / d) g (d)

証明.

右辺に

g (d) = \sum_{e ∣ d} f (e)

を代入すると，

d ∣ n \sum μ (n / d) e ∣ d \sum f (e) = e ∣ n \sum f (e) d ∣ n e ∣ d \sum μ (n / d)

d = e k

とおくと内側の和は

\sum_{k ∣ (n / e)} μ (n / (e k))

である．

m = n / e

とすれば

\sum_{k ∣ m} μ (m / k) = \sum_{l ∣ m} μ (l)

であり，これは

m = 1

のとき

1

，

m > 1

のとき

0

であることが知られている（メビウス関数の基本性質）．よって右辺は

f (n)

に等しい． □

例 10.

g (n) = n

（恒等関数）とすると

n = \sum_{d ∣ n} φ (d)

であるから，反転公式より

φ (n) = \sum_{d ∣ n} μ (n / d) \cdot d

が得られる．

包除原理 ― 交互和による数え上げ

1 包除原理

2 完全順列

3 オイラーの $φ$ 関数

4 全射と第二種スターリング数

5 メビウスの反転公式

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

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

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

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

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

1 包除原理

2 完全順列

3 オイラーのφ関数

4 全射と第二種スターリング数

5 メビウスの反転公式

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

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

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

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

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

3 オイラーの $φ$ 関数