包除原理——三つの集合の数え過ぎと条件付きの数え上げ

三つの名簿を足すと誰が何回数えられるのか。小さな集合を実際に並べて包除原理を導き、「ちょうど二つ」「どれにも入らない」や、条件で全体を絞った数え上げに使う。

この単元の目標

三集合の包除原理の符号を、要素が数えられる回数から説明できる
少なくとも一つ・ちょうど二つ・どれにも属さない個数を区別できる
倍数や文字列の条件を集合の共通部分に翻訳して数えられる
追加条件があるとき、全体集合と各共通部分を同じ条件で制限できる

📑 目次

1. 名簿の行数と、実際の人数は違う
2. 一人が最後に一回数えられる式を作る
3. 「少なくとも」と「ちょうど」は別の要求
4. 例題：倍数の共通部分は最小公倍数で作る
5. 例題：「全部使う」は「何かが欠ける」の反対
6. 条件が増えたら「全体」と「悪い集合」を一緒に絞る

1. 名簿の行数と、実際の人数は違う

三つの体験講座に申し込んだ人へ、案内を一人一通だけ送るとします。講座ごとの名簿の行数を足すと、複数講座に申し込んだ人へ何通も送ってしまいます。欲しいのは延べ申込数ではなく、重複を取り除いた人数です。まず図ではなく、番号の小さな集合で「誰を何回数えたか」を追いましょう。以下の名簿や問題のデータは説明用に作ったものです。

全体を U＝{1,2,3,4,5,6,7,8} とし、三つの名簿を A＝{1,2,3,4}、B＝{3,4,5,6}、C＝{4,6,7} とします。A∪B∪C は「少なくとも一つに入る」集合、A∩B は「AとBの両方に入る」集合です。n(A) は有限集合 A の要素数を表します。名簿の内部では、同じ番号は一度だけ記載されているものとします。

番号	入っている名簿	三名簿を足したときの回数
1, 2	Aだけ	各1回
3	AとBだけ	2回
4	AとBとC	3回
5	Bだけ	1回
6	BとCだけ	2回
7	Cだけ	1回
8	どれにも入らない	0回

行数は4＋4＋3＝11ですが、実際に送る相手は{1,2,3,4,5,6,7}の7人です。二名簿の共通部分は A∩B＝{3,4}、A∩C＝{4}、B∩C＝{4,6}。これらの個数2＋1＋2を引くと、3と6は一度ずつに直ります。しかし4は三つの共通部分すべてで引かれ、3−3＝0回になってしまいます。4を最後に一度戻せば、11−5＋1＝7人です。

A∩Bは「AとBだけ」ではありません。Cにも入る4を含みます。「二つの共通部分を引けば終わり」とすると、三つすべてに入る人を消してしまいます。足し戻すのは、その引き過ぎを修復するためです。

2. 一人が最後に一回数えられる式を作る

番号の代わりに、ある一つの要素が何集合に入るかだけを見ます。一集合だけなら足す回数は1、引く回数は0。二集合なら2回足し、共通部分で1回引きます。三集合なら3回足し、三組の共通部分で3回引き、最後に1回戻します。どの場合も最終的に1回になるため、この手順は名簿の大きさによらず使えます。

所属する集合の数	足す回数	二集合の共通部分で引く回数	三集合分を戻す回数	最終回数
0	0	0	0	0
1	1	0	0	1
2	2	1	0	1
3	3	3	1	1

\begin{aligned}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).\end{aligned}

これが三集合の包除原理です。ここでは A、B、C を同じ有限な全体集合 U の部分集合とします。排反や独立の仮定は不要です。数える単位は終始「人」「整数の個数」「文字列の通り数」などにそろえます。確率の近似ではなく、整数として正確な計数です。

3. 「少なくとも」と「ちょうど」は別の要求

ちょうど二集合に属する人を数えたいなら、二集合の共通部分を足すのが出発点です。ただし三集合すべてに属する人は、その和に3回登場します。今度は一回残すのではなく、完全に除きたいので3回分を引きます。ちょうど一集合なら、最初の延べ数から二重所属を消し、三重所属も消すよう回数を調整します。

\begin{gathered}S_1=n(A)+n(B)+n(C),\quad S_2=n(A\cap B)+n(A\cap C)+n(B\cap C),\\T=n(A\cap B\cap C),\\N_{\text{ちょうど2}}=S_2-3T,\qquad N_{\text{ちょうど1}}=S_1-2S_2+3T,\\N_{\text{少なくとも2}}=S_2-2T,\qquad N_{\text{どれにも入らない}}=n(U)-(S_1-S_2+T). \end{gathered}

最初の名簿では S₁＝11、S₂＝5、T＝1。ちょうど二つは5−3＝2人で{3,6}、ちょうど一つは11−10＋3＝4人で{1,2,5,7}です。三つすべての{4}を加えると4＋2＋1＝7人になり、和集合と一致します。少なくとも二つは{3,4,6}の3人、どれにも入らないのは{8}の1人です。

公式を忘れたら、三つすべてに入る番号4を一つ追跡しましょう。「ちょうど二つ」なら最後に0回、「少なくとも二つ」なら1回にしたい。この目標から引く係数を復元できます。

4. 例題：倍数の共通部分は最小公倍数で作る

2の倍数かつ3の倍数は、両方で割り切れる整数、つまり6の倍数です。一般に共通部分は最小公倍数の倍数になります。たとえば4と6なら12の倍数であって24の倍数ではありません。また1以上N以下にある正のdの倍数は、d, 2d, … と並べて ⌊N/d⌋ 個です。⌊x⌋ はx以下の最大の整数を表します。

例題1：1から60までの「2、3、5のどれかの倍数」

1以上60以下の整数のうち、2、3、5の少なくとも一つで割り切れるもの、どれでも割り切れないもの、ちょうど二つで割り切れるものは、それぞれ何個か。

解答・解説

A、B、Cを順に2、3、5の倍数の集合とする。単独の個数は30、20、12。二つの共通部分は6、10、15の倍数なので10、6、4個。三つの共通部分は30の倍数で{30,60}の2個。少なくとも一つは30＋20＋12−10−6−4＋2＝44個。どれでも割り切れないものは60−44＝16個。ちょうど二つは10＋6＋4−3×2＝14個。

例題1の「ちょうど二つ」を別に数えると、6の倍数から30の倍数を除いたものが8個、10の倍数から30の倍数を除いたものが4個、15の倍数から30の倍数を除いたものが2個です。この三群は重ならないので8＋4＋2＝14個。ちょうど一つは62−2×20＋3×2＝28個で、28＋14＋2＝44個とも確かめられます。

5. 例題：「全部使う」は「何かが欠ける」の反対

三種類の文字を全部使う並べ方を直接作ろうとすると、どの文字を何回使うかで場合分けが増えます。使わない文字を指定すれば、その文字を候補から外すだけです。そこで「0を使わない」「1を使わない」「2を使わない」を悪い条件の集合として数え、それらの和集合を全体から引きます。

例題2：0、1、2をすべて使う4文字の列

各位置に0、1、2のいずれかを書く4文字の列を作る。同じ数字は何度使ってもよく、先頭が0でもよい。三種類を少なくとも一度ずつ使う列は何通りか。位置の異なる列は別と数える。

解答・解説

全体は3⁴＝81通り。A、B、Cを順に0、1、2を使わない列とすると、各集合は2⁴＝16通り。二つの数字を使わない共通部分は、残る数字だけの列が1通りずつ。三つとも使わない列は、長さが4なので存在せず0通り。悪い列は3×16−3×1＋0＝45通り。求める数は81−45＝36通り。別解では、三種類すべて使うと使用回数は2,1,1になる。二度使う数字が3通り、その位置が6通り、残り二数字の配置が2通りで3×6×2＝36通り。

6. 条件が増えたら「全体」と「悪い集合」を一緒に絞る

例題2に「先頭は0でない」を加えると、全体の81通りだけを54通りへ直しても解けません。先頭0の列は悪い集合の中にも混ざっていたからです。追加条件を満たす集合をDとしたら、数える舞台をDへ移し、AもA∩Dへ、二つの共通部分もA∩B∩Dへ置き換えます。これは条件を満たす個数の話であり、確率を求める必要はありません。

\begin{aligned}n\bigl(D\cap(A\cup B\cup C)\bigr)={}&n(D\cap A)+n(D\cap B)+n(D\cap C)\\&-n(D\cap A\cap B)-n(D\cap A\cap C)-n(D\cap B\cap C)\\&+n(D\cap A\cap B\cap C).\end{aligned}

例題3：先頭0を禁止した4桁の整数

0、1、2だけを用いる4桁の正の整数で、三種類の数字をすべて使うものは何個か。同じ数字の繰り返しは許す。

解答・解説

Dを先頭0でない列とすると全体は2×3³＝54通り。D内で0を使わない列は2⁴＝16通り。1を使わない列は先頭が2に決まり、残り三位置は0か2なので8通り。2を使わない列も8通り。0と1を使わない列は2222、0と2を使わない列は1111で各1通り。1と2を使わない列は0000しか候補がなくD内では0通り。三つとも使わない列も0通り。したがって54−(16＋8＋8−1−1−0＋0)＝24個。

「使わない数字が一つなら必ず16通り」と流用しないでください。先頭0を禁止すると、0を使わない条件と1を使わない条件は対称ではありません。また、文字列なら0120も数えますが、4桁の整数なら先頭0は許されません。数える対象の定義が先です。

全体集合を決める。範囲の端を含むか、先頭0や繰り返しを許すかも書く。
条件を集合に直す。「少なくとも一つ」か、その反対を数えると楽かを選ぶ。
単独・二つの共通部分・三つの共通部分を同じ全体の中で数える。
一要素の重複度で符号を確認し、答えが0以上で全体の個数以下か確かめる。可能なら別の列挙や場合分けと照合する。

練習：何を一回残したいか

1以上30以下の整数について、2、3、5の少なくとも一つで割り切れるもの、どれでも割り切れないもの、ちょうど二つで割り切れるものを数えよ。
ヒント
三つすべてで割り切れる整数は30だけ。
解答・解説
単独は15、10、6個、二つの共通部分は5、3、2個、三つの共通部分は1個。少なくとも一つは31−10＋1＝22個、どれでも割り切れないものは30−22＝8個。ちょうど二つは10−3＝7個で、列挙すると{6,10,12,15,18,20,24}。30は除く。
0、1、2から作る3文字の列で、三種類をすべて使うものは何通りか。先頭0と繰り返しを許す条件から出発し、包除原理で求めよ。
ヒント
何かが欠ける列の数を27から引く。
解答・解説
全体は3³＝27通り。悪い集合は各2³＝8通り、二つの共通部分は各1通り、三つの共通部分は0通り。27−(24−3)＝6通り。実際に012、021、102、120、201、210の6列である。
1以上60以下の奇数のうち、3または5で割り切れるものは何個か。
ヒント
奇数という条件を満たす全体D内で、3の倍数、5の倍数、15の倍数を数える。
解答・解説
Dは30個の奇数。奇数の3の倍数は3,9,…,57の10個、奇数の5の倍数は5,15,…,55の6個。共通部分は15と45の2個だから10＋6−2＝14個。元の全体での個数20＋12−4＝28をそのまま答えると、偶数も数えてしまう。

確認クイズ：重複の回数を判断する

問1. 三集合すべてに入る要素は、単独の個数を足し、二集合の共通部分をすべて引いた時点で何回分残っているか。

問2. 二集合の共通部分の個数の合計が7、三集合すべての共通部分が1個のとき、ちょうど二集合に入る要素は何個か。

問3. 0、1、2を用いる4桁の整数で「1を使わない」ものは何個か。数字の繰り返しは許す。

まとめ：包除原理は、記号の順番を暗記する公式というより「一つの対象が最後に何回数えられるか」を整える方法です。図がなくても、小さな集合を並べれば足し過ぎと引き過ぎが見えます。追加条件があれば全体も共通部分も一緒に絞り、最後は列挙や別の数え方で照合しましょう。

📝 メモこの端末のみに保存

メモ欄はページ読み込み後に使えるようになります。