【競プロ】包除原理-1

まえがき

今回はABC206の「E - Divide Both」の解法を理解するために記事を書いています。
この問題の公式解説ではABC162のE問題が参照されており、こちらの有志解説記事では約数系包除が前提知識となっていました。
約数系包除は包除原理の派生らしいですがどちらも初見のため、まずは包除原理について理解していきます。

本記事では有志解説記事で紹介されていた包除原理についての偉大なスライドを参考にします。

包除原理とは

包除原理は和集合の要素数を、積集合の要素数から求められるようになる等式です。

$$
\begin{align*}
\left| \bigcup_{i=1}^{n} A_{i} \right| &= \sum_{k=1}^{n} (-1)^{k-1} \sum_{J\subseteq[n], |J|=k} \left| \bigcap {j\in J} A{j} \right| \\
&= \sum_{i} |A_{i}| - \sum_{i<j} \left|A_{i}\cap A_{j}\right| + \cdots + (-1)^{n-1} \left| \bigcap {i=1}^{n} A{i} \right|
\end{align*}
$$

式は一見難しいですが、この式は全ての奇数個の積集合の要素数を足し、全ての偶数個の積集合の要素数を引くと、和集合全体の要素数になると言っています。

等式を試すため、30以下の自然数の中で2か3か5の倍数である数の個数を考えます。
該当しない数は$\{1,7,11,13,17,19,23,29\}$の8個のため、該当する数は22個です。
$U=\{x \in \mathbb{N} \mid x \leq 30 \}$、$A=\{x \in U \mid xは2の倍数\}$、$B=\{x \in U \mid xは3の倍数\}$、$C=\{x \in U \mid xは5の倍数\}$とすると、
$$
\begin{align*}
\sum_{k=1}^{n} (-1)^{k-1} \sum_{J\subseteq[n], |J|=k} \left| \bigcap {j\in J} X{j} \right| &= \sum_{i} |X_{i}| - \sum_{i<j} \left|X_{i}\cap X_{j}\right| + \cdots + (-1)^{n-1} \left| \bigcap {i=1}^{n} X{i} \right| \\
&= (|A| + |B| + |C|) - (|A \cap B| + |A \cap C| + |B \cap C|) + (|A \cap B \cap C|) \\
&= (15 + 10 + 6) - (5 + 3 + 2) + 1 \\
&= 31 - 10 + 1 \\
&= 22
\end{align*}
$$
となり、要素数が包除原理の右辺の結果と等しくなります。

包除原理の証明

包除原理の証明方法はいくつか有り、高校数学の美しい物語 - 包除原理の２通りの証明では二項定理による証明と数学的帰納法による証明が紹介されています。
二項定理による証明の方が好みだったため、本記事では二項定理による証明を紹介します。

まず和集合全体を積集合の集合個数ごとに分けます。
任意の集合数の積集合で包除原理の等式の右辺が1となれば、全ての要素を重複せず数えていることになり、右辺が和集合全体の要素数と等しいことになります。

次に集合個数mの積集合について考え、包除原理の等式の右辺から抽出します。
第1項の$\sum_{i} |A_{i}|$では、集合個数の数だけ足されるため、m回足されます。
第2項では構成する集合から2集合の積集合を作り、その組み合わせの数だけ引かれています。
これはm個から2個選んだ組み合わせの数だけ引くということのため、引いてる数は${}_m C_2$になります。
選ぶ集合数をkとすると、以降もkが奇数であれば${}_m C_k$足され、偶数であれば${}m C_k$引かれています。
これを総和で書くと、
$$
\sum{k=1}^{m} (-1)^{k-1} {}_m C_k
$$
となります。
この総和が1と等しければ、包除原理では全ての要素を重複せず数えていることになります。

最後の証明前準備として二項定理の等式を示します。
二項定理の等式は以下です。
$$
(a + b)^{n} = \sum_{k=0}^{n} {}_n C_k a^{n-k} b^{k}
$$

二項定理の等式で$a = 1, b = -1$とすると、
$$
\begin{align*}
(1 - 1)^{m} &= \sum_{k=0}^{m} (-1)^{k} {}m C_k \\
&= 1 + \sum{k=1}^{m} (-1)^{k} {}m C_k \\
&= 1 - \sum{k=1}^{m} (-1)^{k-1} {}_m C_k
\end{align*}
$$
となります。

$(1 - 1)^{m} = 0$のため、
$$
\sum_{k=1}^{m} (-1)^{k-1} {}_m C_k = 1
$$
となります。
任意の集合数の積集合で包除原理の右辺が1となるため、右辺は要素を重複せず数えており、和集合全体の要素数と等しいことが証明されました。

あとがき

今回は包除原理とその証明を紹介しました。
次回は包除原理を使用する問題を見て応用方法を学んでいきます。