文献あり

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

705

本文

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

基礎

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

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

任意の条件 $P, Q$ に対して、 $| P \land Q | \leq | Q |$ および $| \overset{―}{P} \land Q | \leq | Q |$
とくに、 $| P | \leq | ϕ |$ および $| \overset{―}{P} | \leq | ϕ |$

任意の条件 $P$ に対して、実際には $P$ と $\overset{―}{P}$ のうちいずれか一方が成り立っています。
しかし、部分的な条件の組合せを考えるときには、一部の条件の真理値が不問になることもあることに注意します。
例えば、3つの条件 ${P_{1}, P_{2}, P_{3}}$ があるとき、 $P_{1} \land 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}}, \dots, P_{k_{m}}}$ と表されるとき、 $P_{k_{1}} \land P_{k_{2}} \land \dots \land P_{k_{m}}$ を指します。
例えば、 ${P_{1}, P_{2}, P_{3}}$ の部分集合 ${P_{1}, P_{3}}$ には $P_{1} \land P_{3}$ が対応します。

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

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

まず、 $n = 1, 2, 3$ のときの $\land \overset{―}{P_{i}}$ を考えます。

$n = 1$ のとき、
$| \overset{―}{P_{1}} | = | ϕ | - | P_{1} |$

$n = 2$ のとき、
$| \overset{―}{P_{1}} \land \overset{―}{P_{2}} | = | ϕ | - | P_{1} | - | P_{2} | + | P_{1} \land P_{2} |$

$n = 3$ のとき、
$| \overset{―}{P_{1}} \land \overset{―}{P_{2}} \land \overset{―}{P_{3}} | = | ϕ | - | P_{1} | - | P_{2} | - | P_{3} | + | P_{1} \land P_{2} | + | P_{1} \land P_{3} | + | P_{2} \land P_{3} | - | P_{1} \land P_{2} \land P_{3} |$

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

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

包除原理

条件の集合 ${P_{i} | 1 \leq i \leq n}$ の部分集合を整数 $0 \leq x < 2^{n}$ と同一視する。
すべての部分集合 $x$ に対し、そのすべての元の論理積を満たす場合の数が $c (x)$ で与えられるとする。
このとき、
$(1) | \land \overset{―}{P_{i}} | = | \overset{―}{\lor P_{i}} | = \sum_{0 \leq x < 2^{n}} (- 1)^{popcount (x)} c (x)$
$(2) | \lor P_{i} | = c (0) - \sum_{0 \leq x < 2^{n}} (- 1)^{popcount (x)} c (x)$
が成り立つ。
ここで、 $popcount (x)$ は $x$ を $2$ 進数で表したときの $1$ の出現数とする。

概略

$n$ についての数学的帰納法により、 $(1)$ のみ示せばよい。
任意の条件 $P, Q$ に対して、
$| P \land \overset{―}{Q} | = | P | - | P \land Q |$
が成り立つことを利用する ( $P$ で表される領域を2分割する)。

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

例えば $n = 3$ のとき、
$| \overset{―}{P_{1}} \land \overset{―}{P_{2}} \land \overset{―}{P_{3}} | = c (0) - c (1) - c (2) - c (4) + c (3) + c (5) + c (6) - c (7)$
$| P_{1} \lor P_{2} \lor 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}$ があり、それらをすべて満たす場合 ( $\land P_{i}$ ) の数を求めるには、 $P_{i}$ の代わりに $\overset{―}{P_{i}}$ で考えればよいです。
すなわち、 $n$ 個の条件 ${\overset{―}{P_{i}} | 1 \leq i \leq n}$ を一つも満たさない場合の数と見なし、このすべての部分集合について、そのすべての元 (条件) の論理積を満たす場合の数が与えられれば、定理 1 から求めることができます。

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

実例 (全射の個数)

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

全射の個数

$n$ 個の区別できる球を $k$ 個の区別できる箱に入れる方法のうち、すべての箱に $1$ 個以上の球が入る場合の数を求めよ。

箱の番号を $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)^{popcount (x)} (k - popcount (x))^{n}$
これを部分集合の元の個数ごとに整理すると、 $i = popcount (x)$ として、
$S = \sum_{i = 0}^{k} (- 1)^{i}_{k} C_{i} (k - i)^{n} = \sum_{i = 0}^{k} (- 1)^{k - i}_{k} C_{i} i^{n}$
が得られます。

実例 (Euler の totient 関数)

Euler の totient 関数

$n$ を正の整数とする。
$n$ 個の整数 $1, 2, \dots, n$ のうち、 $n$ と互いに素なものの個数を求めよ。

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