包除原理の求め方（3 つの集合）

3 つのグループがあって、それぞれの人数と重なりの人数が分かっているとき、少なくともどれか 1 つに入っている人は何人か。これを求めるのが包除原理です。単純に 3 つの人数を足すと、2 つに入っている人を 2 回、3 つ全部に入っている人を 3 回数えてしまうので、そのままでは多すぎる答えになります。

2 つのときから考える

まず集合が 2 つのときを見ます。A と B を足すと、両方に入っている人だけが 2 回数えられています。ですから 1 回ぶん引きます。

3 つでも同じ考え方で進めますが、今度は引きすぎに気をつける必要があります。

最後に 3 つ全部の重なりを足し戻しているところが要点です。3 つ全部に入っている人は、はじめの $|A| + |B| + |C|$ で 3 回数えられ、続く 3 つの引き算で 3 回引かれます。差し引き 0 回になり、この人たちがまるごと消えてしまいます。そこで 1 回ぶん足し直して、ちょうど 1 回数えた状態に戻します。

例

既定の入力で計算します。全体が 100 人、A が 50 人、B が 40 人、C が 30 人、A と B の重なりが 20 人、B と C が 15 人、C と A が 10 人、3 つ全部が 5 人です。

1. まず足します。50 + 40 + 30 = 120 人
2. 2 つずつの重なりを引きます。120 − 20 − 15 − 10 = 75 人
3. 3 つ全部の重なりを足し戻します。75 + 5 = 80 人

少なくとも 1 つに属するのは 80 人です。全体が 100 人なので、どれにも属さないのは 100 − 80 = 20 人になります。

残りの 2 つも出せます。2 つずつの重なりには 3 つ全部に入っている 5 人が含まれているので、3 か所それぞれから 5 人を引くと、ちょうど 2 つに属する人が $(20 - 5) + (15 - 5) + (10 - 5) = 30$ 人と分かります。そして少なくとも 1 つに属する 80 人から、ちょうど 2 つの 30 人と 3 つ全部の 5 人を引けば、ちょうど 1 つだけに属する人が $80 - 30 - 5 = 45$ 人と出ます。45 + 30 + 5 = 80 となって、つじつまが合っています。

入力のつじつま

数字を適当に入れると、現実にはありえない組み合わせになることがあります。この計算機はそれを見つけると、計算せずに知らせます。

• 3 つ全部の重なりは、2 つずつの重なりのどれよりも多くはなれません
• A の中で B か C にも属する人は $|A \cap B| + |C \cap A| - |A \cap B \cap C|$ 人で、これが A の人数を超えることはありません
• 少なくとも 1 つに属する人が、全体の人数を超えることはありません

アンケートの集計でよく使います。3 つの商品について買ったことがあるかを尋ねたとき、少なくとも 1 つ買った人が何人か、どれも買っていない人が何人か、といった数はこの式で出ます。集合が 4 つ、5 つと増えても考え方は同じで、足す、引く、足す、と符号を交互に入れ替えていきます。