A と集合B の和集合を白以外のすべてとして示すベン図 組み合わせ論 において、包含排除原理 （一般にPIEと呼ばれる）は、 2つの有限集合の 和集合 の要素数を求めるおなじみの方法を一般化した計数手法であり、記号的に次のように表される。
| A ∪ B | = | A | + | B | − | A ∩ B | {\displaystyle |A\cup B|=|A|+|B|-|A\cap B|} ここで、A とB は2つの有限集合であり、| S |は集合Sの 濃度 （集合が有限 であれば、集合の要素数と考えることができる）を表します。この式は、一部の要素が二重にカウントされる可能性があるため、2つの集合のサイズの合計が大きくなりすぎる可能性があることを示しています。二重にカウントされる要素は、2つの集合の共通部分 に含まれる要素であり、共通部分のサイズを差し引くことでカウントが修正されます。
包含排除原理は、2つの集合の場合の一般化であり、3つの集合の場合に、おそらくより明確に理解できる。集合A 、B 、C の場合、それは次のように与えられる。
| A ∪ B ∪ C | = | A | + | B | + | C | − | A ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | {\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|} この公式は、ベン図 の各領域が公式の右辺に何回含まれているかを数えることで検証できます。この場合、重複して数えられた要素の寄与を除外すると、3つの集合の共通部分の要素数が過剰に減算されてしまうため、正しい合計値を得るには、その数を再度加算する必要があります。
3つの集合のベン図で示される包含排除の原理 これらの例の結果を一般化すると、包含排除の原理が得られます。n個の集合の和集合の濃度を求めるには、次の方法を用います 。
集合の濃度を含めてください。 ペアごとの交差の要素数を除外します。 三者間交差の要素数を含めてください。 4つ組の交差部分の要素数を除外します。 5つ組ごとの交差の要素数を含めてください。 n タプルごとの共通部分の要素数が、 n が奇数の場合は含まれるか、n が 偶数の場合は含まれないかになるまで続けます。この名前は、原理が過剰な包含 に基づいており、それに続いて補償的な排除が行わ れるという考えに由来しています。この概念はアブラハム・ド・モアブル （1718年）[ 1 ] に帰属されますが、最初に登場したのはダニエル・ダ・シルバ （1854年）[ 2 ] JJシルベスター（1883年） [ 3 ] 数論 で広く使用されている篩法 の例と見なすことができ、篩公式 と呼ばれることもあります。[ 4 ]
有限確率は確率空間 の濃度に対する相対的な数として計算されるため、集合の濃度を有限確率に置き換えた場合でも、包含排除原理の公式は有効です。より一般的には、この原理のどちらのバージョンも、測度論 という共通の枠組みの下に位置づけることができます。
非常に抽象的な設定では、包含排除の原理は、ある行列の逆行列の計算として表現できます。[ 5 ] ジャン＝カルロ・ロータが 述べたように：
離散確率論および組合せ論における列挙の最も有用な原理の一つは、有名な包含排除原理である。この原理を巧みに適用すれば、多くの組合せ論的問題の解決が可能となる。
包含排除の原理の一般式は、有限集合A 1 , ..., A n
包含排除法則の各項は、最終的にベン図 の各部分が正確に一度だけ数えられるまで、徐々にカウントを修正していく。 これは次のように簡潔に記述できます。
| ⋃ 私 = 1 n A 私 | = ∑ k = 1 n （ − 1 ） k + 1 （ ∑ 1 ⩽ 私 1 < ⋯ < 私 k ⩽ n | A 私 1 ∩ ⋯ ∩ A 私 k | ） {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)} または
| ⋃ 私 = 1 n A 私 | = ∑ ∅ ≠ J ⊆ { 1 、 … 、 n } （ − 1 ） | J | + 1 | ⋂ j ∈ J A j | 。 {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|.} 言葉で説明すると、有限集合の有限和集合の要素数を数えるには、まず個々の集合の濃度を合計し、次に少なくとも2つの集合に含まれる要素数を減算し、次に少なくとも3つの集合に含まれる要素数を加算し、次に少なくとも4つの集合に含まれる要素数を減算する、というように繰り返します。和集合に含まれる集合の数よりも多くの集合に含まれる要素は存在しないため、このプロセスは常に終了します。（例えば、n = 4 、 {\displaystyle n=4,} 4 {\displaystyle 4} 5 {\displaystyle 5}
応用においては、この原理が相補的な形で表現されるのが一般的である。すなわち、S を すべてのA i 普遍集合 とし、A 私 ¯ {\displaystyle {\bar {A_{i}}}} S におけるA i ド・モルガンの法則 により、
| ⋂ 私 = 1 n A 私 ¯ | = | S − ⋃ 私 = 1 n A 私 | = | S | − ∑ 私 = 1 n | A 私 | + ∑ 1 ⩽ 私 < j ⩽ n | A 私 ∩ A j | − ⋯ + （ − 1 ） n | A 1 ∩ ⋯ ∩ A n | 。 \displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.} この記述の別の変形として、集合S の要素が持つ可能性のある、または持たない可能性のある特性のリストをP 1 、 ...、P n S の要素の数を計算する方法を提供する。特性P i を持つS の要素の部分集合をA i とし、その補完的な形式で原理を使用する。この変形はJJ Sylvester によるものである。[ 1 ]
原理の一般形において、右側の最初のm<n の m m
例
乱数の数え方 より複雑な例を挙げると次のようになります。
1からn までの番号が振られたn枚 のカードの山があるとします。番号m のカードが正しい位置にあるとは、そのカードが山札のm 番目の か？
まず、 m 番目の A m を定義します。すると、少なくとも 1 枚のカードが正しい位置m にある並び順の数W は次のようになります。
W = | ⋃ m = 1 n A m | 。 {\displaystyle W=\left|\bigcup _{m=1}^{n}A_{m}\right|.} 包含排除の原理を適用し、
W = ∑ m 1 = 1 n | A m 1 | − ∑ 1 ⩽ m 1 < m 2 ⩽ n | A m 1 ∩ A m 2 | + ⋯ + （ − 1 ） p − 1 ∑ 1 ⩽ m 1 < ⋯ < m p ⩽ n | A m 1 ∩ ⋯ ∩ A m p | + ⋯ {\displaystyle W=\sum _{m_{1}=1}^{n}|A_{m_{1}}|-\sum _{1\leqslant m_{1}<m_{2}\leqslant n}|A_{m_{1}}\cap A_{m_{2}}|+\cdots +(-1)^{p-1}\sum _{1\leqslant m_{1}<\cdots <m_{p}\leqslant n}|A_{m_{1}}\cap \cdots \cap A_{m_{p}}|+\cdots } 各値A m 1 ∩ ⋯ ∩ A m p \displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}} p 個 の値m 1 , ..., m p p 個の値が正しいシャッフルの数は p のみに依存し、 の特定の値には依存しないことに注意してください。 m {\displaystyle m} n枚の カードのうち3枚が正しい位置にあることです。したがって、（ n p ） {\textstyle {n \choose p}} p番目の 総和における等しい項（組み合わせを 参照）。
W = （ n 1 ） | A 1 | − （ n 2 ） | A 1 ∩ A 2 | + ⋯ + （ − 1 ） p − 1 （ n p ） | A 1 ∩ ⋯ ∩ A p | + ⋯ {\displaystyle W={n \choose 1}|A_{1}|-{n \choose 2}|A_{1}\cap A_{2}|+\cdots +(-1)^{p-1}{n \choose p}|A_{1}\cap \cdots \cap A_{p}|+\cdots } | A 1 ∩ ⋯ ∩ A p | {\displaystyle |A_{1}\cap \cdots \cap A_{p}|} これは、 p 個の要素が正しい位置にある順序の数であり、残りのn - p 個の要素を順序付ける方法の数、つまり( n - p )!に等しい。したがって、最終的に次の式が得られる。
W = （ n 1 ） （ n − 1 ） ! − （ n 2 ） （ n − 2 ） ! + ⋯ + （ − 1 ） p − 1 （ n p ） （ n − p ） ! + ⋯ = ∑ p = 1 n （ − 1 ） p − 1 （ n p ） （ n − p ） ! = ∑ p = 1 n （ − 1 ） p − 1 n ! p ! （ n − p ） ! （ n − p ） ! = ∑ p = 1 n （ − 1 ） p − 1 n ! p ! {\displaystyle {\begin{aligned}W&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+\cdots +(-1)^{p-1}{n \choose p}(n-p)!+\cdots \\&=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!(n-p)!}}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!}}\end{aligned}}} どの カードも正しい位置にない順列を、デレンジメント（順列の乱数） と呼びます。順列の総数をn ! とすると、ランダムなシャッフルによってデレンジメントが生じる確率Qは次のように表されます。
Q = 1 − W n ! = ∑ p = 0 n （ − 1 ） p p ! 、 {\displaystyle Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},} e −1 のテイラー展開を n + 1 項で切り捨てたものです。したがって、シャッフルされたトランプの順番を推測して、すべてのカードについて間違っている確率は、およそe −1 、つまり 37% です。
特別なケース 上記の順序の乱れの例に現れる状況は、特別な注意を払うに値するほど頻繁に発生します。[ 7 ]
A J := ⋂ j ∈ J A j {\displaystyle A_{J}:=\bigcap _{j\in J}A_{j}} {1, ..., n } の任意のk 要素部分集合J に対して、同じ濃度、例えばα k = | A J | を持つとすると、
| ⋃ 私 = 1 n A 私 | = ∑ k = 1 n （ − 1 ） k − 1 （ n k ） α k 。 {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.} あるいは、補完的な形式では、普遍集合S の 濃度はα 0 であり、
| S ∖ ⋃ 私 = 1 n A 私 | = α 0 − ∑ k = 1 n （ − 1 ） k − 1 （ n k ） α k = ∑ k = 0 n （ − 1 ） k （ n k ） α k 。 {\displaystyle {\begin{aligned}\left|S\smallsetminus \bigcup _{i=1}^{n}A_{i}\right|&=\alpha _{0}-\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}\\&=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\alpha _{k}.\end{aligned}}}
全体集合Sの部分集合 A 1 , A 2 , ..., A n の族 (重複可) が与えられたとき、包含排除原理は、これらの部分集合のいずれにも含まれないSの要素の数を計算します。この概念を一般化すると、これらの集合のうち、ちょうどある固定された m 個 の集合に含まれるS の要素の数を計算することになります。
N = [ n ] = {1,2,..., n }とします。A ∅ = S {\displaystyle A_{\emptyset }=S} A i の いずれにも含まれないものの数は次のとおりです。
∑ J ⊆ [ n ] （ − 1 ） | J | | A J | 。 {\displaystyle \sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.} I が インデックス集合 N の固定部分集合である場合、 I 内のすべてのiに対して A i に属し、他の値には属さない要素の数は次のとおりです。 [ 8 ]
∑ J ⊇ 私 （ − 1 ） | J | − | 私 | | A J | 。 {\displaystyle \sum _{J\supseteq I}(-1)^{|J|-|I|}|A_{J}|.} 集合を定義する
B k = A 私 ∪ { k } のために k ∈ N ∖ 私 。 {\displaystyle B_{k}=A_{I\cup \{k\}}{\text{ for }}k\in N\smallsetminus I.} 包含排除の原理により、B k のどの要素にも含まれない要素の数を求めます。B ∅ = A 私 {\displaystyle B_{\emptyset }=A_{I}}
∑ K ⊆ N ∖ 私 （ − 1 ） | K | | B K | 。 {\displaystyle \sum _{K\subseteq N\smallsetminus I}(-1)^{|K|}|B_{K}|.} N \ I の部分集合とI を含むN の部分集合との間の対応K ↔ J = I ∪ K は全単射であり、この写像の下でJ とKが対応する場合、 B K = A J となり 、結果が妥当であることが示されます。
確率論では 確率論 では、確率空間 における事象A 1 , ..., A nについて （ Ω 、 F 、 P ） {\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )} n = 2の場合、包含排除原理は次のようになる。
P （ A 1 ∪ A 2 ） = P （ A 1 ） + P （ A 2 ） − P （ A 1 ∩ A 2 ） 、 {\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),} n = 3 の場合
P （ A 1 ∪ A 2 ∪ A 3 ） = P （ A 1 ） + P （ A 2 ） + P （ A 3 ） − P （ A 1 ∩ A 2 ） − P （ A 1 ∩ A 3 ） − P （ A 2 ∩ A 3 ） + P （ A 1 ∩ A 2 ∩ A 3 ） {\displaystyle \mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})} そして一般的に
P （ ⋃ 私 = 1 n A 私 ） = ∑ 私 = 1 n P （ A 私 ） − ∑ 私 < j P （ A 私 ∩ A j ） + ∑ 私 < j < k P （ A 私 ∩ A j ∩ A k ） + ⋯ + （ − 1 ） n − 1 P （ ⋂ 私 = 1 n A 私 ） 、 {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})+\cdots +(-1)^{n-1}\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}\right),} これは閉じた形で次のように書くことができる。
P （ ⋃ 私 = 1 n A 私 ） = ∑ k = 1 n （ （ − 1 ） k − 1 ∑ 私 ⊆ { 1 、 … 、 n } | 私 | = k P （ A 私 ） ） 、 {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{I\subseteq \{1,\ldots ,n\} \atop |I|=k}\mathbb {P} (A_{I})\right),} ここで、最後の合計は、ちょうどk 個の要素を含むインデックス 1、...、nのすべての部分集合 Iにわたって実行され、
A 私 := ⋂ 私 ∈ 私 A 私 {\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}} は、 I のインデックスを持つすべてのA i の共通部分を表します。
ボンフェローニの不等式 によれば、式の最初の項の合計は、左辺 の上限と下限を交互に表します。これは、完全な式が煩雑すぎる場合に利用できます。
一般測度空間 ( S ,Σ, μ ) および有限測度 の可測 部分集合A 1 , ..., A n P {\displaystyle \mathbb {P} } μ に置き換えられます。
特別なケース 包含排除原理の確率的バージョンにおいて、共通部分A I の確率はI の濃度のみに依存する、つまり{1, ..., n } のすべての k に対して、次のようなa k
1 k = P （ A 私 ） すべての 私 ⊂ { 1 、 … 、 n } と | 私 | = k 、 {\displaystyle a_{k}=\mathbb {P} (A_{I}){\text{ for every }}I\subset \{1,\ldots ,n\}{\text{ with }}|I|=k,} すると上記の式は次のように簡略化されます。
P （ ⋃ 私 = 1 n A 私 ） = ∑ k = 1 n （ − 1 ） k − 1 （ n k ） 1 k {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}} 二項係数 の組み合わせ論的解釈により（ n k ） {\textstyle {\binom {n}{k}}} A 私 {\displaystyle A_{i}} 独立かつ同一の分布に 従うならば、P （ A 私 ） = p {\displaystyle \mathbb {P} (A_{i})=p} すべてのi に対して、そして、1 k = p k {\displaystyle a_{k}=p^{k}}
P （ ⋃ 私 = 1 n A 私 ） = 1 − （ 1 − p ） n 。 {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=1-(1-p)^{n}.} （この結果は、事象の補集合の共通部分を考慮することによって、より簡単に導き出すこともできます。）A 私 {\displaystyle A_{i}}
同様の簡略化は、一般的な測度空間の場合にも可能である。（ S 、 Σ 、 μ ） {\displaystyle (S,\Sigma ,\mu )} A 1 、 … 、 A n {\displaystyle A_{1},\dots ,A_{n}}
点過程 で使用される別の公式があります。S {\displaystyle S} P {\displaystyle P} S {\displaystyle S} A {\displaystyle A} S {\displaystyle S}
P （ P = A ） = P （ P ⊃ A ） − ∑ j 1 ∈ S ∖ A P （ P ⊃ A ∪ j 1 ） + ∑ j 1 、 j 2 ∈ S ∖ A j 1 ≠ j 2 P （ P ⊃ A ∪ j 1 、 j 2 ） + … + （ − 1 ） | S | − | A | P （ P ⊃ S ） = ∑ A ⊂ J ⊂ S （ − 1 ） | J | − | A | P （ P ⊃ J ） 。 {\displaystyle {\begin{aligned}\mathbb {P} (P=A)&=\mathbb {P} (P\supset A)-\sum _{j_{1}\in S\setminus A}\mathbb {P} (P\supset A\cup {j_{1}})\\&+\sum _{j_{1},j_{2}\in S\setminus A\ j_{1}\neq j_{2}}\mathbb {P} (P\supset A\cup {j_{1},j_{2}})+\dots \\&+(-1)^{|S|-|A|}\mathbb {P} (P\supset S)\\&=\sum _{A\subset J\subset S}(-1)^{|J|-|A|}\mathbb {P} (P\supset J).\end{aligned}}}
この原理は、次のような形式で表現されることがある[ 9 ] 。
g （ A ） = ∑ S ⊆ A f （ S ） {\displaystyle g(A)=\sum _{S\subseteq A}f(S)} それから
包含排除原理の組み合わせ論的バージョンと確率論的バージョンは、（2
数字を見たらn {\displaystyle n} 2 ）は平方因子を持たない 自然数 に対するメビウス反転公式 の一般化である。したがって、（2 ）はA のすべての部分集合の半順序集合 のインカデンス代数 に対するメビウス反転公式とみなされる。
メビウス反転公式の完全版を一般化するには、（2 ）を多重集合 に一般化する必要がある。集合の代わりに多重集合の場合、（2
どこA − S {\displaystyle A-S} （ A − S ） ⊎ S = A {\displaystyle (A-S)\uplus S=A}
μ ( S ) = 1 は、Sが 偶数 濃度 の集合 (つまり、重複要素のない多重集合) である場合です。S が奇数要素の集合 (つまり重複要素のない多重集合) である場合、 μ ( S ) = −1 となります。S が真の多重集合 (つまり、S は二重要素を持つ)である場合、 μ ( S ) = 0 となります。注目してくださいμ （ A − S ） {\displaystyle \mu (A-S)} （ − 1 ） | A | − | S | {\displaystyle (-1)^{|A|-|S|}} ２ A − S {\displaystyle A-S}
アプリケーション 包含排除原理は広く用いられており、ここではその応用例のごく一部しか挙げることができない。
乱数の数え方 包含排除原理のよく知られた応用例として、有限集合のすべての順列 を数える組み合わせ論の問題があります。集合Aの 順列 とは、AからA自身への固定点を持たない 全単射の ことです。包含排除原理を用いると、 Aの濃度が n の場合、順列の数は [ n ! / e ] であることが示せます。ここで [ x ] はx に最も近い整数を表します。詳細な証明は ここに あり、上記の例のセクション も参照してください。
乱数の数を数える問題が最初に登場したのは、初期のギャンブルに関する書籍であるPR de Montmort (1678 – 1719) のEssai d'analyse sur les jeux de hazard であり、「Montmort の問題」または彼自身が付けた名前「problème des rencontres 」として知られていました。[ 10 ] 。
順列の数は、 n の階乗 とも呼ばれ、! nと表記されます。したがって、すべての全単射に同じ確率が割り当てられている場合、ランダムな全単射が順列である確率は、 n が 大きくなるにつれて急速に 1/ e に近づきます。
交差点の数を数える 包含排除の原理は、ド・モルガンの法則 と組み合わせることで、集合の共通部分の濃度を数えるためにも使用できる。A k ¯ {\displaystyle {\overline {A_{k}}}} ある普遍集合A に関するA k の補集合を表す。A k ⊆ A {\displaystyle A_{k}\subseteq A} k について。すると、
⋂ 私 = 1 n A 私 = ⋃ 私 = 1 n A 私 ¯ ¯ {\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A_{i}}}}}} それによって、交点を見つけるという問題が、和集合を見つけるという問題へと変化する。
オント関数の数 有限集合A とB が与えられたとき、Aから B への全射関数 (オント関数) はいくつありますか?一般性を失うことなく、集合の濃度のみが重要となるため、 A = {1, ..., k }、B = {1, ..., n }とすることができます。Sを A からB へのすべての関数 の集合として使用し、B の各i に対して、プロパティP i B の要素i を欠落している」（i は関数の像 に含まれていない）と定義すると、包含排除の原理により、 A とB の間のオント関数の数は次のように与えられます。[ 14 ]
∑ j = 0 n （ n j ） （ − 1 ） j （ n − j ） k 。 {\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}(-1)^{j}(n-j)^{k}.}
禁止位置を含む順列 集合S = {1, ..., n } の順列で、 S の各要素が特定の位置に存在しないように制限されているもの（ここでは順列はSの要素の順序付けとして考えられます）を 、禁止位置を持つ順列と 呼びます。例えば、S = {1,2,3,4} の場合、要素 1 が位置 1 または 3 に存在できず、要素 2 が位置 4 に存在できないという制約を持つ順列は、2134、2143、3124、4123、2341、2431、3241、3421、4231、4321 です。要素i が存在してはならない位置の集合をA i iを A i P i [ 15 ]
与えられた例では、性質P 1を持つ順列は 12 = 2(3!) 個、性質 P 2 を持つ順列は 6 = 3! 個あり、性質P 3 またはP 4 を持つ順列はありません。これは、これら 2 つの要素に対する制約がないためです。したがって、制約を満たす順列の数は次のようになります。
4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10。 この計算における最後の4は、性質P1 とP2 の 両方を持つ順列の数です。この式には、 他にゼロ以外の寄与はありません。
第二種スターリング数 第 2 種のスターリング数 S ( n , k ) は、n 個の要素の集合を k 個の空でない部分集合 (区別できないボックス) に分割する数を数えます。その 明示的な公式は、非常に密接に関連する問題、すなわち n 個の集合をk 個の空 でない が 区別 可能なボックス (順序付けられた 空でない部分集合)に分割する数を数える問題に包含排除の原理を適用することによって得られます。n個の集合を k 個 の(空である可能性のある) 区別可能なボックスA 1 、A 2 、 ...、A k A i が P i を k ! で割ると、第 2 種のスターリング数が得られます。[ 16 ]
S （ n 、 k ） = 1 k ! ∑ t = 0 k （ − 1 ） t （ k t ） （ k − t ） n 。 {\displaystyle S(n,k)={\frac {1}{k!}}\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}(k-t)^{n}.}
ルーク多項式 ルーク多項式と は、チェッカー盤 のマス目の部分集合のような盤面 B 上に、互いに攻撃しないルークを配置する方法の数を 表す母関数 です。つまり、2 つのルークが同じ行または列に配置されることはありません。盤面Bは、 n 行m 列の長方形の盤面のマス目の任意の部分集合です。これは、ルークを配置できるマス目と考えることができます。ルーク多項式 R B ( x ) におけるx k の r k ( B ) 、 互いに攻撃しないk個のルークを B のマス目に配置する方法の数を表します。任意の盤面B に対して、補完的な盤面が存在します。B ′ {\displaystyle B'} B に含まれない正方形から構成される。この補完的な盤面にもルーク多項式がある。R B ′ （ x ） {\displaystyle R_{B'}(x)} r k （ B ′ ） 。 {\displaystyle r_{k}(B').}
補盤のルーク多項式の係数を用いて、ルーク多項式の最高係数を計算できると便利な場合がある。一般性を失うことなく、n ≤ m と仮定できるので、この係数はr n ( B ) である。n 個の 攻撃しないルークを完全なn × m の「チェッカー盤」上に配置する方法の数(ルークが盤Bのマスに配置されているかどうかは考慮しない) は、 次の階乗 で与えられる。
（ m ） n = m （ m − 1 ） （ m − 2 ） ⋯ （ m − n + 1 ） 。 {\displaystyle (m)_{n}=m(m-1)(m-2)\cdots (m-n+1).} P i を、完全な盤面上のn 個 の非攻撃ルークの配置において、 i 列目のルークが盤面B のマス目にないという性質とすると、包含排除の原理により次のようになります。[ 17 ]
r n （ B ） = ∑ t = 0 n （ − 1 ） t （ m − t ） n − t r t （ B ′ ） 。 {\displaystyle r_{n}(B)=\sum _{t=0}^{n}(-1)^{t}(m-t)_{n-t}r_{t}(B').}
オイラーのトーシェント関数、またはファイ関数φ ( n ) は、 n 以下の正の整数のうち、 n と互いに素な整数の数を数える算術関数 です。つまり、n が 正の整数 である場合、φ( n ) は、1 ≤ k ≤ n の 範囲にある整数kのうち、 n と 1 以外の共通因数を持たない整数の数です。φ( n )の公式を得るために、包含排除の原理が用いられます。集合 を {1, ..., n } とし、 S の数が素数p i P i i ≤ r) 。ここで、p iは素因数分解です。
n = p 1 1 1 p 2 1 2 ⋯ p r 1 r 。 {\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}.} 次に、[ 18 ]
φ （ n ） = n − ∑ 私 = 1 r n p 私 + ∑ 1 ⩽ 私 < j ⩽ r n p 私 p j − ⋯ = n ∏ 私 = 1 r （ 1 − 1 p 私 ） 。 {\displaystyle \varphi (n)=n-\sum _{i=1}^{r}{\frac {n}{p_{i}}}+\sum _{1\leqslant i<j\leqslant r}{\frac {n}{p_{i}p_{j}}}-\cdots =n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right).}
原理が正確な公式を与えることができる場合（特に、エラトステネスの篩 を用いて素数を 数える場合）、得られる公式は項数が多すぎるため、有用な内容を提供しません。各項を個別に正確に推定できる場合、誤差の蓄積により、包含排除法則が直接適用できない可能性があります。数論において、この困難は ヴィゴ・ブルン によって取り上げられました。最初はゆっくりとしたペースでしたが、彼のアイデアは他の人々に受け入れられ、さまざまな篩法 が開発されました。これらの方法は、たとえば、正確な公式ではなく、「篩分けされた」集合の上限を見つけようとするものです。
A 1 、 ...、A n を p 1 、 ...、p n を 閉単位区間 [ 0, 1 ] n } 内の任意の偶数k に対して、指示関数は 次の不等式を満たす。[ 19 ]
1 A 1 ∪ ⋯ ∪ A n ≥ ∑ j = 1 k （ − 1 ） j − 1 ∑ 1 ≤ 私 1 < ⋯ < 私 j ≤ n p 私 1 … p 私 j 1 A 私 1 ∩ ⋯ ∩ A 私 j 。 {\displaystyle 1_{A_{1}\cup \cdots \cup A_{n}}\geq \sum _{j=1}^{k}(-1)^{j-1}\sum _{1\leq i_{1}<\cdots <i_{j}\leq n}p_{i_{1}}\dots p_{i_{j}}\,1_{A_{i_{1}}\cap \cdots \cap A_{i_{j}}}.}
主要声明の証明 すべての集合の和集合に含まれる要素を選択し、A 1 、 A 2 、 … 、 A t {\displaystyle A_{1},A_{2},\dots ,A_{t}} t > 0 であることに注意。）式（ 1 A 1 、 A 2 、 … 、 A t {\displaystyle A_{1},A_{2},\dots ,A_{t}}
| { A 私 ∣ 1 ⩽ 私 ⩽ t } | − | { A 私 ∩ A j ∣ 1 ⩽ 私 < j ⩽ t } | + ⋯ + （ − 1 ） t + 1 | { A 1 ∩ A 2 ∩ ⋯ ∩ A t } | = （ t 1 ） − （ t 2 ） + ⋯ + （ − 1 ） t + 1 （ t t ） 。 {\displaystyle {\begin{aligned}|\{A_{i}\mid 1\leqslant i\leqslant t\}|&-|\{A_{i}\cap A_{j}\mid 1\leqslant i<j\leqslant t\}|+\cdots +(-1)^{t+1}|\{A_{1}\cap A_{2}\cap \cdots \cap A_{t}\}|={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}}.\end{aligned}}} 二項定理 により、
0 = （ 1 − 1 ） t = （ t 0 ） − （ t 1 ） + （ t 2 ） − ⋯ + （ − 1 ） t （ t t ） 。 {\displaystyle 0=(1-1)^{t}={\binom {t}{0}}-{\binom {t}{1}}+{\binom {t}{2}}-\cdots +(-1)^{t}{\binom {t}{t}}.} 事実を利用して（ t 0 ） = 1 {\displaystyle {\binom {t}{0}}=1}
1 = （ t 1 ） − （ t 2 ） + ⋯ + （ − 1 ） t + 1 （ t t ） 、 {\displaystyle 1={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}},} したがって、選択された要素は式（ 1
代数的証明 代数的な証明は、指示関数 （特性関数とも呼ばれる）を用いて得ることができる。集合Xの部分集合 S の指示関数は、次の関数である。
1 S : X → { 0 、 1 } 1 S （ x ） = { 1 x ∈ S 0 x ∉ S {\displaystyle {\begin{aligned}&\mathbf {1} _{S}:X\to \{0,1\}\\&\mathbf {1} _{S}(x)={\begin{cases}1&x\in S\\0&x\notin S\end{cases}}\end{aligned}}} もしA {\displaystyle A} B {\displaystyle B} X {\displaystyle X}
1 A ⋅ 1 B = 1 A ∩ B 。 {\displaystyle \mathbf {1} _{A}\cdot \mathbf {1} _{B}=\mathbf {1} _{A\cap B}.} A を 和集合とします⋃ 私 = 1 n A 私 {\textstyle \bigcup _{i=1}^{n}A_{i}} A 1 、 ...、A n の。一般的に包含排除原理を証明するために、まず次の恒等式を検証します。
指標関数の場合、次のようになります。
A 私 = ⋂ 私 ∈ 私 A 私 。 {\displaystyle A_{I}=\bigcap _{i\in I}A_{i}.} 以下の関数
（ 1 A − 1 A 1 ） （ 1 A − 1 A 2 ） ⋯ （ 1 A − 1 A n ） = 0 、 {\displaystyle \left(\mathbf {1} _{A}-\mathbf {1} _{A_{1}}\right)\left(\mathbf {1} _{A}-\mathbf {1} _{A_{2}}\right)\cdots \left(\mathbf {1} _{A}-\mathbf {1} _{A_{n}}\right)=0,} は恒等的にゼロになります。なぜなら、x が A に含まれていない場合、すべての因子は 0−0 = 0 であり、そうでない場合、x が何らかの A m に属している場合は、対応するm 番目の 因子は 1−1=0 だからです。左辺の積を展開すると、式 ( 4
集合の濃度に関する包含排除原理を証明するには、A 1 , ..., A n xについて式 ( 4 4 ) の期待値 を取ります。一般に、式 ( 4 ) をμ に関して積分します 。これらの導出では常に線形性を使用します。
参考文献 Allenby, RBJT; Slomson, Alan (2010)、「How to Count: An Introduction to Combinatorics」 、Discrete Mathematics and Its Applications (第2 版)、CRC Press、pp. 51–60 、ISBN 9781420082609 Björklund, A.; Husfeldt, T.; Koivisto, M. (2009)、「包含排除による集合分割」、SIAM Journal on Computing 39 (2): 546–563 、CiteSeerX 10.1.1.526.9573 、doi : 10.1137/070683933 ブルアルディ、リチャード A. (2010)、『入門組合せ論』 （第 5 版）、プレンティス・ホール、ISBN 9780136020400 キャメロン、ピーター・J. (1994)『組み合わせ論：トピック、テクニック、アルゴリズム 』ケンブリッジ大学出版局、ISBN 0-521-45761-0 Fernández, Roberto; Fröhlich, Jürg ; Alan D., Sokal (1992), Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory , Texts an Monographs in Physics, Berlin: Springer-Verlag , pp. xviii+444, ISBN 3-540-54358-9 MR 1219313、Zbl 0761.60061 グラハム, ロータリー州 ;グレッチェル、M. ; Lovász, L. (1995)、Hand Book of Combinatorics (volume-2) 、MIT Press – 北オランダ、ISBN 9780262071710 Gross, Jonathan L. (2008), 『コンピュータ応用による組み合わせ手法』 、Chapman&Hall/CRC、ISBN 9781584887430 「包含排除原理」、数学百科事典 EMS Press 、2001年 [1994年] マズール、デイビッド・R. (2010)、『組み合わせ論入門』 、アメリカ数学協会、ISBN 9780883857625 ロバーツ、フレッド・S. 、テスマン、バリー（2009）、『応用組合せ論 （第2 版）』、CRC Press、ISBN 9781420099829 Rota、Gian-Carlo (1964)、「組み合わせ理論の基礎について I. メビウス関数の理論」、Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 、2 (4): 340–368 、doi : 10.1007/BF00531932 、S2CID 121334025 スタンレー、リチャード P. (1986)、『列挙的組み合わせ論 第 1 巻』 、ワズワース & ブルックス/コール、ISBN 0534065465 van Lint, JH ; Wilson, RM (1992), A Course in Combinatorics , Cambridge University Press, ISBN 0521422604 この記事は、 PlanetMath の包含排除原理からの資料を取り入れており、クリエイティブ・コモンズ表示-継承ライセンスの下でライセンスされています。
![{\displaystyle \sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbccfd27a154c270d8977aa13873938a3508e132)
