포함배제의 원리

포함-배제의 원리(inclusion-exclusion principle)는 유한 개의 집합들의 합집합의 크기를 각 집합의 크기 및 교집합의 크기를 이용하여 계산하는 방법이다. 조합론, 확률론 등 다양한 분야에서 활용된다.

정의

유한집합 $A_1, A_2, \dots, A_n$이 주어졌을 때, 다음이 성립한다.

$|A_1 \cup A_2 \cup \dots \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| - \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$

여기서 $|A|$는 집합 $A$의 원소 개수를 나타낸다.

설명

포함-배제의 원리는 다음과 같은 방식으로 이해할 수 있다.

1. 각 집합의 크기를 모두 더한다. (포함)
2. 두 집합의 교집합의 크기를 모두 뺀다. (배제)
3. 세 집합의 교집합의 크기를 모두 더한다. (포함)
4. 네 집합의 교집합의 크기를 모두 뺀다. (배제)
5. 이 과정을 반복하여 마지막으로 n개의 집합의 교집합의 크기를 더하거나 뺀다.

이렇게 포함과 배제를 반복함으로써, 각 원소가 합집합에 정확히 한 번만 포함되도록 보장한다.

예시

두 집합 A와 B의 합집합의 크기를 구하는 경우, 포함-배제의 원리는 다음과 같이 적용된다.

$|A \cup B| = |A| + |B| - |A \cap B|$

세 집합 A, B, C의 합집합의 크기를 구하는 경우, 다음과 같다.

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

응용

포함-배제의 원리는 다양한 문제 해결에 응용될 수 있다. 예를 들어, 주어진 범위 내에서 특정 수로 나누어 떨어지지 않는 정수의 개수를 구하거나, 특정 조건을 만족하는 순열의 개수를 구하는 데 사용될 수 있다. 또한, 그래프 이론, 암호학 등 다양한 분야에서 응용된다.