はじめに

包除原理を知っていますか？私は知っています

知ってはいますが, 全然使いこなせていないし使うたびに頭が壊れてしまって「答えが合ったので, ﾖｼ!!」と提出してしまうので, ちゃんと勉強しようと思いました

この記事はそのまとめです

本文

とりあえずググりましょう

一番上に wikipedia 先生が出てきたので開いてみると, このような式が乗っています

$\left\vert \displaystyle \bigcup _ {i =1} ^ n A _ i \right\vert = \displaystyle\sum _ {k=1} ^ n (-1) ^ {k - 1} \displaystyle\sum _ { \vert J \vert = k} \left\vert \displaystyle\bigcap _ {j \in J} A _ j \right\vert$

複雑そうに見えるかもしれませんが, 「積集合をいい感じに足し引きすると和集合になる」というだけです

証明はいつもお世話になっております高校数学の美しい物語さんを見るといいでしょう

この式を見ればわかる通り, これは積集合から和集合を求めています

つまり, ある集合 $S$ を決め打ったときに「少なくとも $S$ を含む場合」が簡単にわかるときに「少なくとも一つを含む場合」を求めようとしています

また, $A _ 1, A _ 2, ... , A _ n$ の上位集合を $X$ とすると

$X - \left\vert \displaystyle \bigcup _ {i =1} ^ n A _ i \right\vert = X - \displaystyle\sum _ {k=1} ^ n (-1) ^ {k - 1} \displaystyle\sum _ { \vert J \vert = k} \left\vert \displaystyle\bigcap _ {j \in J} A _ j \right\vert \ = \displaystyle\sum _ {k=0} ^ n (-1) ^ {k} \displaystyle\sum _ { \vert J \vert = k} \left\vert \displaystyle\bigcap _ {j \in J} A _ j \right\vert$

と書けます ( $0$ 個の積集合 = 上位集合全体と考えています)

これは元の式の余事象なので, 「一つも含まない場合」を意味します

ここまで集合の形で書きましたが, 競プロではだいたいこのままの形では出ません

競プロの問題文を要約すると, たいていの場合

いくつかの条件が与えられるこれらをすべて満たすようなものが何通りあるか求めよ

みたいな感じになります

このせいで, 「なんか包除するのかな～」という気持ちになっても「条件のうち, これとこれは満たすものを足し合わせて... ？」となって混乱してしまいます (僕だけですか？)

上に書いた通り, 包除原理で求めることができるのは和集合です

「すべて満たすようなもの」というのは積集合なのでこのままでは求められません

そのため, 逆に「条件を満たさないもの」を考えます

つまり,

いくつかの条件が与えられるこれらに一つも違反していないものは何通りあるか求めよ

という感じに言い換えるわけです

すると, この「これらに一つも違反していないもの」は「少なくともこれとこれは違反するような方法は何通りあるか」のようなものが求められれば包除原理で求められるわけです

おわりに

個人的に, この「条件を満たさないものを考える」というのがとても非直感的だなと感じてしまうため, いつも思考が妨げられていました

こうやってちゃんと考えて少しずつ慣れていけたらなと思います

参考文献

包除原理 - Wikipedia

包除原理の２通りの証明 | 高校数学の美しい物語

Suuさんのブログ

包除原理の基礎的な話

はじめに

本文

おわりに

参考文献