[조합론] 2. 경우의 수 세기(1: 순열, 조합)

[조합론] 2. 경우의 수 세기(1: 순열, 조합)

두 집합$$\begin{align*}X&=\{x_{1},\,\cdots,\,x_{m}\}\\Y&=\{y_{1},\,\cdots,\,y_{n}\}\end{align*}$$에 대하여 \(X\cap Y=\emptyset\)이면, \(X\)와 \(Y\)는 서로 겹치는 원소를 갖지 않으므로 \(X\cup Y\)의 원소의 개수는 \(m+n\) 즉,$$|X\cup Y|=m+n=|X|+|Y|$$(\(|X|\)는 집합 \(X\)의 원소의 개수)이다.

만약 \(X\cap Y\neq\emptyset\)이고 \(|X\cap Y|=k\)이면,$$|X\cup Y|=m+n-k=|X|+|Y|-|X\cap Y|$$이다.

위 사실을 이용하여 다음의 덧셈법칙(addition principle)을 얻을 수 있다:

어떤 사건이 일어날 경우의 수가 \(n_{1}\)이고, 첫번째 사건과 교집합이 공집합인 두번째 사건이 일어날 경우의 수가 \(n_{2}\)이면, 첫번째 사건 또는 두번째 사건이 일어나는 경우의 수는 \(n_{1}+n_{2}\)이다. 일반적으로 첫번째 사건이 일어나는 경우의 수가 \(n_{1}\), 두번째 사건이 일어나는 경우의 수가 \(n_{2}\), ..., \(k\)번째 사건이 일어나는 경우의 수가 \(n_{k}\)이면, 이 사건들 중 정확히 하나의 사건이 일어나는 경우의 수는 \(n_{1}+n_{2}+\cdots+n_{k}\)이다.

예: 1부터 100까지 정수 중에서 2 또는 3의 배수의 개수는?

풀이: 2의 배수는 50개, 3의 배수는 33개 있고, 2와 3의 최소공배수는 6이므로 6의 배수는 16개 있다. 이 경우는 6의 배수가 중복되기 때문에 6의 배수의 개수를 빼주어야 하고 따라서$$50+33-16=67$$이 2 또는 3의 배수의 개수이다.

예: 어느 호텔식당에 중식 10가지, 일식 10가지가 있다. 이 식당에서 식사를 하는 경우의 수는?

풀이: 중식과 일식은 겹치지 않으므로$$10+10=20$$이 이 식당에서 식사를 하는 경우의 수 이다.

두 집합$$\begin{align*}X&=\{x_{1},\,\cdots,\,x_{m}\}\\Y&=\{y_{1},\,\cdots,\,y_{n}\}\end{align*}$$에 대하여$$X\times Y=\{(x_{1},\,y_{1}),\,(x_{1},\,y_{2}),\,\cdots,\,(x_{m},\,y_{n-1}),\,(x_{m},\,y_{n})\}$$이므로 \(|X\times Y|=|X||Y|=mn\)이다.

위 사실을 이용하여 다음의 곱셈법칙(multiplication principle)을 얻을 수 있다:

어떤 사건이 일어나는 경우의 수가 \(n_{1}\)이고, 그 사건 각각에 대하여 다른 사건이 일어나는 경우의 수가 \(n_{2}\)이면, 두 사건이 동시에 일어나는 경우의 수는 \(n_{1}\times n_{2}\)이다. 일반적으로 첫번째 사건이 일어나는 경우의 수가 \(n_{1}\), 그 각각에 대하여 두번째 사건이 일어나는 경우의 수가 \(n_{2}\), ..., \(k-1\)번째 일어나는 사건 각각에 대하여 \(k\)번째 사건이 일어나는 경우의 수가 \(n_{k}\)이면, 일어날 수 있는 모든 사건의 경우의 수는 \(n_{1}\times\cdots\times n_{k}\)이다. 

예: 자연수 \(n\)이 다음과 같이 소인수분해 될 때(\(p_{1},\,p_{2}\)는 소수), \(n\)의 양의 약수의 개수는?$$n=p_{1}^{a}p_{2}^{b}\,(\text{gcd}(p_{1},\,p_{2})=1,\,a,\,b\geq1)$$풀이: \(n\)의 약수는$$p_{1}^{i}p_{2}^{j}\,(0\leq i\leq a,\,0\leq j\leq b)$$의 형태이다.$$i=0,\,1,\,\cdots,\,a,\,j=0,\,1,\,\cdots,\,b$$이므로 \(i\)를 선택할 수 있는 방법은 \((a+1)\)가지, \(j\)를 선택할 수 있는 방법은 \((b+1)\)가지이다. 따라서 \(n\)의 약수의 개수는 \((a+1)(b+1)\)이다.

예: 집합 \(A=\{a,\,b,\,c\}\)에서 집합 \(B=\{0,\,1\}\)로의 함수의 개수는?

풀이: \(a\)의 함숫값은 \(0\) 또는 \(1\)이므로 \(a\)의 함숫값을 선택하는 경우의 수는 \(2\)이다. 마찬가지로 \(b\), \(c\)의 함숫값을 선택하는 경우의 수도 각각 \(2\)이므로 함수의 개수는 \(2\times2\times2=8\)이다.

예: 집합 \(A=\{1,\,2\,\cdots,\,n\}\)의 부분집합의 개수는?

풀이: \(A\)의 부분집합은 각 \(i\,(1\leq i\leq n)\)에 대하여 \(i\)가 들어있거나 그렇지 않을 수 있다. 아래의 그림에서

\(i\)가 포함되면 그 칸에 \(1\)을 넣고, 그렇지 않으면 \(0\)을 넣는 방법으로 \(A\)의 부분집합을 모두 나타낼 수 있다. 그러므로 \(A\)의 부분집합의 개수는 \(2\times\cdots\times2=2^{n}\)이다.

서로 다른 \(n\)개 중에서 \(r\)개를 선택해서 일렬로 나열한 것을 \(n\)개에서 \(r\)개를 선택한 순열(permutation)이라 하고, 그 개수를 \(_{n}P_{r}\)로 나타내고 이때$$\begin{align*}_{n}P_{r}&=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}\\(n!&=n(n-1)\cdots2\cdot1,\,0!=1)\end{align*}$$이다.

증명: \(n\)개에서 \(r\)개를 선택하는 순열의 수 \(_{n}P_{r}\)은 아래 그림대로 일렬로 나열된 \(r\)개의 자리에 \(r\)개의 서로 다른 원소를 배치하는 방법의 수와 같다.

따라서$$\begin{align*}_{n}P_{r}&=n(n-1)\cdots(n-(r-1))\\&=n(n-1)\cdots(n-r+1)\\&=\frac{n(n-1)\cdots(n-r+1)(n-r)!}{(n-r)!}\\&=\frac{n!}{(n-r)!}\end{align*}$$이다.

참고: \(_{n}P_{n}=n!\)

예: 10명의 학생으로 구성된 동아리에서 회장, 부회장, 서기를 뽑는 경우의 수는?

풀이: 10개 중 3개를 선택하는 순열의 수와 같고, 따라서 \(_{10}P_{3}=10\times9\times8=720\)이다.

예: 1부터 8까지의 자연수를 사용해서 다음의 조건을 만족하는 세자리 자연수를 만들 수 있는 방법의 수는?

(1) 자리의 숫자가 모두 다르다.

(2) 자리의 수가 모두 다르고 2를 반드시 포함해야 한다.

풀이:

(1): 8개의 숫자 중에서 3개를 선택해서 일렬로 나열하는 경우의 수와 같으므로 \(_{8}P_{3}=8\cdot7\cdot6=336\)이다.

(2): 2가 첫째, 둘째, 셋째자리 중 한 곳에 위치하고 각각의 경우의 수는 7개의 숫자 중 2개를 선택해 나열하는 경우의 수와 같으므로 \(3\times_{7}P_{2}=3\cdot7\cdot6=126\)이다.

(또는 자릿수가 서로 다른 세자리 자연수는 총 336개이고, 2를 아예 포함하지 않는 서로 다른 세자리 자연수는 총 210개이므로 \(336-210=126\)이다.)

서로 다른 \(n\)개 중에서 \(r\)개를 선택하는 것을 \(n\)개에서 \(r\)개를 선택한 조합(combination)이라 하고, 그 개수를 \(\displaystyle\binom{n}{r}\)(또는 \(_{n}C_{r}\))로 나타내고 이때$$\binom{n}{r}=\frac{_{n}P_{r}}{r!}=\frac{n!}{r!(n-r)!}$$이다.

증명: \(n\)개에서 \(r\)개를 선택하여 일렬로 나열하는 경우의 수(순열)는 \(_{n}P_{r}\)이고, \(n\)개에서 \(r\)개를 선택하는 경우의 수는 \(\displaystyle\binom{n}{r}\), 그 \(r\)개를 일렬로 나열하는 경우의 수는 \(r!\)이므로$$_{n}P_{r}=\binom{n}{r}r!$$이고 따라서$$\binom{n}{r}=\frac{_{n}P_{r}}{r!}=\frac{n!}{(n-r)!}\frac{1}{r!}=\frac{n!}{r!(n-r)!}$$이다.

참고:$$\begin{align*}\binom{n}{r}=\frac{n!}{r!(n-r)!}=\binom{n}{n-r}\end{align*}$$이고$$\binom{n}{0}=\binom{n}{n}=1$$이다.

\(n\)개에서 \(r\)개를 선택하는 순열의 수는 \(n\)개에서 \(r\)개를 선택하고, 그 \(r\)개를 일렬로 나열하는것까지 포함하지만

\(n\)개에서 \(r\)개를 선택하는 조합의 수는 \(n\)개에서 \(r\)개를 선택하는 선에서 끝난다.

정리

(1) \(r\leq n\)인 두 자연수 \(r,\,n\)에 대하여$$\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$$이 성립한다.

(2) \(i\leq k\leq n\)인 세 자연수 \(i,\,k,\,n\)에 대하여$$\binom{n}{k}\binom{k}{i}=\binom{n}{i}\binom{n-i}{k-i}$$가 성립한다.

증명:

(1): \(n\)개에서 \(r\)개를 선택하는 방법의 수 \(\displaystyle\binom{n}{r}\)은 다음의 두 경우로 나눌 수 있다.

(i) 특정 원소 하나가 뽑히지 않는 경우: 나머지인 \(n-1\)개 중에서 \(r\)개를 선택해야 하고, 이 경우의 수는 \(\displaystyle\binom{n-1}{r}\)이다.

(ii) 특정 원소 하나가 뽑히는 경우: 그 원소가 이미 뽑혔기 때문에 나머지인 \(n-1\)개 중에서 \(r-1\)개를 선택해야 하고, 이 경우의 수는 \(\displaystyle\binom{n-r}{r-1}\)이다.

(i)과 (ii)는 동시에 일어나지 않는 사건이므로$$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$이다.

(2): 다음 등식으로부터 성립한다.$$\binom{n}{k}\binom{k}{i}=\frac{n!}{k!(n-k)!}\frac{k!}{i!(k-i)!}=\frac{n!}{(n-k)!i!(k-i)!}=\frac{n!}{i!(n-i)!}\frac{(n-i)!}{(n-k)!(k-i)!}=\binom{n}{i}\binom{n-i}{k-i}$$

예: 한 평면 위에 25개의 점이 어느 세 개도 같은 직선 위에 있지 않게 놓여있다.

(1) 이 점들에 의해 몇개의 직선이 결정되는가?

(2) 이 점들에 의해 몇개의 삼각형(평면)이 결정되는가?

풀이:

(1) 서로 다른 두 점을 지나는 직선은 오직 하나뿐이므로 \(\displaystyle\binom{25}{2}=\frac{25!}{2!23!}=300\)개의 직선이 결정된다.

(2) 같은 직선위에 있지 않은 세 점은 하나의 삼각형(평면)을 결정하므로 \(\displaystyle\binom{25}{3}=\frac{25!}{3!22!}=2300\)개의 삼각형(평면)이 결정된다.

예: 4명의 남자와 7명의 여자 중 다음과 같이 몇명을 뽑는 경우의 수는?

(1) 남자 2명, 여자 3명

(2) 같은 수의 남자, 여자

(3) 특정한 사람 1명을 포함한 4명

(4) 적어도 2명의 여자를 포함한 4명

(5) 남자 2명, 여자 2명. 이때 특정한 남자 1명과 여자 1명은 동시에 뽑힐 수 없다.

풀이:

(1) \(\displaystyle\binom{4}{2}\binom{7}{3}=6\cdot35=210\)가지이다.

(2) 남자 여자 각각 \(k\)명을 뽑는 경우의 수는 \(\displaystyle\binom{4}{k}\binom{7}{k}\,(0\leq k\leq4)\)이므로$$\sum_{k=0}^{4}{\binom{4}{k}\binom{7}{k}}=1+4\cdot7+6\cdot21+4\cdot35+1\cdot35=330$$가지이다.

(3) 특정한 사람 1명을 이미 뽑았다고 가정하면 나머지 10명 중에서 3명을 선택하면 된다. 따라서 \(\displaystyle\binom{10}{3}=120\)가지이다.

(4) 여자를 \(k\,(2\leq k\leq4)\)명 뽑으면, 남자는 \(4-k\)명을 뽑아야 한다. 따라서$$\sum_{k=2}^{4}{\binom{7}{k}\binom{4}{4-k}}=21\cdot6+35\cdot4+35=301$$가지이다.

(5) 남자 여자 각각 2명씩 뽑는 경우의 수에서 특정한 남자와 특정한 여자가 뽑는 경우의 수를 빼면 된다. 따라서$$\binom{4}{2}\binom{7}{2}-\binom{3}{1}\binom{6}{1}=126-18=108$$가지이다.

참고자료:

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

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