OMC対策（C分野：包除原理）

本記事の前提知識

　本記事では，集合 $S$ の要素の個数を絶対値記号 $| S |$ で表す．次の知識は前提とするため，知らなければこの先を読み進めるのは難しいと思う．　

2

つ，

3

つの集合についての包除原理

　有限集合 $A_{1}, A_{2}, A_{3}$ に対して
　　 $| A_{1} \cup A_{2} | = | A_{1} | + | A_{2} | - | A_{1} \cap A_{2} |$
　　 $| A_{1} \cup A_{2} \cup A_{3} | = | A_{1} | + | A_{2} | + | A_{3} | - | A_{1} \cap A_{2} | - | A_{2} \cap A_{3} | - | A_{3} \cap A_{1} | + | A_{1} \cap A_{2} \cap A_{3} |$

　参考までに，次のような問題が難なく解ければ本記事は読めると思う．

　 $60$ 以下の正整数で， $2$ または $3$ または $5$ で割り切れるものはいくつあるか．

（解答） $60$ 以下の正整数で， $2$ で割り切れるものの集合を $A$ ， $3$ で割り切れるものの集合を $B$ ， $5$ で割り切れるものの集合を $5$ とおく．求めるべきは $| A \cup B \cup C |$ である．
　 $| A | = 30, | B | = 20, | C | = 12, | A \cap B | = 10, | B \cap C | = 4, | C \cap A | = 6, | A \cap B \cap C | = 2$ なので， $| A \cup B \cup C | = 44$ 個である．

　次の公式も，練習問題等で使っている．

ド・モルガンの法則

　有限集合 $A_{1}, \dots, A_{n}$ に対して
　　 $\overset{―}{A_{1} \cup \dots \cup A_{n}} = \overset{―}{A_{1}} \cap \dots \cap \overset{―}{A_{n}}$
　　 $\overset{―}{A_{1} \cap \dots \cap A_{n}} = \overset{―}{A_{1}} \cup \dots \cup \overset{―}{A_{n}}$

　証明は省略する．

一般の包除原理

　高校の数学の教科書の多くには，公式1（集合が $2, 3$ 個の場合）が載っている．そこで「集合が $4$ つ以上だとどうなるのだろう」と考えるのは自然である．
　答えは，冒頭の公式1から十分推測できるものであり（つまり覚えやすい）， $| A_{1} \cap \dots \cap A_{k} |$ の集合の個数が奇数個であれば $+ 1$ ，偶数個であれば $- 1$ が係数となる．
　例えば $| A_{1} \cup A_{2} \cup A_{3} \cup A_{4} |$ であれば次のように書ける．
$\begin{aligned} | A_{1} \cup A_{2} \cup A_{3} \cup A_{4} | = & | A_{1} | + | A_{2} | + | A_{3} | + | A_{4} | \\ - | A_{1} \cap A_{2} | - | A_{1} \cap A_{3} | - | A_{1} \cap A_{4} | - | A_{2} \cap A_{3} | - | A_{2} \cap A_{4} | - | A_{3} \cap A_{4} | \\ + | A_{1} \cap A_{2} \cap A_{3} | + | A_{1} \cap A_{2} \cap A_{4} | + | A_{1} \cap A_{3} \cap A_{4} | + | A_{2} \cap A_{3} \cap A_{4} | \\ - | A_{1} \cap A_{2} \cap A_{3} \cap A_{4} | \end{aligned}$

$| A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup A_{5} |$ であれば次のようになる．
$\begin{aligned} | A_{1} \cup A_{2} \cup A_{3} \cup A_{4} \cup A_{5} | = & | A_{1} | + | A_{2} | + | A_{3} | + | A_{4} | + | A_{5} | \\ - | A_{1} \cap A_{2} | - \dots - | A_{4} \cap A_{5} | \\ + | A_{1} \cap A_{2} \cap A_{3} | + \dots + | A_{3} \cap A_{4} \cap A_{5} | \\ - | A_{1} \cap A_{2} \cap A_{3} \cap A_{4} | - \dots - | A_{2} \cap A_{3} \cap A_{4} \cap A_{5} | \\ + | A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5} | \end{aligned}$

　これをさらに一般化したものが，次の式である．

包除原理

　有限集合 $A_{1}, \dots, A_{n}$ に対して
　　 $| ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} ((- 1)^{k - 1} \sum_{k 個} | ⋂_{j} A_{j} |)$

　右辺がわかりづらいと思うので補足しておく． $(- 1)^{k - 1}$ の部分は，共通部分を取る集合の個数によって正負が入れかわることを表している． $\sum_{k 個} | ⋂_{j} A_{j} |$ は， $k$ 個の集合の共通部分全てについて（つまり $_{n} C_{k}$ 通りについて），その要素の個数を足していく．
　手始めに，全くありがたみのない例ではあるが，次の例を考えよう．

　集合 $A_{1} = \dots = A_{n} = {1}$ とすると，当然 $⋃_{i = 1}^{n} A_{i} = {1}$ であり， $| ⋃_{i = 1}^{n} A_{i} | = 1$ である．
　包除原理を適用して，こうなることを確かめよ．

解答

　任意の選び方に対して

| ⋂_{j} A_{j} | = 1

である（

j

が

0

個の場合は，包除原理では現れない）．
　よって

\sum_{k 個} | ⋂_{j} A_{j} | = \sum_{_{n} C_{k} 通り} 1 =_{n} C_{k}

であり，
　

\sum_{k = 1}^{n} ((- 1)^{k - 1} \sum_{k 個} | ⋂_{j} A_{j} |) = \sum_{k = 1}^{n} (- 1)^{k - 1}_{n} C_{k}

の値を求めればよい．二項定理を考えるとこの値は確かに

1

である．
　　

　もう少しまともな例として，次の問題を考えてみよ．オイラーの $ϕ$ 関数を知っていたとしても，包除原理を用いて考えてほしい．

　 $210$ 以下の正整数で， $2$ または $3$ または $5$ または $7$ で割り切れるものはいくつあるか．

解答

　次の式を参考にせよ．

\begin{aligned} | A_{1} \cup A_{2} \cup A_{3} \cup A_{4} | = & | A_{1} | + | A_{2} | + | A_{3} | + | A_{4} | \\ - | A_{1} \cap A_{2} | - | A_{1} \cap A_{3} | - | A_{1} \cap A_{4} | - | A_{2} \cap A_{3} | - | A_{2} \cap A_{4} | - | A_{3} \cap A_{4} | \\ + | A_{1} \cap A_{2} \cap A_{3} | + | A_{1} \cap A_{2} \cap A_{4} | + | A_{1} \cap A_{3} \cap A_{4} | + | A_{2} \cap A_{3} \cap A_{4} | \\ - | A_{1} \cap A_{2} \cap A_{3} \cap A_{4} | \end{aligned}

1

行目は

105 + 70 + 42 + 30

，

2

行目は

- 35 - 21 - 15 - 14 - 10 - 6

，

3

行目は

2 + 3 + 5 + 7

，

4

行目は

- 1

であり，合計は

162

個である．
　

　この問題3の一般化として，次の定理が得られる．

オイラーの

ϕ

関数

　 $n$ 以下で $n$ と互いに素な正整数の個数を $ϕ (n)$ で表す（これは一般的な記法である）．
　 $n$ を素因数分解すると $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ と表されるとき（ただし $e_{k} \neq 0$ ），
　　 $ϕ (n) = n (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{k}})$

証明の方針

　問題3を解く際に「

1

行目は

105 + 70 + 42 + 30

，

2

行目は

- 35 - 21 - 15 - 14 - 10 - 6

，

3

行目は

2 + 3 + 5 + 7

，

4

行目は

- 1

」と書いたが，これを次のように書き直してみよう．
　

1

行目は

210 \times (\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7})

，

2

行目は

- 210 \times (\frac{1}{6} + \frac{1}{10} + \frac{1}{14} + \frac{1}{15} + \frac{1}{21} + \frac{1}{35})

，

3

行目は

210 \times (\frac{1}{30} + \frac{1}{42} + \frac{1}{70} + \frac{1}{105})

，

4

行目は

- 210 \times \frac{1}{210}

　さて，

ϕ (210)

は，

210

から上の値を全て引いたものである．つまり
　

\begin{aligned} ϕ (210) = & 210 \times (1 \\ - \frac{1}{2} - \frac{1}{3} - \frac{1}{5} - \frac{1}{7} \\ + \frac{1}{6} + \frac{1}{10} + \frac{1}{14} + \frac{1}{15} + \frac{1}{21} + \frac{1}{35} \\ - \frac{1}{30} - \frac{1}{42} - \frac{1}{70} - \frac{1}{105} \\ + \frac{1}{210}) \\ = 210 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) (1 - \frac{1}{7}) \end{aligned}

　このように，オイラーの

ϕ

関数に相当するものが導かれる．
　以上の式変形を，文字を使って書き直せば，オイラーの

ϕ

関数の性質を証明できる（記述するのは面倒なので割愛する）．
　

包除原理を用いた具体例

　まずは，有名な具体例を $2$ つ挙げよう．
　どちらも，できれば証明を見る前に，包除原理を適用して確かめてみてほしい．

かく乱順列（完全順列）の個数

　 $1, 2, \dots, n$ の並べ替え $a_{1}, a_{2}, \dots a_{n}$ であって，任意の $k$ に対して $a_{k} \neq k$ であるようなものを，かく乱順列（または完全順列）と呼ぶ．
　そのような順列の個数は， $n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}$ である．

　なお，その値は $\frac{n!}{e}$ に最も近い整数値に一致する（この証明はマクローリン展開を使えばよい．本記事の主旨からは逸れるので省略する）．

証明のヒント

a_{i} = i

であるような並べ替えを全て含む集合を

A_{i}

とする．
　

| A_{i} |

は

a_{i} = i

を満たす順列の個数なので，

(n - 1)!

となる．
　

証明

a_{i} = i

であるような並べ替えを全て含む集合を

A_{i}

とする．
　包除原理の公式

| ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} ((- 1)^{k - 1} \sum_{k 個} | ⋂_{j} A_{j} |)

において，

| ⋂_{j} A_{j} | = (n - k)!

であり，

\sum_{k 個} | ⋂_{j} A_{j} | =_{n} C_{k} (n - k)! = \frac{n!}{k!}

となる．
　よって

| ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k - 1} \frac{n!}{k!}

であり，かく乱順列の個数は

n!

からこの値を引けばよい．
　

　包除原理を使う問題（証明）においては，この例のように，それぞれの $A_{i}$ が何なのかを明確にするとよい．
　もう一つ，次の命題も有名な例である．

全射の個数

　 $k ≦ n$ を満たす正整数に対して，次の条件を満たす数列を考える．

長さ $n$ の数列である
$a_{1}, \dots, a_{n}$ はいずれも $1$ 以上 $k$ 以下の正整数である
$1$ 以上 $k$ 以下のいずれの正整数も，数列の項の中に存在する．

　このような数列は $\sum_{i = 1}^{k} (- 1)^{k - i}_{k} C_{i} i^{n}$ 個存在する．

証明のヒント

　上の

2

つの条件を満たし，かつ，数列の項として

i

を含まないような数列の個数を

A_{i}

とする．
　

A_{i}

は，

i

を含まない以外に追加の条件がない（別の数

i^{'}

を含まなくてもよい）ため，

| A_{i} | = (k - 1)^{n}

である．
　

証明

　上の

2

つの条件を満たし，かつ，数列の項として

i

を含まないような数列の個数を

A_{i}

とする．
　包除原理の公式

| ⋃_{i = 1}^{k} A_{i} | = \sum_{i = 1}^{k} ((- 1)^{i - 1} \sum_{i 個} | ⋂_{j} A_{j} |)

において（添え字が微妙に異なることに注意せよ），

| ⋂_{j} A_{j} | = (k - i)^{n}

であり，

\sum_{i 個} | ⋂_{j} A_{j} | =_{k} C_{i} (k - i)^{n}

となる．
　よって

| ⋃_{i = 1}^{k} A_{i} | = \sum_{i = 1}^{k} (- 1)^{i - 1}_{k} C_{i} (k - i)^{n}

であり，全射の個数は

k^{n}

からこの値を引けばよい（

\sum

内部の

k - i

を

i

に置き換えよ）．
　

　以上の $2$ つの例は，非常に有名で，包除原理の解説をする際によく登場する例である．
　ここから $3$ 題，オリジナルの練習問題を用意した．いずれもOMCの難易度で $300$ 前後のものだろう．計算がやや面倒なので，立式までで答え合わせをしてもよい．

　 $20$ 以下の正整数から $10$ 個の正整数を選ぶ方法で，次の条件を満たすものは何通りあるか．
（条件） $5$ で割った余りが $0, 1, 2, 3, 4$ であるような数を，それぞれ $1$ つ以上含む．

（具体例） ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$ は条件を満たす． ${1, 2, 3, 4, 6, 7, 8, 9, 11, 12}$ は， $5$ で割った余りが $0$ のものを含まず，条件を満たさない．

ヒント

5

で割った余りが

i

であるような数を含まないような選び方を

A_{i}

とする．
　

解答

5

で割った余りが

i

であるような数を含まないような選び方を

A_{i}

とする．
　求めたいものは

| \overset{―}{A_{0}} \cap \dots \cap \overset{―}{A_{4}} | = | \overset{―}{A_{0} \cup \dots \cup A_{4}} |

である．

| A_{0} \cup \dots \cup A_{4} |

の値を求め，

_{20} C_{10}

から引けばよい．
　

| A_{i} | =_{16} C_{10}

，

| A_{i} \cap A_{j} | =_{12} C_{10}

なので，包除原理より
　　

| A_{0} \cup \dots \cup A_{4} | = 5 \times_{16} C_{10} - 10 \times_{12} C_{10}

である．従って求めるべき値は

_{20} C_{10} - 5 \times_{16} C_{10} + 10 \times_{12} C_{10} = 145376

通り．
　

　さいころを $9$ 個投げる．ちょうど $3$ 個出ているような目が存在する確率を求めよ．

（具体例） $9$ 個投げたときの出目が， $1, 1, 1, 2, 2, 3, 4, 5, 6$ や $1, 1, 1, 2, 2, 2, 3, 3, 3$ であれば条件を満たす． $1, 1, 2, 2, 3, 3, 4, 5, 6$ や $1, 1, 1, 1, 2, 2, 2, 2, 2$ であれば条件を満たさない．

ヒント

　目

i

がちょうど

3

個出ているような事象を

A_{i}

と置く．
　

解答

　目

i

がちょうど

3

個出ているような事象を

A_{i}

と置く．
　

P (A_{i}) =_{9} C_{3} {(\frac{1}{6})}^{3} {(\frac{5}{6})}^{6}

，

P (A_{i} \cap A_{j}) = \frac{9!}{3! 3! 3!} {(\frac{1}{6})}^{3} {(\frac{1}{6})}^{3} {(\frac{4}{6})}^{3}

，

P (A_{i} \cap A_{j} \cap A_{k}) = \frac{9!}{3! 3! 3!} {(\frac{1}{6})}^{3} {(\frac{1}{6})}^{3} {(\frac{1}{6})}^{3}

であり，求めるべき値は

\begin{aligned} _{6} C_{1} P (A_{i}) -_{6} C_{2} P (A_{i} \cap A_{j}) +_{6} C_{3} P (A_{i} \cap A_{j} \cap A_{k}) & = \frac{9!}{6^{9} (3!)^{3}} (6 \cdot \frac{1}{20} \cdot 5^{6} - 15 \cdot 4^{3} + 20) \\ = \frac{9!}{6^{12}} \cdot \frac{7495}{2} \\ = \frac{262325}{419904} \end{aligned}

　 $5 \times 5$ のマス目があり，各マスには白石，黒石のいずれか $1$ つが置かれている．次の条件を満たす石の置き方は何通りか．
（条件）どの行，どの列を見ても，黒石が $1$ つ以上置かれている．（白石については，置かれていなくてもよい．）

ヒント１

　行と列，両方の条件があるから厄介である．片方の条件（例えば行の条件）は満たしているものとして，列の条件に対して包除原理を適用しよう．
　

ヒント２

　行の条件は満たしているものとして，

i

列目に黒石が置かれていないような石の置き方を

A_{i}

とする．
　

解答

　行の条件は満たしているものとして，

i

列目に黒石が置かれていないような石の置き方を

A_{i}

とする．
　

| A_{i} | = 15^{5}

，

| A_{i} \cap A_{j} | = 7^{5}

，

| A_{i} \cap A_{j} \cap A_{k} | = 3^{5}

，

| A_{i} \cap A_{j} \cap A_{k} \cap A_{l} | = 1^{5}

なので，包除原理より求めるべき値は

31^{5} - 5 \times 15^{5} + 10 \times 7^{5} - 10 \times 3^{5} + 5 \times 1^{5} = 24997921

通り．
　

　最後にOMCの例題である．ここに挙げた他にもいくつかあるだろうから，見つけたら更新していく．

OMCの例題

OMC113(E)
OMC103(F)

投稿日：4月2日

更新日：4月2日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

て

779

他の人のコメント

コメントはありません。

読み込み中

て

OMC対策（C分野：包除原理）

本記事の前提知識
一般の包除原理
包除原理を用いた具体例