1. 개요
조합론에서 여러 개의 합집합의 크기를 구할 때 사용하는 공식이다. 이산수학 및 확률론에서 중요하고 유용한 원리 중 하나이다.
비교적 친숙한 [math(|A cup B| = |A| + |B| - |A cap B|)], [math(|A cup B cup C| = |A| + |B| + |C| - |A cap B| - |B cap C| - |C cap A| + |A cap B cap C|)] 등의 공식을 [math(n)]개짜리 합집합으로 일반화했다고 생각할 수 있다. 이름의 유래는 [math(A)], [math(B)], ……에 속하는 원소들을 포함시키고(더하고), 두 번 세어준 [math(A cap B)], ……의 원소들을 배제하고(빼고), 다시 [math(3)]개짜리 교집합이 빠졌으므로 더해주고, ……의 아이디어에서 나왔다.
비교적 친숙한 [math(|A cup B| = |A| + |B| - |A cap B|)], [math(|A cup B cup C| = |A| + |B| + |C| - |A cap B| - |B cap C| - |C cap A| + |A cap B cap C|)] 등의 공식을 [math(n)]개짜리 합집합으로 일반화했다고 생각할 수 있다. 이름의 유래는 [math(A)], [math(B)], ……에 속하는 원소들을 포함시키고(더하고), 두 번 세어준 [math(A cap B)], ……의 원소들을 배제하고(빼고), 다시 [math(3)]개짜리 교집합이 빠졌으므로 더해주고, ……의 아이디어에서 나왔다.
2. 진술
포함·배제의 원리(inclusion-exclusion principle)
유한집합인 전체집합 [math(U)]의 부분집합 [math(A_1,~A_2, cdotscdots,~A_n)]에 대해, 이들의 합집합의 원소의 개수는 다음과 같이 주어진다. [math(displaystyle left| bigcup_{i=1}^n A_i right| = sum_{emptyset ne I subset [n]} left( -1 right)^{|I|-1} left| bigcap_{i in I} A_i right| )]
여기서 [math([n] = {1,~2, cdotscdots,~n})]이고, [math(| cdot |)]은 집합의 크기(원소의 개수)이다. 이를 풀어쓰면 다음과 같다.
[math(|A_1 cup A_2 cup cdots cdots cup A_n| = (|A_1|+|A_2| + cdots cdots + |A_n|) - (|A_1 cap A_2| + cdots cdots + |A_{n-1} cap A_n|) + cdots cdots + left( -1 right)^{n-1}|A_1 cap A_2 cap cdots cdots cap A_n|)]
|
홀수 개의 교집합은 더하고, 짝수 개의 교집합을 뺀다는 식으로 기억하면 된다. 다음과 같은 여집합 형태도 많이 등장하는데 ([math(I=emptyset)]일 때는 전체집합을 더하는 것으로 간주) 이 경우에는 부호가 반대가 된다.
[math( displaystyle left| U setminus bigcup_{i=1}^n A_i right| = sum_{I subset [n]} left( -1 right)^{|I|} left| bigcap_{i in I} A_i right|)]
확률공간의 사건 [math(A_1,~A_2, cdots cdots,~A_n)]에 대해, 이들의 합집합의 확률은 다음과 같이 주어진다.
[math(displaystyle P left( bigcup_{i=1}^n A_i right) = sum_{emptyset ne I subset [n]} left( -1 right)^{|I|-1} P left( bigcap_{i in I} A_i right) )]
|
3. 증명
원소의 개수를 다룬 버전을 서술한다. 일반적인 확률 및 측도 버전은 비슷하게 접근하면 된다. (합 및 개수를 확률/측도로 바꾼다던지 등등)
전체집합 [math(U)]의 원소들은 [math(A_i)]에 속하냐, 속하지 않냐 두 가지의 기준으로 나눌 수 있다. 어떤 원소 [math(x in U)]가 [math(i=i_1,~i_2, cdots cdots,~i_k)]에 대해선 [math(x in A_i)]이고 나머지에 대해선 [math(x notin A_i)]라 하자. [math(J = { i_1, cdots cdots,~i_k })]라고 놓자. 이제 임의의 [math(I)]에 대해서 [math(displaystyle bigcap_{i in I} A_i)]가 [math(x)]를 포함할 필요충분조건은 [math(I subset J)]가 되고, 따라서 공식의 우변에서 [math(x)]가 세어지는 횟수는 [math(displaystyle sum_{emptyset ne I subset J} left( -1 right)^{|I|-1} )]가 된다. 만약 [math(J)]가 공집합이라면 그런 [math(I)]는 없으므로 횟수는 [math(0)]번이 된다. [math(J)]가 공집합이 아니라면 저 횟수는
전체집합 [math(U)]의 원소들은 [math(A_i)]에 속하냐, 속하지 않냐 두 가지의 기준으로 나눌 수 있다. 어떤 원소 [math(x in U)]가 [math(i=i_1,~i_2, cdots cdots,~i_k)]에 대해선 [math(x in A_i)]이고 나머지에 대해선 [math(x notin A_i)]라 하자. [math(J = { i_1, cdots cdots,~i_k })]라고 놓자. 이제 임의의 [math(I)]에 대해서 [math(displaystyle bigcap_{i in I} A_i)]가 [math(x)]를 포함할 필요충분조건은 [math(I subset J)]가 되고, 따라서 공식의 우변에서 [math(x)]가 세어지는 횟수는 [math(displaystyle sum_{emptyset ne I subset J} left( -1 right)^{|I|-1} )]가 된다. 만약 [math(J)]가 공집합이라면 그런 [math(I)]는 없으므로 횟수는 [math(0)]번이 된다. [math(J)]가 공집합이 아니라면 저 횟수는
[math(displaystyle sum_{emptyset ne I subset J} left( -1 right)^{|I|-1} =sum_{I subset J} left( -1 right)^{|I|-1} - left( -1 right)^{|emptyset|-1} =sum_{l=0}^k binom{k}{l} left( -1 right)^{l-1} +1 = 1)]
4. 예시 및 활용, 확장
교과과정에선 다음과 비슷한 문제로 이 원리가 등장하곤 한다.
ㅁㅁ초등학교 어느 한 반의 [math(40)]명 중 [math(25)]명은 리그 오브 레전드를, [math(18)]명은 오버워치를, [math(9)]명은 둘다 한다. 이 때 롤과 옵치를 둘다 안하는 사람의 수는?
|
두 합집합의 원소의 수가 [math((25+18)-9=34)]이므로 이 여집합이므로 답은 [math(6)]명이다. 간간히 집합이 3개인 경우도 나오는 듯하다.
조합론 중 특히 enumerative combinatorics 계열에선 집합의 개수가 [math(n)]개인 경우 각 잡고 제대로 쓴다면 꽤나 강력한 도구가 되는데, 예로 다음과 같은 문제들에 포함·배제의 원리를 적용할 수 있다.
조합론 중 특히 enumerative combinatorics 계열에선 집합의 개수가 [math(n)]개인 경우 각 잡고 제대로 쓴다면 꽤나 강력한 도구가 되는데, 예로 다음과 같은 문제들에 포함·배제의 원리를 적용할 수 있다.
- 교란순열, 즉 일대일대응 [math(sigma: [n] rightarrow [n])] 중 모든 [math(x)]에 대해 [math(sigma left( x right) neq x)]인 [math(sigma)]의 개수
- 제한된 순열 문제. 집합 [math(A subset[n] times [n])]이 주어졌을 때 [math((x,~sigma left( x right)) notin A)]인 순열의 개수. 위 교란순열 문제의 일반화이다.
- 전사함수 [math(f: [n] rightarrow [m])]의 개수. 제2종 스털링 수(Stirling numbers of the second kinds)와도 연관이 있다.
- 어떤 수 [math(n)]이 주어졌을 때 [math(1 le m le n)]인 정수 [math(m)] 중 [math(n)]과 서로소인 [math(m)]의 개수 (즉 오일러 정리에 나오는 오일러 파이 함수 [math(varphi left( n right))] 구하기)
- 변의 길이가 정수고 둘레가 [math(n)]인 삼각형의 개수(변의 순서가 다르면 다른 것으로 취급할 때).
일반적으로 여러 개의 제약조건이 복합적으로 작용할 때, 보통 이들의 교집합을 생각하는 건 쉽지만 합집합 및 여집합을 생각하는 건 어려울 때가 많은데, 이럴 때 이 포함 배제의 원리를 범용적으로 쓸 수 있다.
한편 확률론에선 다음 부등식 버전의 포함배제의 원리를 생각하기도 한다.
한편 확률론에선 다음 부등식 버전의 포함배제의 원리를 생각하기도 한다.
본페로니 부등식(Bonferroni inequality)
위의 포함·배제 공식을 [math(|I| le j)]인 범위까지만 더했을 때, [math(j)]가 홀수이면 [math(displaystyle P left( bigcup_{i=1}^n A_i right) le sum_{I subset [n],~|I| le j} left( -1 right)^{|I|} P left( bigcap_{i in I} A_i right))]
[math(j)]가 짝수이면
[math(displaystyle P left( bigcup_{i=1}^n A_i right) ge sum_{I subset [n],~|I| le j} left( -1 right)^{|I|} P left( bigcap_{i in I} A_i right))]
가 성립한다.
|
예를 들어서 [math(n=3)]이면
[math(P left( A cup B cup C right) le P left( A right) + P left( B right) + P left( C right))]
[math(P left( A cup B cup C right) ge P left( A right) + P left( B right) + P left( C right) - P left( A cap B right) - P left( B cap C right) - P left( C cap A right))]
[math(P left( A cup B cup C right) ge P left( A right) + P left( B right) + P left( C right) - P left( A cap B right) - P left( B cap C right) - P left( C cap A right))]
등이 성립하는 식. 교집합의 개수가 많은 항의 기여도가 비교적 작고 계산이 더러울 때, 몇 번째 교집합까지만 더해서 근사를 하고 싶은 상황에서 이 부등식을 활용할 수 있다. 예로 [math(nx ll 1)]일 때 확률 [math(x)]로 일어나는 [math(n)]개의 독립사건의 합집합 왜인지 던파확률의 법칙에 나와있는거 같다 의 확률을 위 부등식에 근거해 다음처럼 근사할 수 있다.
[math(1-nx le left( 1-x right)^n le 1-nx + dfrac{n left( n-1 right)}2 x^2)]