Lemma for PIE. 원소의 개수가 \(t\)인 전체집합이 주어져있을 때, 전체집합의 부분집합 \(A, B, C, \ldots, Z\)의 어느 것에도 속하지 않는 원소의 개수는 \begin{align*} t & \\ & -(\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*} 이다.
증명
부분집합 \(A, B, C, \ldots, Z\) 중 정확히 \(k\)개에 속하는 원소를 생각하자. 이 원소가 증명하고자 하는 식에서 세어지는 것을 생각해보자. 식의 각 줄에 나타나는 횟수를 고려하여 써보면 \[ 1-\binom{k}{1}+\binom{k}{2}-\binom{k}{3}+\cdots +(-1)^{k}\binom{k}{k} \] 와 같다. 이항정리에 의해 \(k>0\)일 때, 이 식의 값이 \((1-1)^{k}\), 즉 \(0\)이며, \(k=0\)일 때에도 이 식의 값은 \(1\)임을 얻으며 이 결과가 나타내는 것이 바로 증명하고자 하는 것이다.
PIE는 위의 보조정리로부터 다음과 같이 바로 얻어지는 것이다. 위의 보조정리나 아래의 PIE나 동일한 내용을 다른 방식으로 말한 것에 불과하며, 위의 보조정리를 PIE라 부르는 경우도 있다.
포함-배제의 원리. 유한집합들 \(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*} 이다.
PIE를 다른 표기를 이용하여 다시 써볼텐데, 이는 종종 유용하게 쓰이곤 한다. 그리고 참고로 별도의 증명 없이 PIE를 일반화한 명제 두 개를 소개한다.
주어진 집합 \(A_{1}, A_{2}, \ldots, A_{n}\)의 모든 \(k\)-tuple intersection 각각의 크기들의 합을 \(S_{k}\)로 나타내자. 많은 문제에서 \(S_{k}\)는 \(\binom{n}{k}\)개의 동일한 형태의 항의 합인 것에 유의하자. 이 표기를 이용하면 다음과 같이 쓸 수 있다. \begin{align*} S_{1}&=\vert A_{1}\vert+\vert A_{2}\vert+\vert A_{3}\vert+\cdots+\vert A_{n}\vert,\\ S_{2} &=\vert A_{1}\cap A_{2}\vert+\vert A_{1}\cap A_{3}\vert+\cdots+\vert A_{n-1}\cap A_{n}\vert, \\ S_{3} &=\vert A_{1}\cap A_{2}\cap A_{3}\vert+\vert A_{1}\cap A_{2}\cap A_{4}\vert+\cdots+\vert A_{n-2}\cap A_{n-1}\cap A_{n}\vert, \\ S_{4} &=\vert A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\vert+\cdots+\vert A_{n-3}\cap A_{n-2}\cap A_{n-1}\cap A_{n}\vert, \\ \phantom{1} \vdots & \\ S_{n} &=\vert A_{1}\cap A_{2}\cap A_{3}\cap \cdots\cap A_{n-1}\cap A_{n}\vert \end{align*}
PIE and Two Generalizations. 주어진 집합 \(A_{1}, A_{2}, \ldots, A_{n}\)의 모든 \(k\)-tuple intersection 각각의 크기들의 합을 \(S_{k}\)로 나타내자. 그러면 주어진 집합들 중 적어도 하나의 집합에 속하는 원소의 개수는 \[ S_{1}-S_{2}+S_{3}-S_{4}+\cdots+(-1)^{k-1}S_{k}+\cdots+(-1)^{n-1}S_{n} \] 이다. 다음으로 주어진 집합들 중 정확히 \(r\)개에 속하는 원소의 개수는 \[ S_{r}-\binom{r+1}{r}S_{r+1}+\binom{r+2}{r}S_{r+2}-\cdots+(-1)^{k}\binom{r+k}{r}S_{r+k}+\cdots+(-1)^{n-r}\binom{n}{r}S_{n} \] 이다. 또한 주어진 집합들 중 적어도 \(r\)개에 속하는 원소의 개수는 \[ S_{r}-\binom{r}{r-1}S_{r+1}+\binom{r+1}{r-1}S_{r+2}-\cdots+(-1)^{k}\binom{r+k-1}{r-1}S_{r+k}+\cdots+(-1)^{n-r}\binom{n-1}{r-1}S_{n} \] 이다.
PIE Problems Ⅱ.
- 모든 모음을 포함하고 있는 것은 아닌 \(10\)-letter word는 몇 개인가?
- 서로 구별되는 \(4\)개의 상자에 \(40\)개의 빨간 공을 담을 때, 각 상자에는 많아야 \(15\)개의 공이 들어 있도록 담는 경우의 수는?
- 서로 구별되는 \(6\)개의 상자에 서로 구별되는 \(11\)개의 공을 담을 때, 적어도 하나의 상자는 비어 있도록 담는 경우의 수는?
- 방정식 \[ x_{1}+x_{2}+x_{3}+x_{4}=100 \] 의 정수해 중 \(0\leq x_{i}\leq 30\ (i=1, 2, 3, 4)\)를 만족시키는 것은 몇 개인가?
- \(1\)센트짜리 동전 \(7\)개, \(5\)센트짜리 동전 \(8\)개, \(25\)센트짜리 동전 \(7\)에서 총 \(10\)개의 동전을 택하는 경우의 수는?
- 서로 구별되는 \(n\)개의 상자에 서로 구별되는 \(r\)개의 공을 담을 때, 비어 있는 상자가 없도록 담는 경우의 수는?