条件 (命題) で考える包除原理

本文

包除原理 (inclusion-exclusion principle) は、「集合の元の数」を計算する方法として説明されることが多いようですが、現実の問題に適用するときには「条件 (命題) を満たす場合の数」として考えることもあると思います。
そこで本稿では、「条件」という言葉を使って包除原理を記述することを試みます。本質的にはどちらで説明しても内容は変わりません。

基礎

条件$P$が真であるときの場合の数を$|P|$で表すことにします。
また、条件が一つも設定されていない状態を$\phi$で表すことにします。これはつまり、全事象を指します。

条件は「制約」と言い表してもよく、条件の設定を増やすことで場合の数は減っていきます。
すなわち、次が成り立ちます。

• 任意の条件$P,Q$に対して、$|P \wedge Q| \leq |Q|$ および $|\overline{P} \wedge Q| \leq |Q|$
• とくに、$|P| \leq |\phi|$ および $|\overline{P}| \leq |\phi|$

任意の条件$P$に対して、実際には$P$と$\overline{P}$のうちいずれか一方が成り立っています。
しかし、部分的な条件の組合せを考えるときには、一部の条件の真理値が不問になることもあることに注意します。
例えば、3つの条件 $\{ P_1, P_2, P_3 \}$ があるとき、$P_1 \wedge P_3$ は$P_1, P_3$が真であり、$P_2$については真偽が不問であることを指します。

包除原理で何ができるか

$n$個の条件 $\{ P_i ~|~ 1 \leq i \leq n \}$ の部分集合は$2^n$個あります。
これらのすべての部分集合について、そのすべての元 (条件) の論理積を満たす場合の数が既知である (与えられる) とき、

• $n$個の条件を一つも満たさない場合の数
• $n$個の条件のうち少なくとも一つ満たす場合の数

を求めることができます。

「部分集合のすべての元 (条件) の論理積」とは、ある部分集合が $\{ P_{k_1}, P_{k_2}, \cdots , P_{k_m} \}$ と表されるとき、$P_{k_1} \wedge P_{k_2} \wedge \cdots \wedge P_{k_m}$ を指します。
例えば、$\{ P_1, P_2, P_3 \}$ の部分集合 $\{ P_1, P_3 \}$ には $P_1 \wedge P_3$ が対応します。

条件を一つも満たさない場合の数

$n$個の条件 $\{ P_i ~|~ 1 \leq i \leq n \}$ があり、それらのうち一つも満たさない場合 ($\wedge \, \overline{P_i} = \overline{\vee P_i}$) の数を本節で求めます。
また、それらのうち少なくとも一つ満たす場合 ($\vee \, P_i$) の数を求めるには、上記の否定を考えればよいです。

まず、$n=1,2,3$のときの $\wedge \, \overline{P_i}$ を考えます。

$n=1$のとき、
$$ ~~ |\overline{P_1}| = |\phi| - |P_1| $$

$n=2$のとき、
$$ ~~ |\overline{P_1} \wedge \overline{P_2}| = |\phi| - |P_1| - |P_2| + |P_1 \wedge P_2| $$

$n=3$のとき、
$$ ~~ |\overline{P_1} \wedge \overline{P_2} \wedge \overline{P_3}| = |\phi| - |P_1| - |P_2| - |P_3| \\ \hspace{80pt} + |P_1 \wedge P_2| + |P_1 \wedge P_3| + |P_2 \wedge P_3| - |P_1 \wedge P_2 \wedge P_3| $$

このように、右辺の$2^n$個の項が与えられれば、左辺が求められます。

では、一般の$n$に拡張しましょう。

とくに、$c(0)$は全事象の数を表します。
また、$\mathrm{popcount}(x)$ は、部分集合$x$の元の数と言い換えられます。

例えば$n=3$のとき、
$$ ~~ |\overline{P_1} \wedge \overline{P_2} \wedge \overline{P_3}| = c(0) - c(1) - c(2) - c(4) + c(3) + c(5) + c(6) - c(7) $$
$$ ~~ |P_1 \vee P_2 \vee P_3| = c(1) + c(2) + c(4) - c(3) - c(5) - c(6) + c(7) $$
です。

$c(x)$の計算量オーダーを$C$とすると、全体の時間計算量は$O(C \cdot 2^n)$となります。

条件をすべて満たす場合の数

$n$個の条件 $\{ P_i ~|~ 1 \leq i \leq n \}$ があり、それらをすべて満たす場合 ($\wedge \, P_i$) の数を求めるには、$P_i$の代わりに$\overline{P_i}$で考えればよいです。
すなわち、$n$個の条件 $\{ \overline{P_i} ~|~ 1 \leq i \leq n \}$ を一つも満たさない場合の数と見なし、このすべての部分集合について、そのすべての元 (条件) の論理積を満たす場合の数が与えられれば、定理 1 から求めることができます。

また、$\{ P_i \}$ のうち少なくとも一つ満たさない場合 ($\vee \, \overline{P_i} = \overline{\wedge P_i}$) の数を求めるには、上記の否定を考えればよいです。

実例 (全射の個数)

包除原理を実例で考えてみましょう。

箱の番号を$1 \leq i \leq k$とします。
すると、求める数は、$k$個の条件「箱$i$には$1$個以上の球が入る」をすべて満たす場合の数です。
さらに、これらの否定である$k$個の条件「箱$i$に球は入らない」を一つも満たさない場合の数、と言い換えられます。

これらの$k$個の条件の任意の部分集合の論理積となる場合の数は簡単に得られます。
実際、部分集合の元の個数を$c$とすると、各球に対して$k-c$個の箱を自由に選べるため$(k-c)^n$です。
したがって、包除原理を適用して、
$$ ~~ S = \sum_{0 \leq x < 2^n} (-1)^{\mathrm{popcount}(x)} (k- \mathrm{popcount}(x))^n $$
これを部分集合の元の個数ごとに整理すると、$i=\mathrm{popcount}(x)$として、
$$ ~~ S = \sum_{i=0}^k \, (-1)^i {}_k {\mathrm C}_i \, (k-i)^n = \sum_{i=0}^k \, (-1)^{k-i} {}_k {\mathrm C}_i \, i^n $$
が得られます。

実例 (Euler の totient 関数)

$n$の素因数の種類 (重複なし) が $p_1, p_2, \cdots , p_m$ と表せたとします。
すると、求める数は、$m$個の条件「$p_i$と互いに素」をすべて満たす場合の数です。
さらに、これらの否定である$m$個の条件「$p_i$の倍数」を一つも満たさない場合の数、と言い換えられます。

これらの$m$個の条件の任意の部分集合の論理積となる場合の数は簡単に得られます。
例えば、「$p_i$の倍数」かつ「$p_j$の倍数」は「$p_i p_j$の倍数」です。
したがって、包除原理を適用して求めることができます。

例えば、$n=20$のとき、
$$ ~~ (全体)-(2の倍数)-(5の倍数)+(10の倍数) = 20-10-4+2 = 8 $$
です。

これは Euler の totient 関数 $\varphi(n)$ と呼ばれますが、実はこれをさらに簡潔に計算することができます。
上の定理の証明の中で「$P$で表される領域を2分割する」と書きましたが、このときに「$p_i$の倍数」でない数の割合が$\dfrac{p_i - 1}{p_i}$であることが示せます。
したがって、$1 \leq i \leq m$に対してこれを乗算していけばよく、
$$ ~~ \varphi(n) = n \prod_{1 \leq i \leq m} \frac{p_i - 1}{p_i} $$
が成り立ちます。
この等式を使えば、全体では素因数分解がボトルネックとなり、時間計算量は$O(\sqrt{n})$で済みます。

改訂履歴

• 2021.08.28 全射の個数の例を追記。