包除原理
おそらく、包除原理のもっともよく知られている応用は、組み合わせ問題における有限集合の攪乱(derangement)に対するものであろう。集合Aの攪乱とはAから自分自身への全単射であって不動点を持たないもののことである。包除原理によって、Aの基数(要素数)をnとしたときの攪乱の数が
[ n ! e ] {\displaystyle \left[{\frac {n!}{e}}\right]}
となることを示せる。ここで[x]はもっとも近い整数をあたえる関数(nearest integer function)を表す。
これはnのsubfactorialとしても知られ、 ! n {\displaystyle !n} と表す。 これはまた、全ての全単射に等しい確率が与えられた場合、無作為に選ばれた全単射が攪乱となっている確率がnの増加に従い、1/e に素早く近づくことを示している。
この原理によって理論的な公式を求める場合(特にエラトステネスの篩を用いる素数の数え上げ)、誤差評価が困難であるため有効な公式が得られないことが多い。これは、各項が個別には正確に求められてもそれらの相殺の様子を一般的に定式化することが難しい上に、和の項数が非常に多くなってしまうためである。数論において、ヴィーゴ・ブルンはこのような困難を部分的に克服する方法を見出し、これは現代的な篩の理論の端緒となった。ただし、この理論を用いてもたいてい、厳密な公式はもとより漸近公式さえ得られるのもまれで、したがってふるい落とされた集合の大きさの評価を与えるにとどまる。
包除原理(ほうじょげんり、英: Inclusion-exclusion principle, principle of inclusion and exclusion, Principle of inclusion-exclusion, PIE)あるいは包含と排除の原理とは、数え上げ組合せ論における基本的な結果のひとつ。特別な場合には「有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する元の数 |A ∩ B| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。
以上の2つの有限集合 A, B に対する包除原理は次のように表せる。
| A ∪ B | = | A | + | B | − | A ∩ B | {\displaystyle {\begin{aligned}\left|A\cup B\right|=&\left|A\right|+\left|B\right|-\left|A\cap B\right|\\\end{aligned}}}
同様に、3つの有限集合 A, B, C に対する包除原理は次のように表せる。