包除原理の拡張を考える - pencoderのブログ

多次元累積和を用いて多次元配列の矩形範囲の総和を計算するときに必要になったので，包除原理の拡張を考えました．

全体集合 $\Omega$ の $n (\geq 1)$ 個の部分集合 $A_1, A_2, \cdots , A_n$ と写像 $f\colon\Omega\to\mathbb{R}$ を考えます．このとき，和集合 $\bigcup_{i=1}^n A_i$ の全ての要素の $f$ による像の総和 $\sum_{a\in\bigcup_{i=1}^n A_i} f(a)$ について次の等式が成り立ちます．

$\displaystyle \sum_{a\in\bigcup_{i=1}^n A_i} f(a) = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k A_{i_j}} f(a)$

$\forall_{a\in\Omega} f(a)=1$ のとき，和集合の要素数 $|\bigcup_{i=1}^n A_i|$ を計算する通常の包除原理と一致します．

証明

数学的帰納法を用いて証明します．

まず， $n=1$ ，即ち集合が1個のときを考えると，

$\displaystyle (\text{左辺}) = (\text{右辺}) = \sum_{a\in A_1} f(a)$

より成り立ちます．

次に， $n(n \geq 1)$ 個の集合について成り立つと仮定し， $n+1$ 個の集合について考えます．

$\displaystyle \begin{align} (\text{左辺}) & = \sum_{a \in \bigcup_{i=1}^{n+1} A_i} f(a) \\ & = \sum_{a \in (\bigcup_{i=1} A_i)\cup A_{n+1}} f(a) \\ & = \sum_{a \in \bigcup_{i=1}^n A_i} f(a) + \sum_{a \in A_{n+1}} f(a) - \sum_{a \in (\bigcup_{i=1}^n A_i)\cap A_{n+1}} f(a) \\ & = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k A_{i_j}} f(a) + \sum_{a \in A_{n+1}} f(a) - \sum_{a \in (\bigcup_{i=1}^n (A_i \cap A_{n+1}))} f(a) \\ \end{align}$

ここで，

$\displaystyle \begin{align} \sum_{a \in (\bigcup_{i=1}^n (A_i \cap A_{n+1}))} f(a) & = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k (A_{i_j} \cap A_{n+1})} f(a) \\ & = \sum_{k=2}^{n+1} (-1)^k \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) - \sum_{k=2}^n (-1)^k \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = -\sum_{k=2}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) + \sum_{k=2}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \end{align}$

より，

$\displaystyle \begin{align} (\text{左辺}) & = \sum_{k=1}^1 (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k A_{i_j}} f(a) + \sum_{a \in A_{n+1}} f(a) + \sum_{k=2}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = \sum_{i=1}^{n+1} \sum_{a \in A_i} f(a) + \sum_{k=2}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = \sum_{k=1}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = (\text{右辺}) \end{align}$

よって， $n+1$ 個の集合についても成り立ちます．

以上より，全ての正の整数 $n$ について成り立つことが示されました．