|
이산수학 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색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
包 含· 排 除의 原 理, 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( \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)]명은 둘다 한다. 이 때 롤과 옵치를 둘다 안하는 사람의 수는? |
조합론 중 특히 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(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(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(1-nx \le \left( 1-x \right)^n \le 1-nx + \dfrac{n \left( n-1 \right)}2 x^2)]