포함·배제의 원리

 



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

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

1. 개요

조합론에서 여러 개의 합집합의 크기를 구할 때 사용하는 공식이다. 이산수학 및 확률론에서 중요하고 유용한 원리 중 하나이다.
비교적 친숙한 $$|A \cup B| = |A| + |B| - |A \cap B|$$, $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|$$ 등의 공식을 $$n$$개짜리 합집합으로 일반화했다고 생각할 수 있다. 이름의 유래는 $$A$$, $$B$$, ……에 속하는 원소들을 포함시키고(더하고), 두 번 세어준 $$A \cap B$$, ……의 원소들을 배제하고(빼고), 다시 $$3$$개짜리 교집합이 빠졌으므로 더해주고, ……의 아이디어에서 나왔다.

2. 진술

'''포함·배제의 원리'''(inclusion-exclusion principle)
유한집합인 전체집합 $$U$$의 부분집합 $$A_1,~A_2, \cdots\cdots,~A_n$$에 대해, 이들의 합집합의 원소의 개수는 다음과 같이 주어진다.
$$\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| $$
여기서 $$[n] = \{1,~2, \cdots\cdots,~n\}$$이고, $$| \cdot |$$은 집합의 크기(원소의 개수)이다. 이를 풀어쓰면 다음과 같다.
$$|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|$$
홀수 개의 교집합은 더하고, 짝수 개의 교집합을 뺀다는 식으로 기억하면 된다. 다음과 같은 여집합 형태도 많이 등장하는데 ($$I=\emptyset$$일 때는 전체집합을 더하는 것으로 간주) 이 경우에는 부호가 반대가 된다.
$$ \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|$$
사실 원소의 개수가 가장 생각하기 쉽지만 집합의 크기를 재는 어떤 함수이건 적용할 수 있다. 확률론에서의 다음 버전도 많이 쓰인다.
확률공간의 사건 $$A_1,~A_2, \cdots \cdots,~A_n$$에 대해, 이들의 합집합의 확률은 다음과 같이 주어진다.
$$\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. 증명

원소의 개수를 다룬 버전을 서술한다. 일반적인 확률 및 측도 버전은 비슷하게 접근하면 된다. (합 및 개수를 확률/측도로 바꾼다던지 등등)
전체집합 $$U$$의 원소들은 $$A_i$$에 속하냐, 속하지 않냐 두 가지의 기준으로 나눌 수 있다. 어떤 원소 $$x \in U$$가 $$i=i_1,~i_2, \cdots \cdots,~i_k$$에 대해선 $$x \in A_i$$이고 나머지에 대해선 $$x \notin A_i$$라 하자. $$J = \{ i_1, \cdots \cdots,~i_k \}$$라고 놓자. 이제 임의의 $$I$$에 대해서 $$\displaystyle \bigcap_{i \in I} A_i$$가 $$x$$를 포함할 필요충분조건은 $$I \subset J$$가 되고, 따라서 공식의 우변에서 $$x$$가 세어지는 횟수는 $$\displaystyle \sum_{\emptyset \ne I \subset J} \left( -1 \right)^{|I|-1} $$가 된다. 만약 $$J$$가 공집합이라면 그런 $$I$$는 없으므로 횟수는 [math(0)]번이 된다. $$J$$가 공집합이 아니라면 저 횟수는
$$\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번 세어진다. 이상을 종합하면 우변의 식은 $$\cup A_i$$의 원소들을 한 번씩만 센다고 할 수 있다.

4. 예시 및 활용, 확장

교과과정에선 다음과 비슷한 문제로 이 원리가 등장하곤 한다.
ㅁㅁ초등학교 어느 한 반의 $$40$$명 중 $$25$$명은 리그 오브 레전드를, $$18$$명은 오버워치를, $$9$$명은 둘다 한다. 이 때 롤과 옵치를 둘다 안하는 사람의 수는?
두 합집합의 원소의 수가 $$(25+18)-9=34$$이므로 이 여집합이므로 답은 $$6$$명이다. 간간히 집합이 3개인 경우도 나오는 듯하다.
조합론 중 특히 enumerative combinatorics 계열에선 집합의 개수가 $$n$$개인 경우 각 잡고 제대로 쓴다면 꽤나 강력한 도구가 되는데, 예로 다음과 같은 문제들에 포함·배제의 원리를 적용할 수 있다.
  • 교란순열, 즉 일대일대응 $$\sigma: [n] \rightarrow [n]$$ 중 모든 $$x$$에 대해 $$\sigma \left( x \right) \neq x$$인 $$\sigma$$의 개수
  • 제한된 순열 문제. 집합 $$A \subset[n] \times [n]$$이 주어졌을 때 $$(x,~\sigma \left( x \right)) \notin A$$인 순열의 개수. 위 교란순열 문제의 일반화이다.
  • 전사함수 $$f: [n] \rightarrow [m]$$의 개수. 제2종 스털링 수(Stirling numbers of the second kinds)와도 연관이 있다.
  • 어떤 수 $$n$$이 주어졌을 때 $$1 \le m \le n$$인 정수 $$m$$ 중 $$n$$과 서로소인 $$m$$의 개수 (즉 오일러 정리에 나오는 오일러 파이 함수 $$\varphi \left( n \right)$$ 구하기)
  • 변의 길이가 정수고 둘레가 $$n$$인 삼각형의 개수(변의 순서가 다르면 다른 것으로 취급할 때).
일반적으로 여러 개의 제약조건이 복합적으로 작용할 때, 보통 이들의 교집합을 생각하는 건 쉽지만 합집합 및 여집합을 생각하는 건 어려울 때가 많은데, 이럴 때 이 포함 배제의 원리를 범용적으로 쓸 수 있다.
한편 확률론에선 다음 부등식 버전의 포함배제의 원리를 생각하기도 한다.
'''본페로니 부등식'''(Bonferroni inequality)
위의 포함·배제 공식을 $$|I| \le j$$인 범위까지만 더했을 때, $$j$$가 홀수이면
$$\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)$$
$$j$$가 짝수이면
$$\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)$$
가 성립한다.
예를 들어서 $$n=3$$이면
$$P \left( A \cup B \cup C \right) \le P \left( A \right) + P \left( B \right) + P \left( C \right)$$
$$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)$$
등이 성립하는 식. 교집합의 개수가 많은 항의 기여도가 비교적 작고 계산이 더러울 때, 몇 번째 교집합까지만 더해서 근사를 하고 싶은 상황에서 이 부등식을 활용할 수 있다. 예로 $$nx \ll 1$$일 때 확률 $$x$$로 일어나는 $$n$$개의 독립사건의 합집합 의 확률을 위 부등식에 근거해 다음처럼 근사할 수 있다.
$$1-nx \le \left( 1-x \right)^n \le 1-nx + \dfrac{n \left( n-1 \right)}2 x^2$$

분류