はじめに
この記事では、よく知られた包除原理を少し式変形した包除原理の応用例について書きます。 以下、$[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$ を加えた次の式が便利な場合があります。
$$ \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個の共通部分は全体集合）とします。
1つめの包除原理→2つめの包除原理の証明
2つめの包除原理の左辺について以下が成り立ちます。 $$ \begin{align} \left\lvert \bigcap_{i\in[n]} {A_i}^C \right\rvert &= \left\lvert \left(\bigcup_{i\in[n]} {A_i}\right)^C \right\rvert \\ &= \lvert X \rvert - \left\lvert \bigcup_{i\in[n]} {A_i} \right\rvert \end{align} $$ 2つめの包除原理の右辺について以下が成り立ちます。 $$ \begin{align} \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert}\left\lvert\bigcap_{i\in S} {A_i} \right\rvert &= \lvert X \rvert + \sum_{S\subseteq [n],\ S\neq \emptyset } (-1)^{\lvert S \rvert}\left\lvert\bigcap_{i\in S} {A_i} \right\rvert\\ &= \lvert X \rvert - \sum_{S\subseteq [n],\ S\neq \emptyset } (-1)^{\lvert S \rvert -1}\left\lvert\bigcap_{i\in S} {A_i} \right\rvert \end{align} $$ 以上から、1つめの包除原理から2つめの包除原理が示せます。
前回の記事では、2つめの包除原理が証明がしやすく見通しがよいことを書きました。*1
包除原理の応用の点でも、2つめの包除原理が便利なケースがあります。 具体的には、ある種の共通部分の要素数を求める問題で2つめの包除原理を使うと、1つめの包除原理と比べて補集合を考えて引き算をする手間が省けることがあります。 この記事では、2つめの包除原理を使うと証明しやすくなる例を2つ紹介します。
攪乱順列の数（席替えで全員席が変わる場合の数）
包除原理の応用例として、まずは攪乱順列の数について考えます。
$n$ を $0$ 以上の整数とします。$1,2,\ldots,n$ を並び替えてできる順列 $p_1, p_2,\ldots,p_n$ のうち、「$i=1,2,\ldots, n$ に対して $p_i \neq i$」を満たす順列を撹乱順列といいます。長さ $n$ の攪乱順列の数を $a_n$ としたとき、以下が成り立ちます。 $$a_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}$$
撹乱順列は席替えで全員席が変わる席替えの仕方だと考えられます。（$n$ 人で席替えをした場合、席替えの仕方 $n!$ 通りのうち、全員の席が変わる場合の数は $\displaystyle a_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}$ 通りと言えます。）
まずは1つめの包除原理を使った証明を書きます。
撹乱順列ではない順列の数を求めて、$n!$ から引けば、攪乱順列の数が求まります。 撹乱順列ではない順列の数を求めます。
$A_i$ を 「$1,2,\ldots,n$ を並び替えてできる順列 $p_1, p_2,\ldots,p_n$ のうち $p_i = i$を満たす順列全体の集合」とします。攪乱順列でない順列全体は $\bigcup_{i\in [n]} A_i$ です。
1つめの包除原理から次が言えます。 $$ \begin{align} \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 \\ &= \sum_{S\subseteq [n],\ S\neq \emptyset }(-1)^{\lvert S \rvert -1} (n - \lvert S \rvert)! \\ &= \sum_{k=1}^n \binom{n}{k} (-1)^{k -1} (n - k)!\\ &= n! \sum_{k=1}^n \frac{(-1)^{k -1}}{k!} \end{align} $$
2つめの等号について: $\bigcap_{i\in S}{A_i}$ は「各 $i\in S$ に対して順列の $i$ 番目の値が $i$ である順列全体」です。$S$ にない $n-\lvert S\rvert$ 個の元の順列を考えることで、 $\lvert\bigcap_{i\in S}{A_i}\rvert = (n - \lvert S \rvert)!$ が得られます。
以上から、攪乱順列の数 $a_n$ は以下のように求まります。 $$ \begin{align} a_n &= n! - n! \sum_{k=1}^n \frac{(-1)^{k -1}}{k!}\\ &= n!\sum_{k=0}^n \frac{(-1)^k}{k!} \end{align} $$
攪乱順列の条件「$i=1,2,\ldots, n$ に対して $p_i\neq i$を満たす」はある種の共通部分*2を取っていると考えられるので、2つめの包除原理を使うとシンプルに証明ができます。
$A_i$ を 「$1,2,\ldots,n$ を並び替えてできる順列 $p_1, p_2,\ldots,p_n$ のうち $p_i = i$を満たす順列全体の集合」とします。 攪乱順列全体は $\bigcap_{i\in[n]} {A_i}^C$ です。 （ただし、全体集合を順列全体の集合として補集合を考えます。）
2つめの包除原理から次が言えます。 $$ \begin{align} \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 \\ &= \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} (n - \lvert S \rvert)! \\ &= \sum_{k=0}^n \binom{n}{k} (-1)^{k} (n - k)!\\ &= n! \sum_{k=0}^n \frac{(-1)^{k}}{k!} \end{align} $$
2つめの等号について: $\bigcap_{i\in S}{A_i}$ は「各 $i\in S$ に対して順列の $i$ 番目の値が $i$ である順列全体」です。$S$ にない $n-\lvert S\rvert$ 個の元の順列を考えることで、 $\lvert\bigcap_{i\in S}{A_i}\rvert = (n - \lvert S \rvert)!$ が得られます。
以上から、攪乱順列の数 $a_n$ は以下のように求まります。 $$ \begin{align} a_n &= n!\sum_{k=0}^n \frac{(-1)^k}{k!} \end{align} $$
補足: $\bigcap_{i\in \emptyset }{A_i}$ ($S=\emptyset$ の場合) について
2つめの包除原理の説明で、$\bigcap_{i\in \emptyset }{A_i} = X$ （攪乱順列の文脈では、$X$ は順列全体）としました。
- $\bigcap_{i\in \emptyset }{A_i} = X$ とするとうまくいく話
- $\bigcap_{i\in \emptyset }{A_i} = X$ とすると、攪乱順列の数の証明中に現れた $\lvert\bigcap_{i\in S}{A_i}\rvert = (n - \lvert S \rvert)!$ という式は $S=\emptyset$ でも成り立ちます。つまり、$\bigcap_{i\in \emptyset }{A_i} = X$ とすると、攪乱順列の数の証明がうまくいくことがわかります。
- $\bigcap_{i\in \emptyset }{A_i} = X$ の解釈
- $A_1 \cap A_2$ は $A_1$ にも $A_2$ にも属している順列全体ですが、$\bigcap_{i\in \emptyset }{A_i}$ は $A_1, A_2$ などに属しているという条件が課せられていないので、単に順列全体であると解釈ができます。
- $\bigcap_{i\in S }{A_i} = \{ x\in X \mid \forall i \in S,\ x \in A_i\}$ と定義されていると考えて、$\bigcap_{i\in \emptyset }{A_i} = X$ が導けるという解釈もできます。
攪乱順列の数という文脈において、2つめの包除原理には以下のメリットがあります。
- 1つめの包除原理を使った証明では、順列全体の数から攪乱順列でない順列の数を引くということを考えました。2つめの包除原理を使った証明では、全体から引くという計算がない分シンプルになりました。
- $\displaystyle a_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}$ という式は、1つめの包除原理の式より2つめの包除原理の式に似ています（総和が $k=0$ から始まる部分や $(-1)^k$ の部分が似ています）。そのため、$a_n$ の式を覚えるという場合は2つめの包除原理を意識すると覚えやすいです。
全射の数（グループ分けの場合の数）
次に、包除原理の応用として全射の数について考えます。
全射の数は、$\lvert X \rvert $ 人を $\lvert Y \rvert $ 個の（区別する）グループにグループ分けをする（各グループは1人以上入るようにする）ときの分け方の数だと考えることができます。
まずは1つめの包除原理を使った証明を書きます。
全射でない写像の数を求めて、写像の総数 ${\lvert Y \rvert}^{\lvert X \rvert }$ から引けば、全射の数が求まります。 全射ではない写像の数を求めます。
$Y = \{y_1, y_2, \ldots, y_{\lvert Y \rvert }\}$とします。 $A_i = \{f\colon X \to Y \mid y_i \notin f(X)\}$ （$y_i$ を値に持たない写像全体）とします。 このとき、全射でない写像全体は $\bigcup_{i \in [\lvert Y\rvert ]} A_i$ となります。
１つ目の包除原理から次が言えます。 $$ \begin{align} \left\lvert \bigcup_{i\in [\lvert Y \rvert ]} {A_i} \right\rvert &= \sum_{S\subseteq [\lvert Y \rvert ],\ S\neq \emptyset }(-1)^{\lvert S \rvert -1} \left\lvert\bigcap_{i\in S}{A_i}\right\rvert \\ &= \sum_{S\subseteq [\lvert Y \rvert ],\ S\neq \emptyset }(-1)^{\lvert S \rvert -1} (\lvert Y \rvert - \lvert S \rvert)^{\lvert X \rvert} \\ &= \sum_{k=1}^n (-1)^{k -1}\binom{\lvert Y \rvert}{k} (\lvert Y \rvert - k)^{\lvert X \rvert}\\ \end{align} $$
2つめの等号について: $\bigcap_{i\in S}{A_i}$ は「$\lvert S \rvert$ 個の値 $y_i\ (i\in S)$ を値に取らない写像全体の集合」です。よって、 $\lvert\bigcap_{i\in S}{A_i}\rvert = (\lvert Y \rvert - \lvert S \rvert)^{\lvert X \rvert}$ が得られます。
以上から、求めたい全射の総数は以下のように求まります。 $$ \begin{align} &\quad {\lvert Y \rvert}^{\lvert X \rvert } - \sum_{k=1}^n (-1)^{k -1}\binom{\lvert Y \rvert}{k} (\lvert Y \rvert - k)^{\lvert X \rvert}\\ &= \sum_{k=0}^n (-1)^k \binom{\lvert Y \rvert}{k} (\lvert Y \rvert - k)^{\lvert X \rvert} \end{align} $$
次に2つめの包除原理を使った証明を書きます。$X$ から $Y$ への写像が全射であるとは「任意の $y\in Y$ に対して $y \in f(X)$ である」というように、ある種の共通部分として書けます。具体的には全射全体は以下のように書けます。 $$ \{f\colon X\to Y \mid \forall y \in Y,\ y\in f(X)\} = \bigcap_{y\in Y} \{f\colon X\to Y \mid y \in f(X)\} $$ よって、2つめの包除原理を使うとシンプルに証明が書けます。
$Y = \{y_1, y_2, \ldots, y_{\lvert Y \rvert }\}$とします。 $A_i = \{f\colon X \to Y \mid y_i \notin f(X)\}$ （$y_i$ を値に持たない写像全体）とします。 このとき、$X$ から $Y$ への全射全体は $\bigcap_{i \in [\lvert Y\rvert ]} {A_i^C}$ となります。
2つ目の包除原理から次が言えます。 $$ \begin{align} \left\lvert \bigcap_{i\in [\lvert Y \rvert ]} {A_i}^C \right\rvert &= \sum_{S\subseteq [\lvert Y \rvert ]}(-1)^{\lvert S \rvert} \left\lvert\bigcap_{i\in S}{A_i}\right\rvert \\ &= \sum_{S\subseteq [\lvert Y \rvert ]}(-1)^{\lvert S \rvert} (\lvert Y \rvert - \lvert S \rvert)^{\lvert X \rvert} \\ &= \sum_{k=0}^n (-1)^{k}\binom{\lvert Y \rvert}{k} (\lvert Y \rvert - k)^{\lvert X \rvert}\\ \end{align} $$
2つめの等号について: $\bigcap_{i\in S}{A_i}$ は「$\lvert S \rvert$ 個の値 $y_i\ (i\in S)$ を値に取らない写像全体の集合」です。よって、 $\lvert\bigcap_{i\in S}{A_i}\rvert = (\lvert Y \rvert - \lvert S \rvert)^{\lvert X \rvert}$ が得られます。
以上から、求めたい全射の総数は以下の通りです。 $$ \sum_{k=0}^n (-1)^{k}\binom{\lvert Y \rvert}{k} (\lvert Y \rvert - k)^{\lvert X \rvert} $$
おわりに
2種類の包除原理を紹介しました。また、包除原理の応用例として、攪乱順列の数と全射の数を求めました。 攪乱順列の数と全射の数の導出を通して、2つめの包除原理には以下のメリットがあることがわかりました。
- 2つめの包除原理の方が証明がシンプルになることがあります（全体から引く部分がない分）。とくに、ある種の共通部分の要素数を求める問題で有効です。
- 2つめの包除原理が背景にあると、攪乱順列の数や全射の数の式が覚えやすい（納得しやすい）です。
