포함-배제 원리의 세 가지 증명

이 글에서는 포함-배제 원리를 소개하고, 증명 방법 세 가지를 살펴봅니다. 이 글은 Jiří Matoušek 교수님과 Jaroslav Nešetřil 교수님의 책 『Invitation to Discrete Mathematics』 2판 3.7절의 내용을 참고하여 작성하였습니다.

포함-배제 원리

세 유한집합 \(A,\) \(B,\) \(C\)가 있을 때 이들의 합집합의 원소의 개수는 다음과 같다. \[\begin{align} \lvert A\cup B\cup C \rvert &= \lvert A \rvert + \lvert B \rvert + \lvert C \rvert \\[5pt] &\,\,- \lvert A\cap B \rvert - \lvert B \cap C \rvert - \lvert C \cap A \rvert + \lvert A \cap B \cap C \rvert.\tag{1} \end{align}\] 일반적으로 \(n\)개의 유한집합 \(A_1 ,\) \(A_2 ,\) \(\cdots ,\) \(A_n \)이 있을 때 이들의 합집합의 원소의 개수는 다음과 같다. \[\begin{align} \lvert A_1 \cup A_2 \cup \cdots \cup A_n \rvert &= \lvert A_1 \rvert + \lvert A_2 \rvert + \cdots + \lvert A_n \rvert \\[5pt] &\quad - \lvert A_1 \cap A_2 \rvert - \lvert A_1 \cap A_3 \rvert - \cdots - \lvert A_1 \cap A_n \rvert \\[5pt] &\quad - \lvert A_2 \cap A_3 \rvert - \cdots - \lvert A_{n-1} \cap A_n \rvert \\[5pt] &\quad + \lvert A_1 \cap A_2 \cap A_3 \rvert + \lvert A_1 \cap A_2 \cap A_4 \rvert \\[5pt] &\quad + \cdots + (-1)^{n-1} \lvert A_1 \cap A_2 \cap \cdots \cap A_n \rvert.\tag{2} \end{align}\] 이와 같이 유한 개의 유한집합의 합집합의 원소의 개수를 구하는 방법을 포함-배제 원리(inclusion-exclusion principle)라고 부른다.

포함-배제 원리를 (2)와 같은 식으로 기술하는 것은 명료하지 못하다. 식의 형태를 살짝 개선하면 다음과 같은 식을 얻는다. \[\begin{align} \lvert A_1 \cup A_2 \cup \cdots \cup A_n \rvert &= \sum_{i=1}^{n} \lvert A_i \rvert - \sum_{1\le i_1 < i_2 \le n} \lvert A_{i_1} \cap A_{i_2} \rvert \\[5pt] &\quad + \sum_{1\le i_1 < i_2 < i_3 \le n} \lvert A_{i_1} \cap A_{i_2} \cap A_{i_3} \rvert \\[5pt] &\quad - \cdots + (-1)^{n-1} \lvert A_1 \cap A_2 \cap \cdots \cap A_n \rvert .\tag{3} \end{align}\] 만약 집합 \(X\)의 부분집합 중 원소의 개수가 \(k\)인 것들의 모임을 \(\binom{X}{k}\)로 나타내면 (3)은 다음과 같이 명료하게 나타낼 수 있다.

등식 (4)는 다음과 같이 더 간단하게 나타낼 수도 있다. \[\left\lvert \bigcup_{i=1}^{n} A_i \right\rvert = \sum_{\varnothing \ne I \subseteq \left\{ 1,\,2,\,\cdots ,\,n \right\}} (-1)^{\lvert I \rvert - 1} \left\lvert \bigcap _{i\in I} A_i \right\rvert.\tag{5}\]

이제 포함-배제 원리를 세 가지 방법으로 증명해 보자.

첫 번째 증명: 수학적 귀납법

집합의 수를 \(n\)이라 하고 \(n\)에 대한 수학적 귀납법을 사용하자. 먼저 \(n=1\) 또는 \(n=2\)인 경우는 자명하다.

이제 (4)에서 \(n\)을 \(n-1\)로 바꾼 등식이 성립한다고 가정하자. 그러면 다음을 얻는다. \[\begin{align} \left\lvert \bigcup_{i=1}^{n} A_i \right\rvert &= \left\lvert \left( \bigcup_{i=1}^{n-1}A_i \right) \cup A_n \right\rvert \tag{6}\\[5pt] &= \left\lvert \bigcup_{i=1}^{n-1} A_i \right\rvert + \lvert A_n \rvert - \left\lvert \left( \bigcup_{i=1}^{n-1} A_i \right) \cap A_n \right\rvert \tag{7}\\[5pt] &= \left\lvert \bigcup_{i=1}^{n-1} A_i \right\rvert + \lvert A_n \rvert - \left\lvert \bigcup_{i=1}^{n-1} \left( A_i \cap A_n \right) \right\rvert \tag{8}\\[5pt] &= \left( \sum_{k=1}^{n-1} (-1)^{k-1} \sum_{I\in\binom{\left\{1,\,2,\,\cdots,\,n-1\right\}}{k}} \left\lvert \bigcap_{i\in I} A_i \right\rvert \right) + \lvert A_n \rvert \\[5pt] &\quad - \left( \sum_{k=1}^{n-1} (-1)^{k-1} \sum_{I\in\binom{\left\{1,\,2,\,\cdots,\,n-1\right\}}{k}} \left\lvert \bigcap_{i\in I\cup\left\{ n \right\}} A_i \right\rvert \right) . \tag{9} \end{align}\] 여기서 마지막 식은 (4)의 우변과 같다. 그러므로 수학적 귀납법에 의하여 증명이 완료되었다.

(4)의 우변과 같은 명료한 표현 방법을 사용하지 않았더라면, 증명을 이렇게 우아하게 기술할 수 없었을 것이다.

두 번째 증명: 셈하기

임의의 원소 \(x\in A_1 \cup A_2 \cup \cdots \cup A_n\)을 생각하자. 이 원소는 (4)의 좌변의 합집합의 크기에 딱 \(1\) 만큼 보태어 주는 역할을 한다. 그렇다면 (4)의 우변의 크기에 \(x\)가 보태어 주는 크기가 얼마인지를 구하고 그것이 \(1\)임을 보이면 증명이 완료되는 셈이다. \(A_i\)들 중 \(x\)를 원소로 갖는 것들의 개수를 \(j\)라고 하자. \(A_i\)들 중 \(x\)를 원소로 갖는 것들의 이름을 다시 붙여서 \(A_1, \) \(A_2 ,\) \(\cdots,\) \(A_j\)라고 하자.

\(A_1 ,\) \(A_2 ,\) \(\cdots ,\) \(A_j\) 중에서만 \(k\)개의 집합을 골라 교집합하여 만든 집합에 \(x\)가 속하며, 다른 방법으로 만든 교집합에는 \(x\)가 속하지 않는다. 서로 다른 \(j\)개의 물건 중 \(k\)개를 택하는 경우의 수는 \(\binom{j}{k}\)이므로, 교집합하여 만든 집합 중 \(x\)를 원소로 갖는 경우의 수는 \(\binom{j}{k}\)이다. (4)의 우변에서 \(k\)개의 집합의 교집합의 원소의 개수의 합에 \((-1)^{k-1}\)을 곱하여 계산하므로, \(x\)가 보태어 주는 크기는 다음과 같다. \[j - \binom{j}{2} + \binom{j}{3} - \cdots + (-1)^{j-1} \binom{j}{j} .\tag{10}\] 그런데 \[\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \binom{n}{3} + \cdots = \sum_{k=0}^{n}(-1)^k \binom{n}{k} = 0\tag{11}\] 이므로 (10)의 값은 \(1\)이다. (4)의 우변에서 각 원소 \(x\)가 보태어 주는 크기는 \(1\)이므로, (10)의 우변은 모든 원소의 개수를 센 것과 같다.

세 번째 증명: 다항식과 특성함수

이번에는 다음과 같은 등식을 사용하여 증명해 보자. \[(1+x_1)(1+x_2)\cdots (1+x_n) = \sum_{I\subseteq\left\{1,\,2,\,\cdots,\,n\right\}} \left( \prod_{i\in I} x_i \right).\tag{12}\] 위 식에서 \(I=\varnothing\)인 경우는 당연히 \(\prod_{i\in I} x_i = 1\)로 정의한다.

\(A = A_1 \cup A_2 \cup \cdots \cup A_n \)이라고 하자. 그리고 집합 \(A_i\)의 특성함수를 \(f_i : A\,\rightarrow \,\left\{0,\,1\right\}\)로 나타내자. 즉 \(a\in A_i\)일 땐 \(f_i (a) = 1\)이고, \(a\notin A_i\)일 땐 \(f_i (a) =0\)이다. 각 \(a\in A\)에 대하여 \[\prod_{i=1}^{n} (1-f_i (a)) = 0\tag{13}\] 이므로 (12)에 \(x_i = -f_i (a)\)를 대입하면 다음 식을 얻는다. \[\sum_{I\subseteq\left\{1,\,2,\,\cdots,\,n\right\}} (-1)^{\lvert I \rvert} \prod_{i\in I} f_i (a) =0.\tag{14}\] 모든 \(a\)에 대한 (14)의 합을 구하고, 합 기호의 순서를 바꾸면 다음을 얻는다. \[\begin{align} 0 &= \sum_{a\in A} \left( \sum_{I\subseteq\left\{1,\,2,\,\cdots,\,n\right\}} (-1)^{\lvert I \rvert} \prod_{i\in I} f_i (a) \right) \\[5pt] &= \sum_{I\subseteq\left\{ 1,\,2,\,\cdots ,\,n\right\}} (-1)^{\lvert I \vert} \left(\sum_{a\in A} \prod_{i\in I} f_i (a) \right). \tag{15} \end{align}\] 이제 함수 \[a\,\mapsto\,\prod_{i\in I}f_i (a)\tag{16}\] 가 \(\bigcap_{i\in I} A_i\)의 특성함수이므로 다음을 얻는다. \[\sum_{a\in A} \prod_{i\in I} f_i (a) = \left\lvert \bigcap_{i\in I} A_i \right\rvert .\tag{17}\] 특히 \(I=\varnothing\)일 때 \(\prod_{i\in\varnothing} f_i (a) = 1\)이므로 다음이 성립한다. \[\sum_{a\in A} \prod_{i\in\varnothing} f_i (a) = \sum_{a\in A} 1 = \lvert A \rvert.\tag{18}\] 그러므로 (15)를 다음과 같이 쓸 수 있다. \[\lvert A \rvert + \sum_{\varnothing \ne I \subseteq \left\{ 1,\,2,\,\cdots,\,n\right\}} (-1)^{\lvert I \rvert} \left\lvert \bigcap_{i\in I} A_i \right\rvert = 0.\tag{19}\] 이 식은 곧 포함-배제 원리의 식과 일치한다.