「少なくとも 1 つ」を余事象で数える、そして包除原理へ

「少なくとも 1 つ」と書かれた問題を、そのまま数えにいくと苦しくなります。1 つの場合、2 つの場合、3 つの場合と枝が増えていく。

反対から見ると 1 通りで済みます。「1 つもない」場合を数えて、全体から引く。この引き算が余事象です。

余事象の考え方

全体の場合の数を $N$、条件を満たす場合の数を $a$ とします。条件を満たさない場合は $N-a$ 通り。

「少なくとも 1 つ」の反対は「1 つもない」で、こちらは条件が 1 本しかありません。だから数えやすい。

「少なくとも」という言葉を見たら、まず反対側を見る。これが習慣になると、場合分けがほとんど消えます。

例：サイコロ 3 個で少なくとも 1 個は 6

大中小のサイコロを振ります。目の出方は全部で $6^3=216$ 通り。

6 が 1 個も出ないのは、どのサイコロも 1 から 5 のいずれかになる場合です。$5^3=125$ 通り。

$$216-125=91$$

91 通りになります。直接数えると、6 が 1 個だけ、2 個、3 個と 3 つに分ける必要がある。

念のため直接でも確かめます。1 個だけなら $3\times 5^2=75$、2 個なら $3\times 5=15$、3 個なら 1 で、合計 91。一致しました。

例：コインを 5 回投げて少なくとも 1 回は表

全体は $2^5=32$ 通り。表が 1 回も出ないのは全部裏の 1 通りだけ。

$32-1=31$ 通りです。余事象がたった 1 通りになるので、引き算の効きがいちばん大きい形。

例：3 個のサイコロで少なくとも 2 個が同じ目

反対は「3 個とも違う目」です。こちらなら順に選べます。

$6\times 5\times 4=120$ 通り。全体から引いて $216-120=96$ 通り。

「少なくとも 2 つが同じ」を直接数えると、2 個だけ同じ場合と 3 個とも同じ場合に分かれます。反対側は 1 本で済む。

例：先頭が特定の人にならない並び

6 人が一列に並びます。A が先頭に来ない並び方を数える。

全体は $6!=720$ 通り。A が先頭なのは、残り 5 人を並べる $5!=120$ 通り。

$720-120=600$ 通りです。「〜でない」も余事象で処理できます。

条件が 2 つ以上になると引きすぎる

条件が 1 つなら引き算で足ります。2 つ以上になると、そのままでは合わなくなる。

$1$ から $100$ までで、3 の倍数または 5 の倍数を数えます。3 の倍数は 33 個、5 の倍数は 20 個。

足して 53 とすると誤りです。15 の倍数である 15、30、45、60、75、90 の 6 個を、両方で数えている。

$$33+20-6=47$$

47 個が正しい。重なりを 1 回引いて戻すのが、包除原理のいちばん簡単な形です^[1]。

図のとおり、重なった 6 個だけが二重に数えられます。足してから 1 回引けば帳尻が合う。

集合の記号で書くと次の形になります。$n(A)$ は集合 $A$ の要素の個数です。

$$n(A\cup B)=n(A)+n(B)-n(A\cap B)$$

3 つになると足し戻しが要る

条件が 3 つに増えると、引きすぎが起きます。まず 3 つ足し、2 つずつの重なりを引き、最後に 3 つ全部の重なりを足し戻す。

$$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(A\cap C)-n(B\cap C)+n(A\cap B\cap C)$$

真ん中の 3 つを引いた時点で、3 つすべてに属する要素は 3 回足して 3 回引かれ、0 回になっています。だから 1 回足し戻す^[2]。

例：2 でも 3 でも 5 でも割り切れない数

$1$ から $100$ までで、2、3、5 のどれでも割り切れない整数を数えます。

倍数の個数は 2 が 50 個、3 が 33 個、5 が 20 個。2 つずつの重なりは 6 の倍数が 16 個、10 の倍数が 10 個、15 の倍数が 6 個。3 つすべては 30 の倍数で 3 個。

式に入れます。

$$50+33+20-16-10-6+3=74$$

いずれかで割り切れる数が 74 個。全体の 100 から引いて、どれでも割り切れない数は 26 個です。

図の 7 つの区画を足しても 74 になります。区画ごとに数えるほうが、式より間違えにくいこともある。

例：3 つの部屋に空室なしで入れる

4 人を 1 号室、2 号室、3 号室に入れます。空室を作らない入れ方を数える。

制限なしなら $3^4=81$ 通り。ここから空室のある入れ方を引きます。

ある 1 部屋が空になるのは $2^4=16$ 通りで、その部屋の選び方が 3 通りなので $3\times 16=48$。2 部屋が空になる場合を引きすぎているので、$3\times 1=3$ を足し戻す。

$$81-48+3=36$$

36 通りです。この形の数え上げは、全射の個数と呼ばれる量にあたります^[4]。

例：4 人のじゃんけんであいこ

4 人が 1 回じゃんけんをします。あいこになる場合を数える。

全体は $3^4=81$ 通り。勝負がつくのは、出た手がちょうど 2 種類のときです。

2 種類の選び方が ${}_3{\mathrm{C}}_2=3$ 通り。その 2 種類を 4 人に割り当てるのは $2^4=16$ 通りですが、全員同じ手になる 2 通りは 1 種類しか出ていないので除きます。

$3\times (16-2)=42$ 通りが勝負のつく場合。あいこは $81-42=39$ 通りです。

余事象と包除原理の使い分け

条件が 1 つなら余事象、複数が重なるなら包除原理。境目はここです。

ただし包除原理も、突き詰めれば同じ発想の繰り返し。数えすぎたら引き、引きすぎたら足す、を最後まで続けるだけ。

一般の形

条件が $n$ 個のときも規則は変わりません。1 つずつを足し、2 つの重なりを引き、3 つの重なりを足す、と符号が交互に入れかわります^[3]。

高校で式として書くのは 3 つまでです。4 つ以上は、図か表に整理して数え上げるほうが確実になる。

例：条件を表にして数える

3 つの条件がある問題では、区画を表に並べる手もあります。

合計が 100 になるかを最後に確かめます。合わなければ、どこかの区画が抜けている。

引き算の順序を間違えない

余事象を使うとき、全体をどうとるかで答えが変わります。全体の定義を先に書き留めておく。

「6 個のうち少なくとも 1 個が当たり」なら、全体は 6 個の選び方すべて。当たりの個数ではありません。

よくある誤り

最後に合計が全体に戻るかを確かめる。この一手間で、符号のとり違えはほぼ見つかります。

参考文献

^[1] が包除原理の一般形と応用、^[2] と ^[3] が各国語での定式化、^[4] は空室なしの配り方が持つ意味、^[5] は和の法則の前提です。