[조합론] 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\)이다.

참고자료:

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

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