포함배제의 원리 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Inclusion-exclusion.svg|섬네일|집합이 세 개일 때의 포함배제의 원리를 [[벤 다이어그램]]으로 표현한 것]]
[[조합론]]에서 '''포함배제의 원리'''(包含排除의原理, {{llang|en|inclusion–exclusion principle}})는 [[유한 집합]]의 [[합집합]]의 원소 개수를 세는 기법이다. [[조합론]]에서 널리 쓰이는 근본적인 기법이며, 이에 대하여 조합론자 [[잔카를로 로타]]는 다음과 같이 평했다.
{{인용문2|유명한 포함배제의 원리는 이산 확률론과 조합론에서의 열거 문제에서 가장 유용한 기법 가운데 하나이다. 잘 적용하면, 이 원리를 사용하여 수많은 조합론적 문제를 해결할 수 있다.<br>
{{lang|en|One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem.}}|<ref>{{저널 인용|성=Rota|이름=Gian-Carlo |저자링크=잔카를로 로타|날짜=1964|제목=On the foundations of combinatorial theory I. Theory of Möbius functions|url=http://www.maths.ed.ac.uk/~aar/papers/rota1.pdf|저널=Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete|권=2|호=4|쪽= 340–368|doi=10.1007/BF00531932|zbl= 0121.02406|issn=0044-3719|언어=en}}</ref>}}

== 정의 ==
[[유한 측도 공간]] <math>(X,\mathcal A,\mu)</math>가 주어졌다고 하자. '''포함배제의 원리'''에 따르면, 임의의 유한 개의 [[가측 집합]] <math>A_1,\dots,A_n\in\mathcal A</math>에 대하여, 다음이 성립한다.
:<math>\mu(A_1\cup\cdots\cup A_n) = \sum_{i=1}^n\mu(A_i) - \sum_{1\le i<j\le n}\mu(A_i\cap A_j) + \sum_{1\le i<j<k\le n}\mu(A_i\cap A_j\cap A_k) - \cdots + (-1)^{n-1}\mu(A_1\cap\cdots\cap A_n)</math>
특히, 2개의 가측 집합 <math>A,B\in\mathcal A</math>에 대한 포함배제의 원리는 다음과 같다.
:<math>\mu(A\cup B)=\mu(A)+\mu(B)-\mu(A\cap B)</math>
또한, 3개의 집합 <math>A,B,C\in\mathcal A</math>에 대한 포함배제의 원리는 다음과 같다.
:<math>\mu(A\cup B\cup C)=\mu(A)+\mu(B)+\mu(C)-\mu(A\cap B)-\mu(A\cap C)-\mu(B\cap C)+\mu(A\cap B\cap C)</math>
포함배제의 원리는 [[근접 대수]]에서의 [[뫼비우스 반전 공식]]의 특수한 경우이다. 구체적으로, <math>n</math>개의 [[가측 집합]] <math>A_1,\dots,A_n\in\mathcal A</math>이 있을 때, <math>n</math>개의 원소의 집합 <math>\{1,2,\dots,n\}</math>의 [[멱집합]] <math>\mathcal P(\{1,2,\dots,n\})</math> (이는 포함 관계에 따라 [[부분 순서 집합]]을 이룬다) 위의 [[실수]] 계수 [[근접 대수]]를 생각한다면, 포함배제의 원리는 그 위의 [[뫼비우스 반전 공식]]의 한 예이다.

=== 집합의 원소 개수의 경우 ===
[[유한 집합]] <math>A</math>의 원소 개수는 <math>|A|</math>로 표기한다. '''포함배제의 원리'''에 따르면, 임의의 유한 개의 [[유한 집합]] <math>A_1,\dots,A_n</math>에 대하여, 다음이 성립한다.
:<math>|A_1\cup\cdots\cup A_n|=\sum_{i=1}^n|A_i|-\sum_{1\le i<j\le n}|A_i\cap A_j|+\sum_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n-1}|A_1\cap\cdots\cap A_n|</math>
특히, 2개의 집합 또는 3개의 집합의 경우는 각각 다음과 같다.
:<math>|A\cup B|=|A|+|B|-|A\cap B|</math>
:<math>|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|</math>

집합의 원소 개수는 어떤 [[유한 집합]] <math>X</math>의 [[멱집합]] <math>\mathcal P(X)</math>에 국한시켰을 때 [[유한 측도]]를 이루며, 이를 [[셈측도]]라고 한다. 집합의 원소 개수에 대한 포함배제의 원리는 [[셈측도 공간]] <math>(X,\mathcal P(X),||)</math> 위의 포함배제의 원리와 같다.

=== 확률의 경우 ===
[[확률 공간]]은 [[유한 측도 공간]]이므로, 포함배제의 원리는 유한 개의 사건들의 [[확률]]에 대해서도 성립한다. [[확률 공간]] <math>(\Omega,\mathcal F,\operatorname{Pr})</math>이 주어졌다고 하자. '''포함배제의 원리'''에 따르면, 임의의 유한 개의 사건 <math>A_1,\dots,A_n\in\mathcal F</math>에 대하여, 다음이 성립한다.
:<math>\operatorname{Pr}(A_1\cup\cdots A_n)=\sum_{i=1}^n\operatorname{Pr}(A_i)-\sum_{1\le i<j\le n}\operatorname{Pr}(A_i\cap A_j)+\sum_{1\le i<j<k\le n}\operatorname{Pr}(A_i\cap A_j\cap A_k)-\cdots+(-1)^{n-1}\operatorname{Pr}(A_1\cap\cdots A_n)</math>
2개 또는 3개의 사건의 경우 다음과 같다.
:<math>\operatorname{Pr}(A\cap B)=\operatorname{Pr}(A)+\operatorname{Pr}(B)-\operatorname{Pr}(A\cap B)</math>
:<math>\operatorname{Pr}(A\cap B\cap C)=\operatorname{Pr}(A)+\operatorname{Pr}(B)+\operatorname{Pr}(C)-\operatorname{Pr}(A\cap B)-\operatorname{Pr}(A\cap C)-\operatorname{Pr}(B\cap C)+\operatorname{Pr}(A\cap B\cap C)</math>

== 따름정리 ==
=== 부등식 ===
[[확률 공간]] <math>(\Omega,\mathcal F,\operatorname{Pr})</math>이 주어졌다고 하자. 그렇다면, 임의의 두 사건 <math>A,B\in\mathcal F</math>에 대하여, 다음과 같은 부등식이 성립한다.
:<math>\operatorname{Pr}(A\cap B)\ge\operatorname{Pr}(A)+\operatorname{Pr}(B)-1</math>

== 예 ==
=== 완전 순열의 수 ===
{{본문|준계승}}
<math>n</math>개의 원소 <math>\{1,\dots,n\}</math>의 [[완전 순열]]의 개수를 구하는 문제를 생각해 보자. <math>\{1,\dots,n\}</math>의 [[완전 순열]]은 임의의 <math>i\in\{1,\dots,n\}</math>에 대하여, <math>\sigma(i)\ne i</math>인 [[순열]] <math>\sigma\in S_n</math>을 뜻한다. [[완전 순열]]의 집합을 <math>D_n</math>이라고 하고, 각 <math>i\in\{1,\dots,n\}</math>에 대하여,
:<math>A_i=\{\sigma\in S_n\colon \sigma(i)=i\}</math>
가 <math>i</math>의 위치를 변경하지 않는 [[순열]]들의 집합이라고 하자. 그렇다면, [[완전 순열]]의 정의에 따라 <math>D_n=S_n\setminus(A_1\cup\cdots\cup A_n)</math>이다. 서로 다른 <math>A_{i_1},\dots,A_{i_k}</math>의 [[교집합]]은 <math>i_1,\dots,i_k</math>를 제외한 <math>n-k</math>개의 원소들의 [[순열]]의 집합과 일대일 대응하므로,
:<math>|A_{i_1}\cap\cdots\cap A_{i_k}|=(n-k)!</math>
이다. 포함배제의 원리에 따라
:<math>|A_1\cup\cdots\cup A_n|=\sum_{k=1}^n\left((-1)^{k-1}\sum_{1\le i_1<\cdots<i_k\le n}|A_{i_1}\cap\cdots\cap A_{i_k}|\right)=\sum_{k=1}^n\binom nk(n-k)!=n!\sum_{k=1}^n\frac{(-1)^{k-1}}{k!}</math>
이다. 모든 순열의 개수는 <math>|S_n|=n!</math>이므로, 모든 완전 순열의 개수는
:<math>|D_n|=|S_n|-|A_1\cup\cdots\cup A_n|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}</math>
이다.

== 각주 ==
{{각주}}
* {{서적 인용
|성1=Athreya
|이름1=Krishna B.
|성2=Lahiri
|이름2=Soumendra N.
|제목=Measure Theory and Probability Theory
|언어=en
|총서=Springer Texts in Statistics
|출판사=Springer
|위치=New York, NY
|날짜=2006
|isbn=978-0-387-32903-1
|issn=1431-875X
|doi=10.1007/978-0-387-35434-7
|zbl=1125.60001
}}

== 외부 링크 ==
* {{eom|제목=Inclusion-and-exclusion principle}}
* {{매스월드|id=Inclusion-ExclusionPrinciple|제목=Inclusion-exclusion principle}}

[[분류:집합론]]
[[분류:열거조합론]]
[[분류:수학 정리]]