이 글에서는 포함-배제의 원리를 일반적이고 명확하게 기술해보고 포함-배제 원리의 산뜻한 증명을 시도해 본다. 이 글에서 소개한 산뜻한 증명은 참고문헌 [1]을 바탕으로 작성한 것이다.
포함-배제의 원리를 산뜻하게 기술하기
학교수학에서는 포함-배제의 원리를 다음과 같이 소개하곤 한다.1
포함-배제의 원리(중,고등학교 버전) 유한개의 원소를 갖는 집합 $A, B$에 대하여 \[ \vert A\cup B\vert=\vert A\vert +\vert B\vert - \vert A\cap B\vert\] 가 성립한다. 또한 유한개의 원소를 갖는 집합 $A, B, C$에 대하여 \[\vert A\cup B\cup C\vert=\vert A\vert+\vert B\vert+\vert C\vert-\vert A\cap B\vert-\vert B\cap C\vert-\vert C\cap A\vert+\vert A\cap B\cap C\vert \] 가 성립한다.
'셈하기를 이용한 포함-배제의 원리 증명'이라는 제목의 포스트(바로가기)에서는 더 많은 집합의 개수를 염두에 둔 다음과 같은 형태로 포함-배제의 원리를 소개하였다.
포함-배제의 원리(1). 유한집합들 $A, B, C, \ldots, Z$ 중에서 하나 이상의 집합에 속하는 원소의 총 개수는 \begin{align*} & +(\vert A\vert+\vert B\vert+\vert C\vert+\cdots+\vert Z\vert) \\ & -(\vert A\cap B\vert+\vert A\cap C\vert+\cdots+\vert Y\cap Z\vert) \\ & +(\vert A\cap B\cap C\vert+\vert A\cap B\cap D\vert+\cdots+\vert X\cap Y\cap Z\vert) \\ & -(\vert A\cap B\cap C\cap D\vert+\cdots+\vert W\cap X\cap Y\cap Z\vert) \\ &\ \ \vdots \\ & \pm \vert A\cap B\cap C\cap \cdots \cap Y\cap Z\vert \end{align*} 이다.
이 경우 포함-배제의 원리를 학교 수학 버전보다야 훨씬 일반화된 형태로 기술하긴 하였지만, $26$개의 알파벳을 사용한 점 혹은 맨 마지막 줄의 기호 `$\pm$'에서 모종의 불편함을 느낀 독자도 있을 것이다. 또한 위의 기술에는 여러 줄을 할애하여 공간 및 잉크를 낭비했다는 아쉬운 점도 있다.
포함-배제의 원리에 등장하는 집합의 개수를 $n$으로 두어 앞선 두 경우보다 일반적이고 명확하게 다음과 같이 그 원리를 기술할 수 있다.
포함-배제의 원리(2). 유한개의 유한 집합 $A_{1}, A_{2}, \ldots, A_{n}$에 대하여 다음이 성립한다. \begin{multline*} \left\vert\bigcup_{j=1}^{n}A_{j} \right\vert=\sum_{i=1}^{n}\left\vert A_{i}\right\vert-\sum_{1\leq i_{1}< i_{2}\leq n}\left\vert A_{i_{1}}\cap A_{i_{2}}\right\vert +\sum_{1\leq i_{1}< i_{2}< i_{3}\leq n}\left\vert A_{i_{1}}\cap A_{i_{2}}\cap A_{i_{3}}\right\vert\\ -\cdots +(-1)^{n-1}\left\vert A_{1}\cap A_{2}\cap\cdots\cap A_{n}\right\vert \end{multline*}
위의 등식을 좀 더 간략하고 명확하게 \[ \left\vert\bigcup_{j=1}^{n}A_{j} \right\vert= \sum_{j=1}^{n}(-1)^{j-1}\sum_{1\leq i_{1}<\cdots < i_{j}\leq n} \left\vert A_{i_{1}}\cap \cdots\cap A_{i_{j}}\right\vert \] 와 같이 쓸 수도 있겠다. 물론 여기서 기호 \[ \sum_{1\leq i_{1}<\cdots < i_{j}\leq n} \] 는 $1\leq i_{1}<\cdots < i_{j}\leq n$를 만족시키는 양의 정수로 이루어진 $j$-tuple $(i_{1},\ldots,i_{j})$에 대한 합으로 총 $\binom{n}{j}$개의 항에 대한 합을 나타낸다.
집합 $X$와 음이 아닌 정수 $k$에 대하여, $k$개의 원소를 갖는 $X$의 부분집합을 모두 모아 놓은 집합을 $\binom{X}{k}$로 나타내자. 그러면 위의 포함-배제 원리의 등식을 \[ \left\vert\bigcup_{j=1}^{n}A_{j} \right\vert= \sum_{k=1}^{n}(-1)^{k-1}\sum_{I\in\binom{\{1,2,\ldots,n\}}{k}}\left\vert \bigcap_{i\in I}A_{i} \right\vert \] 와 같이 쓸 수 있다. 이정도면 포함-배제의 원리를 어느정도 산뜻하게 기술하였다 할 수 있겠다. 마지막으로 합의 기호 $\sum$를 한 번만 사용한 산뜻한 등식을 감상해보자.
포함-배제의 원리(산뜻한 버전). 유한개의 유한 집합 $A_{1}, A_{2}, \ldots, A_{n}$에 대하여 다음이 성립한다. \[ \left\vert\bigcup_{j=1}^{n}A_{j} \right\vert=\sum_{\varnothing\neq I\subset\{1,2,\ldots,n\}}(-1)^{\vert I\vert-1}\left\vert \bigcap_{i\in I}A_{i}\right\vert \]
위의 등식이 자연스럽다고 느껴질때까지 이를 감상하는 것을 추천한다. $n=2$ 혹은 $n=3$인 경우를 직접 써보면 도움이 된다.
포함-배제의 원리를 산뜻하게 증명하기
포함-배제의 원리는 물론 수학적 귀납법을 이용하여 보일 수 있다. 수학적 귀납법을 이용한 증명은 각자 시도해 보기 바란다(블로그에 왠 과제?!). 한편 '셈하기를 이용한 포함-배제의 원리 증명'이라는 제목의 포스트(바로가기)에서는 셈하기를 활용한 증명을 소개하였다.
이 글에서 소개하고자 하는 증명은 위의 어느 증명보다도 더 산뜻한 기분을 느낄 수 있는 증명이다. 먼저 다음 등식을 확인하자. \begin{equation}\label{eq:identity01} (1+x_{1})(1+x_{2})\cdots(1+x_{n})=\sum_{I\subset\{1,2,\ldots,n\}}\left(\prod_{i\in I}x_{i}\right) \tag{1} \end{equation} 여기서 $I=\varnothing$인 경우 $\prod_{i\in \varnothing}x_{i}=1$인 것으로 약속한다. 이번에도 위의 식 \eqref{eq:identity01}이 자연스럽다고 느낄 수 있도록 $n=2$ 혹은 $n=3$인 경우를 직접 써보는 것을 추천한다.
증명(Proof of the PIE)
집합 $A$를 $A=\bigcup_{i=1}^{n}A_{i}$로 정의하고 함수 $f_{i}:A\to \{0, 1\}$를 집합 $A_{i}$의 특성함수, 즉 \[ f_{i}(a)=\begin{cases} 1, & \mbox{if $a\in A_{i}$},\\ 0, & \mbox{otherwise} \end{cases} \] 로 정의하자. 모든 $a\in A$에 대하여 \[ \prod_{i=1}^{n}\left(1-f_{i}(a)\right)=0 \] 가 성립함을 확인할 수 있으며, 또한 식 \eqref{eq:identity01}에서 $x_{i}=-f_{i}(a)$인 경우를 생각하여 \[ \sum_{I\subset\{1,2,\ldots,n\}}(-1)^{\vert I\vert}\prod_{i\in I}f_{i}(a)=0 \] 을 얻는다. 위의 등식을 모든 $a$에 대하여 합한 후, 합의 순서를 바꾸어 \begin{equation}\label{eq:identity02} \begin{split} 0&=\sum_{a\in A}\left(\sum_{I\subset\{1,2,\ldots,n\}}(-1)^{\vert I\vert}\prod_{i\in I}f_{i}(a)\right) \\ &=\sum_{I\subset\{1,2,\ldots,n\}}(-1)^{\vert I\vert}\left(\sum_{a\in A}\prod_{i\in I}f_{i}(a)\right) \end{split} \tag{2} \end{equation} 를 얻는다.
집합 $A$의 원소 $a$를 $\prod_{i\in I}f_{i}(a)$로 대응시키는 함수를 $\bigcap_{i\in I}A_{i}$의 특성함수로 생각할 수 있고 따라서 \[ \sum_{a\in A}\prod_{i\in I}f_{i}(a)=\left\vert\bigcap_{i\in I}A_{i}\right\vert\]를 얻는다. 또한 이때 $I=\varnothing$인 경우를 생각하여 \[ \sum_{a\in A}\prod_{i\in I}f_{i}(a)=\sum_{a\in A}1=\left\vert A\right\vert \] 도 얻는다. 따라서 식 \eqref{eq:identity02}를 \[ \vert A\vert +\sum_{\varnothing\neq I\subset\{1,2,\ldots,n\}}(-1)^{\vert I\vert}\left\vert\bigcap_{i\in I}A_{i}\right\vert=0 \] 로 다시 쓸 수 있으며 이는 포함-배제의 원리를 나타내는 등식과 동일한 식이다.
참고 문헌
- Matousek, J., & Nesetril, J. (2009). Invitation to discrete mathematics. Oxford University Press.
- Martin, G. E. (2001). Counting: The art of enumerative combinatorics. Springer Science & Business Media.