포함-배제의 원리는 조합론에서 여러 집합의 합집합 크기를 계산하는 데 사용되는 중요한 공식입니다. 이 원리를 증명하는 방법은 여러 가지가 있지만, 가장 직관적이고 이해하기 쉬운 방법은 수학적 귀납법을 이용하는 것입니다. 또한, 각 원소가 합집합에 속하는 횟수를 세는 방식으로도 증명할 수 있습니다.
포함-배제의 원리란?
포함-배제의 원리(Principle of Inclusion-Exclusion)는 크기 $n$인 유한 집합 $S$의 부분집합 $A_1, A_2, ext{...}, A_m$에 대해, 이들 집합의 합집합의 크기 $|A_1 igcup A_2 igcup ext{...} igcup A_m|$ 을 다음과 같이 계산하는 원리입니다.
$|A_1 igcup A_2 igcup ext{...} igcup A_m| = extstyle igcup_{i=1}^m |A_i| - extstyle igcup_{1 ext{ $ extless$}}$ i $ extless$ j $ extstyle igcup_{}^{m}} |A_i igcap A_j| + extstyle igcup_{1 ext{ $ extless$}}$ i $ extless$ j $ extless$ k $ extstyle igcup_{}^{m}} |A_i igcap A_j igcap A_k| - ext{...} + (-1)^{m-1} |A_1 igcap A_2 igcap ext{...} igcap A_m|$
간단히 말해, 각 집합의 크기를 더하고, 두 집합의 교집합 크기를 빼고, 세 집합의 교집합 크기를 더하는 식으로, 교집합의 크기를 번갈아 가며 더하거나 빼는 것입니다.
수학적 귀납법을 이용한 증명
포함-배제의 원리를 증명하는 가장 일반적인 방법은 수학적 귀납법을 사용하는 것입니다. 특히, 집합의 개수 $m$에 대한 귀납법을 사용합니다.
1. $m=1$ 일 때:
$|A_1| = |A_1|$ 입니다. 공식이 성립합니다.
2. $m=2$ 일 때:
$|A_1 igcup A_2| = |A_1| + |A_2| - |A_1 igcap A_2|$ 입니다. 이는 집합론의 기본 성질로부터 증명됩니다. $A_1$에만 속하는 원소, $A_2$에만 속하는 원소, $A_1$과 $A_2$ 모두에 속하는 원소로 나누어 생각하면 쉽게 알 수 있습니다.
3. $m=k$ 일 때 성립한다고 가정:
즉, $k$개의 집합에 대해 포함-배제의 원리가 성립한다고 가정합니다.
4. $m=k+1$ 일 때 성립함을 증명:
이제 $k+1$개의 집합 $A_1, ext{...}, A_k, A_{k+1}$에 대해 포함-배제의 원리가 성립함을 보여야 합니다.
$|A_1 igcup ext{...} igcup A_k igcup A_{k+1}| = |(A_1 igcup ext{...} igcup A_k) igcup A_{k+1}|$
$m=2$일 때의 공식을 적용하면:
$= |A_1 igcup ext{...} igcup A_k| + |A_{k+1}| - |(A_1 igcup ext{...} igcup A_k) igcap A_{k+1}|$
여기서, 귀납법의 가정에 따라 $|A_1 igcup ext{...} igcup A_k|$ 를 포함-배제의 원리로 풀어쓸 수 있습니다.
또한, 분배 법칙에 의해 $(A_1 igcup ext{...} igcup A_k) igcap A_{k+1} = (A_1 igcap A_{k+1}) igcup ext{...} igcup (A_k igcap A_{k+1})$ 입니다.
이 부분에 다시 포함-배제의 원리를 적용하면, $A_i igcap A_{k+1}$ 형태의 $k$개 집합의 합집합이 됩니다. 이 역시 귀납법의 가정에 따라 풀어쓸 수 있습니다.
이 과정을 통해 $m=k+1$일 때도 포함-배제의 원리가 성립함을 증명할 수 있습니다.
각 원소의 기여도를 세는 증명
또 다른 증명 방법은 합집합에 속하는 각 원소가 최종 결과에서 정확히 1번만 세어지도록 하는 것입니다. 임의의 원소 $x$를 생각해 봅시다. 이 원소 $x$가 $A_1, ext{...}, A_m$ 중 정확히 $r$개의 집합에 속한다고 가정합니다.
-
$x$가 $k$개의 집합의 교집합에 속할 때: $x$는 $k$개의 집합의 교집합에 속하게 됩니다. 포함-배제의 원리의 공식에서 $x$는 $|A_i|$ 항에서 $r$번 더해지고, $|A_i igcap A_j|$ 항에서는 $inom{r}{2}$번 빼지고, $|A_i igcap A_j igcap A_k|$ 항에서는 $inom{r}{3}$번 더해지는 식으로 계산됩니다.
따라서 $x$가 최종 결과에 기여하는 총 횟수는 다음과 같습니다.
$inom{r}{1} - inom{r}{2} + inom{r}{3} - ext{...} + (-1)^{r-1} inom{r}{r}$
-
이항 정리 활용: 이항 정리에 의해 $(1-1)^r = inom{r}{0} - inom{r}{1} + inom{r}{2} - ext{...} + (-1)^r inom{r}{r} = 0$ 입니다.
따라서, $inom{r}{1} - inom{r}{2} + inom{r}{3} - ext{...} + (-1)^{r-1} inom{r}{r} = inom{r}{1} - inom{r}{2} + ext{...} - (-1)^r inom{r}{r} = - inom{r}{0} + inom{r}{1} - inom{r}{2} + ext{...} + (-1)^r inom{r}{r} + inom{r}{0}$
$= (1-1)^r + inom{r}{0} = 0 + 1 = 1$
단, $r extgreater$ 0일 때 성립합니다.
-
$r=0$인 경우: 원소 $x$가 어떤 집합에도 속하지 않으면, 합집합에 속하지 않으므로 0번 세어져야 합니다. 위 공식은 $r extgreater$ 0일 때 1을 반환하므로, $r=0$인 경우에는 0이 되어야 합니다. 이 경우, 합집합의 크기에 기여하지 않으므로 자연스럽게 0으로 처리됩니다.
따라서, 각 원소는 합집합에 속하는 경우 정확히 1번만 세어지므로 포함-배제의 원리가 증명됩니다.
결론
포함-배제의 원리는 수학적 귀납법이나 각 원소의 기여도를 세는 방식을 통해 증명될 수 있으며, 이는 조합론 문제 해결에 있어 매우 유용하게 활용됩니다.