[조합론] 9. 포함 배제의 원리, 비둘기 집의 원리

[조합론] 9. 포함 배제의 원리, 비둘기 집의 원리

예: 어느 회사의 신입사원 모집에 18명이 지원했고, 그 중 10명은 전산학, 7명은 경영학 전공이고, 3명은 전산학과 경영학 모두를 전공했다. 그러면 전산학이나 경영학을 전공한 지원자의 수는?

풀이: 전체집합을 $U$, 전산학 전공자들의 집합을 $A$, 경영학 전공자들의 집합을 $B$라고 하자. 그러면 $|U|=18$, $|A|=10$, $|B|=7$, $|A\cap B|=3$이므로 $$|A\cup B|=|A|+|B|-|A\cap B|=10+7-3=14$$ 이다. $|A|+|B|$의 계산에서 $A\cap B$에 속하는 원소들이 두번 계산되었기 때문에 $|A\cap B|$를 빼는 것이다.

이러한 계산과정을 포함 배제의 원리(inclusion-exclusion principle)라고 한다.

전체집합 $U$의 $n$개의 부분집합 $A_{1},\,A_{2},\,\cdots,\,A_{n}$에 대하여 $S_{k}\,(1\leq k\leq n)$를 $k$개의 $A_{i}\,(1\leq i\leq n)$들의 교집합의 원소들의 총합 즉, $$S_{k}=\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n}{\left|\bigcap_{j=1}^{k}{A_{i_{j}}}\right|}$$ 라고 하자. 예를들어 $$\begin{align*}S_{1}&=|A_{1}|+|A_{2}|+\cdots+|A_{n}|\\S_{2}&=|A_{1}\cap A_{2}|+|A_{2}\cap A_{3}|+\cdots+|A_{n-1}\cap A_{n}|\end{align*}$$ 이므로 $$\begin{align*}|A\cup B|&=S_{1}-S_{2}\\&=|A|+|B|-|A\cap B|\\|A\cup B\cup C|&=S_{1}-S_{2}+S_{3}\\&=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|\end{align*}$$ 이다.

 

다음은 일반화된 포함 배제의 원리이다.

정리(포함 배제의 정리 1): 전체집합 $U$의 $n$개의 부분집합 $A_{1},\,A_{2},\,\cdots,\,A_{n}$에 대하여 $$\left|\bigcup_{i=1}^{n}{A_{i}}\right|=\sum_{k=1}^{n}{(-1)^{k+1}S_{k}}$$ 이다.

증명: 어떤 원소가 모든 $A_{i}\,(1\leq i\leq n)$에 대해 어느 곳에도 포함되지 않은 원소이면, 우변의 계산에서 한번도 계산되지 않았다.

$A_{i}\,(1\leq i\leq n)$중 $m\,(1\leq m\leq n)$개의 집합에 동시에 속하는 원소 $x$를 고려하자. $x$는 $S_{1}$의 계산에서 $\displaystyle\binom{m}{1}$번, $S_{2}$의 계산에서 $\displaystyle\binom{m}{2}$번, ..., $S_{m}$의 계산에서 $\displaystyle\binom{m}{m}$번 계산되었다. 따라서 우변의 계산에서 $$\binom{m}{1}-\binom{m}{2}+\cdots+(-1)^{m}\binom{m}{m}=1$$ 만큼 계산되므로 식이 성립한다.

정리(포함 배제의 정리 2): 전체집합 $U$의 $n$개의 부분집합 $A_{1},\,A_{2},\,\cdots,\,A_{n}$에 대하여 $$\left|\bigcap_{i=1}^{n}{A_{i}^{c}}\right|=|U|+\sum_{k=1}^{n}{(-1)^{k}S_{k}}$$ 이다.

증명: 다음 식으로부터 성립한다. $$\left|\bigcap_{i=1}^{n}{A_{i}^{c}}\right|=|U|-\left|\bigcup_{i=1}^{n}{A_{i}}\right|$$

여러가지 성질들 중에서 적어도 하나를 만족하는 원소의 수를 셀 때는 정리 1을 사용하는게 편리하고, 모든 성질을 만족하는 원소의 수를 셀 때는 정리 2를 사용하는게 편리하다. 

예: 52장의 카드에서 5장을 뽑을 때, 뽑힌 5장의 카드들의 무늬가 스페이드, 다이아몬드, 하트, 클로버 모두를 갖는 경우의 수는?

풀이: 전체집합 $U$를 52장의 카드에서 5장을 뽑을 때 나타나는 것들의 집합이라고 하고

$A_{1}$을 $U$의 원소 중에서 스페이드가 없는 것들의 집합, $A_{2}$를 $U$의 원소 중에서 다이아몬드가 없는 것들의 집합, $A_{3}$을 $U$의 원소 중에서 하트가 없는 것들의 집합, $A_{4}$를 $U$의 원소 중에서 클로버가 없는 것들의 집합이라고 하자.

이 문제에서 구하려는 수는 $|A_{1}^{c}\cap A_{2}^{c}\cap A_{3}^{c}\cap A_{4}^{c}|$이고 $$|A_{i}|=\binom{39}{4},\,|A_{i}\cap A_{j}|=\binom{26}{5},\,|A_{i}\cap A_{j}\cap A_{k}|=\binom{13}{5}$$ 이므로 $$\begin{align*}S_{1}&=4\binom{52-13}{5}=4\binom{39}{5},\,S_{2}=\binom{4}{2}\binom{52-26}{5}=6\binom{26}{5}\\S_{3}&=4\binom{13}{5},\,S_{4}=0\end{align*}$$ 이고 따라서 포함 배제의 정리 2에 의해 $$|A_{1}^{c}\cap A_{2}^{c}\cap A_{3}^{c}\cap A_{4}^{c}|=\binom{52}{5}-4\binom{39}{5}+6\binom{26}{5}-4\binom{13}{5}+0$$ 이다.

예: 100이하의 자연수 중 2, 3, 5, ,7의 배수들의 개수는?

풀이: 전체집합 $U$를 100이하의 자연수들의 집합이라고 하고, 임의의 자연수 $i$에 대하여 $A_{i}$를 $U$의 원소 중에서 $i$의 배수들의 집합이라고 하자. 그러면 이 문제에서 구하려는 수는 $|A_{2}\cup A_{3}\cup A_{5}\cup A_{7}|$이고 $$\begin{align*}S_{1}&=|A_{2}|+|A_{3}|+|A_{5}|+|A_{7}|\\&=\left\lfloor\frac{100}{2}\right\rfloor+\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{5}\right\rfloor+\left\lfloor\frac{100}{7}\right\rfloor\\&=50+33+20+14\\&=117\\S_{2}&=|A_{6}|+|A_{10}|+|A_{14}|+|A_{15}|+|A_{21}|+|A_{35}|\\&=16+10+7+6+4+2\\&=45\\S_{3}&=|A_{30}|+|A_{42}|+|A_{70}|=3+2+1\\&=6\\S_{4}&=0\end{align*}$$ 이므로 따라서 $$|A_{2}\cup A_{3}\cup A_{5}\cup A_{7}|=S_{1}-S_{2}+S_{3}-S_{4}=117-45+6=78$$ 이다.

 

예: 2 이상의 정수 $n$의 표준분해가 $n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$일 때의 오일러-피($\phi$) 함숫값($n$이하의 자연수 중에서 $n$과 서로소인 것들의 개수)은 $$\phi(n)=n\prod_{i=1}^{k}{\left(1-\frac{1}{p_{i}}\right)}$$ 이다.

풀이: $U=\{1,\,2,\,\cdots,\,n\}$, $i=1,\,2,\,\cdots,\,n$에 대하여 $A_{i}=\{x\in\mathbb{N}\,|\,1\leq x\leq n,\,p_{i}|x\}$라고 하자. 그러면 $\displaystyle|A_{i}|=\frac{n}{p_{i}}$이고, $A_{i}\cap A_{j}$는 $n$을 넘지 않는 $p_{i}$와 $p_{j}$의 배수들의 집합이므로 $\displaystyle|A_{i}\cap A_{j}|=\frac{n}{p_{i}p_{j}}$이다. 그러면 $$\left|\bigcap_{i=1}^{n}{A_{i}}\right|=\frac{n}{p_{1}p_{2}\cdots p_{k}}$$ 이고 포함 배제의 정리 2에 의해 $$\begin{align*}\phi(n)&=\left|\left(\bigcup_{i=1}^{k}{A_{i}}\right)^{c}\right|=|U|-\left|\bigcup_{i=1}^{k}{A_{i}}\right|=|U|-\sum_{i=1}^{k}{S_{k}}\\&=n-\left(\frac{n}{p_{1}}+\cdots+\frac{n}{p_{k}}\right)+\left(\frac{n}{p_{1}p_{2}}+\cdots+\frac{n}{p_{k-1}p_{k}}\right)+\cdots+(-1)^{k}\frac{n}{p_{1}p_{2}\cdots p_{k}}\\&=n\left\{1-\left(\frac{1}{p_{1}}+\cdots+\frac{1}{p_{n}}\right)+\left(\frac{1}{p_{1}p_{2}}+\cdots+\frac{1}{p_{k-1}p_{k}}\right)+\cdots+\frac{(-1)^{k}}{p_{1}p_{2}\cdots p_{k}}\right\}\\&=\frac{n}{p_{1}p_{2}\cdots p_{n}}\{p_{1}p_{2}\cdots p_{k}-(p_{1}p_{2}\cdots p_{k-1}+\cdots+p_{2}p_{3}\cdots p_{k})+\cdots+(-1)^{k}\}\\&=\frac{n}{p_{1}p_{2}\cdots p_{n}}\{(p_{1}-1)\cdots(p_{k}-1)\}\\&=n\left(\frac{p_{1}-1}{p_{1}}\cdots\frac{p_{k}-1}{p_{k}}\right)\\&=n\prod_{i=1}^{k}{\left(1-\frac{1}{p_{i}}\right)}\end{align*}$$ 이다.

정리: $|X|=m,\,|Y|=n$인 두 집합 $X,\,Y$에 대하여 집합 $X$에서 집합 $Y$로의 전사함수($f[X]=Y$)의 개수는 $$n^{m}-\binom{n}{1}(n-1)^{m}+\binom{n}{2}(n-2)^{m}-\cdots+(-1)^{n}\binom{n}{n}(n-n)^{m}$$ 이다.

증명: 집합 $X$에서 집합 $Y$로의 함수의 개수는 $n^{m}$이고 $Y=\{1,\,2,\,\cdots,\,n\}$이라고 하자. 임의의 $i\in Y$에 대하여 $A=\{f:\,X\,\rightarrow\,Y\,|\,i\notin f[X]\}$라 하면, 전사함수의 개수는 $\displaystyle\left|\bigcap_{i=1}^{n}{A_{i}^{c}}\right|$이고, 포함 배재의 정리 2에 의해 $$\begin{align*}\left|\bigcap_{i=1}^{n}{A_{i}^{c}}\right|&=|U|-\left|\bigcup_{i=1}^{n}{A_{i}}\right|\\&=n^{m}-\binom{n}{1}(n-1)^{m}+\binom{n}{2}(n-2)^{m}-\cdots+(-1)^{n}\binom{n}{n}(n-n)^{m}\end{align*}$$ 이다.

교란(derangement)은 $\{1,\,2,\,\cdots,\,n\}$의 치환 중 각 $i=1,\,2,\,\cdots,\,n$가 $i$번째에 오지 않는 것이고, 그 수(교란수)를 $D_{n}$으로 나타낸다. 예를들어 $D_{1}=0,\,D_{2}=1$이고, $D_{3}=2\,(2,\,3,\,1,\,3,\,1,\,2)$이다.

정리: 교란수 $D_{n}$은 다음과 같다. $$D_{n}=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^{n}\frac{1}{n!}\right)$$

증명: $\{1,\,2,\,\cdots,\,n\}$의 전체 치환의 수는 $n!$이고, 집합 $A_{i}$를 $\{1,\,2,\,\cdots,\,n\}$의 치환 중 각 $i=1,\,2,\,\cdots,\,n$가 $i$번째에 놓여있는 치환들의 집합이라고 하자. 그러면 $\displaystyle D_{n}=\left|\bigcap_{i=1}^{n}{A_{i}^{c}}\right|$이고, 포함 배제의 정리 2에 의해 $$\begin{align*}D_{n}&=n!-\left|\bigcup_{i=1}^{n}{A_{i}}\right|\\&=n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\cdots+(-1)^{n}\binom{n}{n}(n-n)!\\&=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^{n}\frac{1}{n!}\right)\end{align*}$$ 이다.

정리: 교란수 $D_{n}$에 대하여 $D_{n}=(n-1)(D_{n-1}+D_{n-2})$이다.

증명: $D_{1}=0,\,D_{2}=1$이다. $n\geq3$일 때, 교란수 $D_{n}$은 다음의 두가지 경우로 나눌 수 있다.

(1) 첫번째 자리에 $k\,(2\leq k\leq n)$ 가 오고 $k$번째 자리에 $1$이 오는 경우: 이 때의 교란수는 $1$과 $k$를 제외한 나머지 수들의 교란수와 같으므로 이 경우는 $D_{n-2}$이다.

(2) 첫번째 자리에 $k\,(2\leq k\leq n)$가 오고 $k$번째 자리에 $1$이 오지 않는 경우: 첫번째 자리에 놓인 $k$를 제외하고 $1$을 $k$로 대체하면, $1$을 제외한 나머지 $n-1$개의 교란수와 같으므로 이 경우는 $D_{n-1}$이다.

$2\leq k\leq n$이므로 (1)과 (2)에 의해 $D_{n}=(n-1)(D_{n-1}+D_{n-2})$이다.

예: 어느 저녁 모임에 모자를 쓴 $n$명이 참석했다. 이들이 돌아갈 때 정전이 되어 자기 모자를 찾을 수 없었다. $n$명 각자가 모자를 하나씩 가지고 돌아갈 때, 이들 모두 자기 모자가 아닌 타인의 모자를 가지고 돌아가는 경우의 수는 $D_{n}$이다.

비둘기 집의 원리

정리(비둘기 집의 원리, pigeonhole principle): $n+1$마리의 비둘기를 $n$개의 비둘기 집에 넣으면, 적어도 비둘기가 2마리 이상 들어간 집이 반드시 존재한다.

증명: 만약 모든 비둘기집에 한 마리씩만 있다면 전체 비둘기의 수는 최대 $n$이 되는데 처음에 가정한 비둘기의 수가 $n+1$이므로 모순이다.

예: 8명 중 적어도 두 명은 같은 요일이 생일이다.

풀이: 8명 모두 다른 요일에 태어났다면 8개 이상의 요일이 있어야 한다. 그러나 요일은 최대 7개(월, 화, 수, 목, 금, 토, 일)이므로 모순이다.

예: 어느 테니스 선수가 30일 동안 매일 1게임 이상 연습게임을 하며 모두 45게임을 했다고 한다. 그러면 이 선수는 연속된 며칠 사이에 정확하게 14게임을 한 기간이 있다.

풀이: 선수가 처음 $k$일 동안 $a_{k}$회의 게임을 했다면, $$1\leq a_{1}<a_{2}<\cdots<a_{30}=45$$ 이므로 $$a_{1}+14<a_{2}+14<\cdots<a_{30}+14=45+14=59$$ 이고 $$S=\{a_{1},\,a_{2},\,,\cdots,\,a_{30},\,a_{1}+14,\,a_{2}+14,\,\cdots,\,a_{30}+14\}\subset\{1,\,2,\,\cdots,\,59\}$$ 이다.

비둘기집의 원리에 의해 $S$에는 같은 수가 존재한다. 그런데 $a_{1},\,a_{2},\,\cdots,\,a_{30}$들은 서로 다르므로 $a_{1}+14,\,a_{2}+14,\,\cdots,\,a_{30}+14$들도 서로 다르고 같은 수가 되려면 적당한 $1\leq i,\,j\leq 30\,(i\neq j)$에 대하여 $a_{i}+14=a_{j}$가 성립해야 한다. 따라서 $a_{j}-a_{i}=14$이므로 $i+1$일부터 $j$일까지 이 선수는 정확히 14게임을 했다.

예: 집합 $A=\{1,\,2,\,\cdots,\,2n\}$에서 임의로 $n+1$개의 원소를 선택하면 그 중에는 두 수의 차가 1이 되는 두 수가 있다.

풀이: $A$에서 선택한 $n+1$개의 원소를 $b_{1},\,b_{2},\,\cdots,\,b_{n+1}$이라 하자. $A$의 원소를 $n$개의 집합 $$\{1,\,2\},\,\{3,\,4\},\,\cdots\,\{2n-1,\,2n\}$$ 으로 나누면 $n+1$개의 수 $b_{1},\,b_{2},\,\cdots,\,b_{n+1}$가 이 $n$개의 집합에 속하므로 비둘기집의 원리에 의해 적당한 두 수 $b_{i},\,b_{j}\,(i\neq k)$는 같은 집합에 속하고 따라서 $|b_{i}-b_{j}|=1$이다.

참고자료:

조합론 및 그래프이론, 조성진, 김한두, 경문사

조합 및 그래프이론, 김정진, 교우사