mir.pe (일반/어두운 화면)
최근 수정 시각 : 2023-01-07 19:32:52

포함·배제의 원리


이산수학
Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" 		이론
<colbgcolor=#3CC> 기본 대상 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타 P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}


1. 개요2. 진술3. 증명4. 예시 및 활용, 확장


包 含· 排 除의 原 理, inclusion-exclusion principle

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)]개짜리 교집합이 빠졌으므로 더해주고, ……의 아이디어에서 나왔다.

2. 진술

포함·배제의 원리(inclusion-exclusion principle)
유한집합인 전체집합 [math(U)]의 부분집합 [math(A_1,~A_2, \cdots\cdots,~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, \cdots\cdots,~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(\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)]
( 이항정리를 활용한다) 이 되어 1번 세어진다. 이상을 종합하면 우변의 식은 [math(\cup A_i)]의 원소들을 한 번씩만 센다고 할 수 있다.

4. 예시 및 활용, 확장

교과과정에선 다음과 비슷한 문제로 이 원리가 등장하곤 한다.
ㅁㅁ초등학교 어느 한 반의 [math(40)]명 중 [math(25)]명은 리그 오브 레전드를, [math(18)]명은 오버워치를, [math(9)]명은 둘다 한다. 이 때 롤과 옵치를 둘다 안하는 사람의 수는?
두 합집합의 원소의 수가 [math((25+18)-9=34)]이므로 이 여집합이므로 답은 [math(6)]명이다. 간간히 집합이 3개인 경우도 나오는 듯하다.

조합론 중 특히 enumerative combinatorics 계열에선 집합의 개수가 [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(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)]

분류