はじめに
この記事では指示関数を使った包除原理の証明をします。 $[n] = \{1,2,\ldots, n\}$ とします。 $X$ を有限集合として、各 $i\in [n]$ に対して $A_i$ を $X$ の部分集合とします。
よくある包除原理は次の形をしています。
$$ \left\lvert \bigcup_{i\in[n]} {A_i} \right\rvert = \sum_{S\subseteq [n],\ S\neq \emptyset } (-1)^{\lvert S \rvert -1} \left\lvert\bigcap_{i\in S} {A_i} \right\rvert $$
両辺 $-1$ 倍して $\lvert X \rvert$ を加えた、次の式で包除原理が使われることもあります。*1
$$ \left\lvert \bigcap_{i\in[n]} {A_i}^C \right\rvert = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} \left\lvert\bigcap_{i\in S} {A_i} \right\rvert $$ ただし、$\bigcap_{i\in \emptyset} {A_i} = X$ （0個の共通部分は全体集合）とします。
今回は扱いやすさから2つめの包除原理を証明します。（2つめから1つめは簡単に示せます。） また、証明の方法として、数学的帰納法ではなく、指示関数を使った証明をします。
指示関数による包除原理の証明
指示関数とは以下のような関数です。
$X$ の部分集合 $A$ に対して、$1_A\colon X\to \{0,1\}$ を次のように定義します。 $$1_A(x) = \begin{cases}1& x\in A\\0 &x\notin A\end{cases}$$ このとき、$1_A$ を $A$ の指示関数と呼びます。
指示関数を用いた以下の補題を使うと包除原理は簡単に示せます。
$$1_{\bigcap_{i\in[n]} {A_i}^C} = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S} {A_i}}$$
この補題4から包除原理を示す方法は以下の通りです。
一般に、$A\subseteq X$ に対して、$\lvert A \rvert = \sum_{x\in X} 1_A(x)$ です。
補題4の両辺に $x\in X$ を適用し、各 $x\in X$ を足し合わせることで定理2が得られます。 具体的には以下の通りです。 $$ \begin{align} \left\lvert \bigcap_{i\in[n]} {A_i}^C \right\rvert & = \sum_{x\in X} 1_{\bigcap_{i\in[n]} {A_i}^C}(x) \\ & = \sum_{x\in X} \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S}A_i}(x) \\ & = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} \sum_{x\in X} 1_{\bigcap_{i\in S}A_i}(x) \\ & = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} \left\lvert\bigcap_{i\in S} {A_i} \right\rvert \end{align} $$
補題4を証明します。
$x\in X$ を任意に取ります。$M = \{i \in [n] \mid x\in A_i\}$, $m = \lvert M \rvert$ とします。
補題4の左辺と右辺に $x$ を適用した式はそれぞれ以下のように変形できます。 $$ \begin{align} {\left[\sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S} {A_i}}\right]}(x) &= \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S} {A_i}}(x)\\ &= \sum_{S\subseteq M} (-1)^{\lvert S \rvert} \\ &= \sum_{k=0}^m (-1)^k \binom{m}{k} \\ &= (1-1)^m \\ &= 0^m \end{align} $$ $$ \begin{align} 1_{\bigcap_{i\in[n]} {A_i}^C}(x) &= \begin{cases}1 & m=0 \\0 & m >0 \end{cases} \\ &= 0^m \end{align} $$
2つめの等号は以下から言えます。 $$ \begin{align} 1_{\bigcap_{i\in S} {A_i}}(x) = \begin{cases}1 &S\subseteq M\\ 0 & S \not \subseteq M\end{cases} \end{align} $$
3つめの等号は、$\lvert S \rvert = k$ となる $S \subseteq M $ は $\binom{m}{k}$ 通りあることから言えます。
4つめの等号は二項定理から言えます。
以上で、補題4が示されました。
以上で包除原理は示されました。
包除原理に出てくる $-1$ の冪乗が $(1-1)^m $ に二項定理を適用して出てくる $-1$ の冪乗と対応づけられることを考えると、個人的には2つめの包除原理のほうがきれいに感じます。
補題4は代数的な計算によっても証明できるので紹介します。
$A, B\subseteq X$ に対して、$1_{A\cap B} = 1_A1_B,\ 1_{A^C} = 1- 1_A$ が成り立つことを利用します。以下のような指示関数の式変形から示せます。
$$ \begin{align} 1_{\bigcap_{i\in[n]} {A_i}^C} &= \prod_{i\in [n]} 1_{{A_i}^C}\\ &= \prod_{i\in [n]} (1-1_{A_i})\\ &= \sum_{S\subseteq [n]} \prod_{i\in S}(-1_{A_i})\\ &= \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} \prod_{i\in S}1_{A_i}\\ &= \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S}{A_i}} \end{align} $$
式を展開するだけで包除原理が示せるのはおもしろいです。
確率の包除原理の証明
補題4の指示関数による包除原理の記述によって、確率での包除原理も示せます。
$X$ を標本空間、各 $A_i$ を事象としたとき、以下が成り立ちます。
$$ P{\left( \bigcap_{i\in[n]} {A_i}^C \right)} = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} P{\left(\bigcap_{i\in S} {A_i} \right)} $$
証明を2パターン提示します。（1つめは補題4→定理2の証明とよく似ています）
X が有限集合で $X$ の部分集合がすべて事象であるとします。 このとき、$A \subseteq X$ に対して、$P(A) = \sum_{x\in A} P(\{x\}) = \sum_{x\in X} 1_A(x) P(\{x\})$ が成り立ちます。このことから以下のように示せます。
$$ \begin{align} P{\left( \bigcap_{i\in[n]} {A_i}^C \right)} & = \sum_{x\in X} 1_{\bigcap_{i\in[n]} {A_i}^C}(x) P(\{x\})\\ & = \sum_{x\in X} \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S}A_i}(x) P(\{x\})\\ & = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} \sum_{x\in X} 1_{\bigcap_{i\in S}A_i}(x) P(\{x\})\\ & = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} P{\left(\bigcap_{i\in S} {A_i} \right)} \end{align} $$
事象 $A \subseteq X$ に対して、$P(A) = E[1_A]$ が成り立ちます（ただし、$E[\cdot]$ は期待値を表します）。このことから、以下のように示せます。
$$ \begin{align} P{\left( \bigcap_{i\in[n]} {A_i}^C \right)} & = E{\left[1_{\bigcap_{i\in[n]} {A_i}^C}\right]}\\ & = E{\left[\sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S}A_i}\right]}\\ & = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} E{\left[1_{\bigcap_{i\in S}A_i}\right]}\\ & = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} P{\left(\bigcap_{i\in S} {A_i} \right)} \end{align} $$
途中、期待値の線形性を使っています。
補題4の指示関数による包除原理を使うと、確率の包除原理も示せるのはおもしろいなと思いました。
おわりに
指示関数で記述した包除原理を示し、集合や確率における包除原理を示しました。
指示関数を使うと集合の包除原理にも確率の包除原理にも使え、また指示関数によって包除原理の式の見通しが良くなるのがおもしろいなと感じました。
包除原理の応用については以下の記事で扱っているので、合わせてご覧ください。
参考文献
- 包除原理 - Wikipedia
- 包除原理の２通りの証明 | 高校数学の美しい物語 指示関数による証明は Wikipedia に記載されていましたが、行間があったため本記事では行間を埋めました。行間を埋める際には「高校数学の美しい物語」さんの証明を参考にしました。
*1:例: ABC309 G の公式解説 https://atcoder.jp/contests/abc309/editorial/6745
（最初の4行しかわからない）
