§B4.4包除原理の一般形

最終更新

複数の条件の少なくとも一つを満たす対象を数えるときは、各条件を満たす対象の集合を考えます。それらの集合の要素の個数を足し、二つの集合の共通部分の要素の個数を引き、三つの集合の共通部分の要素の個数を足すというように、共通部分をとる集合の個数に応じて符号を交互に変えて足し引きします。

1 一般形

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

∣⋃i=1nAi∣=∑i∣Ai∣−∑i<j∣Ai∩Aj∣+∑i<j<k∣Ai∩Aj∩Ak∣−⋯+(−1)n+1∣A1∩⋯∩An∣\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|

が成り立ちます。

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

rC1−rC2+⋯+(−1)r+1rCr{}_rC_1-{}_rC_2+\cdots+(-1)^{r+1}{}_rC_r

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

0=(1−1)r=rC0−rC1+rC2−⋯+(−1)rrCr0=(1-1)^r ={}_rC_0-{}_rC_1+{}_rC_2-\cdots+(-1)^r{}_rC_r

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

2 錯排への適用

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

例 2.1. 全順列の集合をUUとし、人iiが自分宛ての手紙を受け取る順列の集合をAiA_iとします。求める個数DnD_nは

Dn=∣U∖⋃i=1nAi∣D_n=\left|U\setminus\bigcup_{i=1}^{n}A_i\right|

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

Dn=n!−nC1(n−1)!+nC2(n−2)!−⋯+(−1)n=n!∑k=0n(−1)kk!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 (適用時の確認). 各集合AiA_iが何を表すか、複数の条件を同時に満たす対象が何個あるか、最後の符号が正か負かを確認します。条件の否定を直接数えるときは、全体集合も明示します。

3 例題

レベル2 — 包除原理

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

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

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

例 3.1.

∑i=03(−1)i(3i)(3−i)5\sum_{i=0}^{3} (-1)^i \binom{3}{i} (3-i)^{5}

答150150

注意 全部の入れ方は 3^5==243 通り。A_i を「i 番目の箱が空」とすると、指定した j 個の箱が空になる入れ方は (3−j)^5 通りで、その組は C(3, j) 通り。包除原理で「少なくとも1つ空」を引くと 243 − 96 + 3==150。

4 演習

問題 4.1. 1以上1000以下の整数のうち、2、3、5の少なくとも一つで割り切れるものの個数を求めよ。

解答.

1以上1000以下の整数のうち、2、3、5で割り切れるものの集合をそれぞれA2,A3,A5A_2,A_3,A_5とする。1以上1000以下のmmの倍数の個数は1000/m1000/mの整数部分である。2、3、5は互いに素なので、二つまたは三つの集合の共通部分は、それらの積の倍数の集合である。したがって、

∣A2∣=500,∣A3∣=333,∣A5∣=200,∣A2∩A3∣=166,∣A2∩A5∣=100,∣A3∩A5∣=66,∣A2∩A3∩A5∣=33|A_2|=500,\quad|A_3|=333,\quad|A_5|=200,\quad|A_2\cap A_3|=166,\quad|A_2\cap A_5|=100,\quad|A_3\cap A_5|=66,\quad|A_2\cap A_3\cap A_5|=33

である。定理 1.1により、

∣A2∪A3∪A5∣=500+333+200−166−100−66+33=734|A_2\cup A_3\cup A_5|=500+333+200-166-100-66+33=734

であり、求める個数は734個である。▨

問題 4.2. 4人の完全順列の個数D4D_4を、例 2.1の式から求めよ。

解答.

例 2.1の式でn=4n=4とすると、

D4=4!−4C1⋅3!+4C2⋅2!−4C3⋅1!+4C4⋅0!=24−24+12−4+1=9D_4=4!-{}_4C_1\cdot3!+{}_4C_2\cdot2!-{}_4C_3\cdot1!+{}_4C_4\cdot0!=24-24+12-4+1=9

であり、D4=9D_4=9である。▨

問題 4.3.定理 1.1の証明で、和集合の一つの要素がちょうどrr個の集合に属するとき右辺で一度だけ数えられることを、r=3r=3の場合に確かめよ。

解答.

要素xxがちょうど3個の集合Aa,Ab,AcA_a,A_b,A_cに属するとする。右辺の第1の和では、xxは∣Aa∣,∣Ab∣,∣Ac∣|A_a|,|A_b|,|A_c|の3項で数えられ、3C1=3{}_3C_1=3回加えられる。第2の和では、xxを含む共通部分はAa∩AbA_a\cap A_b、Aa∩AcA_a\cap A_c、Ab∩AcA_b\cap A_cの3C2=3{}_3C_2=3個なので、3回引かれる。第3の和では、xxを含む共通部分はAa∩Ab∩AcA_a\cap A_b\cap A_cの3C3=1{}_3C_3=1個なので、1回加えられる。4個以上の集合の共通部分にxxは属さない。したがって、xxが右辺で数えられる回数は3−3+1=13-3+1=1である。▨

レベル2 — 包除原理

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

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

問題 4.4. 1 から 126 までの整数のうち、2, 3, 7 のいずれかで割り切れるものは何個あるか。

#{ k∣1≤k≤126, 2∣k or 3∣k or 7∣k }\#\{\, k \mid 1 \le k \le 126,\ 2 \mid k\ \text{or}\ 3 \mid k\ \text{or}\ 7 \mid k \,\}
解答.

答9090

注意 A, B, C をそれぞれ 2, 3, 7 の倍数の集合とすると n(A)==63, n(B)==42, n(C)==18。2, 3, 7 は互いに素なのでn(A∩B)n(A\cap B)は 6 の倍数の個数==21、同様にn(B∩C)=n(B\cap C) =6,n(C∩A)=n(C\cap A) =9,n(A∩B∩C)=n(A\cap B\cap C) =3。包除原理より 63 + 42 + 18 − 21 − 6 − 9 + 3==90。▨

問題 4.5. 4 人がそれぞれ1個ずつプレゼントを持ち寄り、無作為に1個ずつ受け取る。全員が自分以外のプレゼントを受け取る配り方は何通りあるか。

D4=∑k=04(−1)k(4k)(4−k)!D_{4} = \sum_{k=0}^{4} (-1)^k \binom{4}{k} (4-k)!
解答.

答99

注意 A_i を「i 番目の人が自分のプレゼントを受け取る」事象の集合とすると、k 個の A_i の共通部分の要素数は (4−k)! で、その組は C(4, k) 通り。包除原理より D_4==24 − 24 + 12 − 4 + 1==9。（全体 24 通りのうち 9 通りで、割合は約 0.375。人数を増やしても 1/e≈\approx0.368 に近づくだけで頭打ちになる。）▨

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

∑i=03(−1)i(3i)(3−i)6\sum_{i=0}^{3} (-1)^i \binom{3}{i} (3-i)^{6}
解答.

答540540

注意 全部の入れ方は 3^6==729 通り。A_i を「i 番目の箱が空」とすると、指定した j 個の箱が空になる入れ方は (3−j)^6 通りで、その組は C(3, j) 通り。包除原理で「少なくとも1つ空」を引くと 729 − 192 + 3==540。▨

前提記事