包除原理の一般形 | 場合の数と確率統計

1 一般形

定理 1.1 (包除原理). $A_1,\ldots,A_n$ を有限集合とします。このとき

\left|\bigcup_{i=1}^{n}A_i\right| =\sum_i|A_i| -\sum_{i<j}|A_i\cap A_j| +\sum_{i<j<k}|A_i\cap A_j\cap A_k| -\cdots +(-1)^{n+1}|A_1\cap\cdots\cap A_n|

が成り立ちます。

証明. 和集合の一つの要素 $x$ を取り、 $x$ がちょうど $r$ 個の集合に属するとします。右辺で $x$ は

{}_rC_1-{}_rC_2+\cdots+(-1)^{r+1}{}_rC_r

回数えられます。二項定理

0=(1-1)^r ={}_rC_0-{}_rC_1+{}_rC_2-\cdots+(-1)^r{}_rC_r

から、この交代和は1です。したがって、和集合の各要素は右辺でちょうど一度ずつ数えられます。▨

$n$ 人へ宛名の異なる $n$ 通の手紙を一通ずつ配ります。誰も自分宛ての手紙を受け取らない配り方を数えます。

例 2.1 (完全順列の個数). 全順列の集合を $U$ とし、人 $i$ が自分宛ての手紙を受け取る順列の集合を $A_i$ とします。求める個数 $D_n$ は

D_n=\left|U\setminus\bigcup_{i=1}^{n}A_i\right|

です。指定した $k$ 人を固定する順列は $(n-k)!$ 通りなので、包除原理から

D_n=n!-{}_nC_1(n-1)!+{}_nC_2(n-2)!-\cdots+(-1)^n =n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}

を得ます。

注意 2.2 (適用時の確認). 各集合 $A_i$ が何を表すか、複数の条件を同時に満たす対象が何個あるか、最後の符号が正か負かを確認します。条件の否定を直接数えるときは、全体集合も明示します。

1の答えは

500+333+200-166-100-66+33=734

個です。2の答えは $24-24+12-4+1=9$ 通りです。3では $3-3+1=1$ となります。

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

包除原理を用いて、次の個数を求めよ。

異なる 5 個のボールを、区別できる 3 個の箱に、どの箱も空にならないように入れる方法は何通りあるか。

解法の型 $n(A\cup B\cup C)$ $=$ n(A)+n(B)+n(C) − $n(A\cap B)$ − $n(B\cap C)$ − $n(C\cap A)$ + $n(A\cap B\cap C)$ （奇数個の共通部分は +、偶数個は −）