확률과 통계 > 수형도와 헤아림의 원리

이해 : 순열과 조합, 그리고 나눗셈과 곱셈의 관계

팩토리얼, 순열, 조합

팩토리얼 : $n$명을 일렬로 세우는 방법의 수는 $n!$이다.

$n$명을 일렬로 세우려면 먼저 맨 앞인 첫 번째 자리에 설 사람을 정해야 합니다. $n$명 중 한 사람을 택해 첫 번째 자리에 세우는 방법의 수는 $n$입니다.1이를 $\NCR n1$로 택하여 $1$로 배열하는 $\NCR n1 \times 1$이라 해석할 수도 있습니다. 이때 $n$명 중 누구를 맨 앞에 세우든 수형도의 모양이 같으므로, 이후 곱의 법칙을 적용할 수 있을 것입니다.
이제 두 번째로 설 사람을 정해야 하고, 그 방법의 수는 $n-1$입니다.2이를 $\NCR {n-1}1$로 택하여 $1$로 배열하는 $\NCR {n-1}1 \times 1$이라 해석할 수도 있습니다. 따라서 $n$명 중 두 명을 일렬로 세우는 방법의 수는 곱의 법칙에 의해 $n\times\left( n-1 \right) $입니다.
같은 방법으로 곱의 법칙을 반복적으로 적용하면 마지막 $n$번째 설 사람을 정해야 하고, 그 방법의 수는 $1$이므로 $n\times\left( n-1 \right) \times \cdots \times 2 \times1$입니다. 이처럼 $n$부터 $1$까지의 자연수의 곱은 경우의 수에서 자주 쓰이므로 $n!$이라 정의합니다.3$6!$까지는 자주 쓰이니 수를 외워두는 것도 좋습니다. 각각 다음과 같습니다. \[\begin{alignat*}{2} 2! &= 2,\: 3!=6,\: &&4!=24\\ 5!&=120, &&6!=720 \end{alignat*}\]

순열 : $n$명 중에서 $r$명을 택하여 일렬로 세우는 방법의 수는 $\NPR nr$이다.

$n$명 중에서 $r$명을 택하여 일렬로 세우는 방법의 수 $\NPR nr$은 $n!$의 수형도를 그리는 과정에서 $r$번째까지만 그리는 것과 같습니다. 따라서 $\NPR nr = n\times \left( n-1 \right)\times\cdots\times\left( n-r+1 \right) $이고, 이를 팩토리얼로 나타내면 $\NPR nr =\dfrac{n!}{\left( n-r \right) !}$입니다.4그러나 우리는 이 공식을 되도록 사용하지 않을 것입니다. 그 이유는 뒤에서 곧 배울 것입니다.

조합 : $n$명 중에서 $r$명을 택하는 방법의 수는 $\NCR nr$이다.

$n$개 중에서 $r$개를 택하는 방법의 수는 $\NCR nr= \dfrac{n!}{r! \left( n-r \right)!}$입니다. 공식이 유도된 과정은 나중에 설명할 것이니, 일단은 공식을 잘 외워둡시다.5빈칸 문제의 과정에서 저 공식을 정확히 암기해야 제대로 풀이할 수 있습니다. 실제 계산에서 조합을 어떻게 계산하는지 연습해볼 것입니다.
조합 : $\NCR nr = \NCR n{n-r}$ : 조합의 대칭성
$\NCR 62$와 $\NCR 64$를 생각해봅시다. $\NCR 62$는 `$6$개 중에서 $2$개를 택하는 방법의 수'를 의미합니다. 이는 곧 $6$개 중에서 택하기 싫은 $4$개를 정하는 방법의 수와 동일한 의미를 갖습니다. 그런데 밑줄은 곧 $\NCR 64$를 의미합니다. 따라서 $\NCR 62 = \NCR 64$입니다.

이를 일반화한 것이 $\NCR nr = \NCR n{n-r}$입니다. 단순히 조합의 정의에 대입하여 계산하면 참임을 알 수 있고, 실제 상황에도 잘 부합함을 알 수 있습니다.6또한 이 내용은 곧 두 종류만 있을 때의 같있순 을 해석하며 또 다시 다룰 것입니다.

조합의 공식과 대칭성을 이용한 조합 계산 방법
조합의 공식과 조합의 대칭성을 이용하면 $\NCR {11}9$와 $\NCR {11}{2}$에 대하여 다음과 같은 식을 얻을 수 있습니다. \[\begin{align*} \NCR {11} 9 = \dfrac{11!}{9!\left( 11-9 \right) !} = \dfrac{11!}{2!9!} = \dfrac{11!}{2! \left( 11-2 \right)!} = \NCR {11} 2 \end{align*}\] 이 중 가장 가운데 식에서 눈여겨보아야 할 것은, 분자의 $11!$과 분모의 $9!$이 서로 약분되어 분자에는 $11\times10$만 남고, 분자에는 $2!=2\times1$만 남는다는 것입니다. 따라서 $\NCR{11}{9}=\NCR{11}2=\dfrac{11\times 10}{2\times 1} = 55$라 계산하면 됩니다.
다음 조합을 계산하시오. \[\begin{align*} \thcn1\:\: \NCR 75\qquad \thcn2\:\: \NCR 85\qquad \thcn3\:\: \NCR 96\qquad \thcn4\:\: \NCR {10}8 \end{align*}\]
\[\begin{alignat*}{2} &\thcn1\:\: \NCR75 = \NCR72 = \dfrac{7\times 6}{2\times 1} = 21\quad &&\thcn2\:\: \NCR 85 = \NCR 83 = \dfrac{8\times 7\times 6}{3\times 2\times 1} = 56\\ &\thcn3\:\: \NCR96 = \NCR93 = \dfrac{9\times 8\times 7}{3\times 2\times 1}=84\quad &&\thcn4\:\: \NCR{10}{8} = \NCR{10}{2}=\dfrac{10\times 9}{2\times 1} = 45 \end{alignat*}\]

\section[순열($\NPR nr$)은 버린다. 택($\NCR nr$)하고 배열($r!$)할 뿐이다.]{순열($\NPR nr$)은 버린다. 선택($\NCR nr$)하고 배열($r!$)할 뿐이다.} 순열의 정의와 조합의 정의를 다시 찬찬히 읽어봅시다.

서로 다른 $n$개에서 $r \; (0\le r \le n)$개를 택하여 일렬로 나열하는 것을 `$n$개에서 $r$개를 택하는 순열'이라 하고, $\NPR nr$이라 나타냅니다.
서로 다른 $n$개에서 순서를 생각하지 않고 $r \; (0\le r \le n)$개를 택하는 것을 `$n$개에서 $r$개를 택하는 조합'이라 하고, $\NCR nr$이라 나타냅니다.
그런데 순열의 정의를 분석해보면, 두 가지의 행위가 잇달아 일어나고 있음을 알 수 있습니다. 바로 $n$개 중에서 $r$개를 택하는 행위와 그 $r$개를 일렬로 나열하는 행위입니다. 이 중 전자는 $\NCR nr$의 정의와 완전히 동일하고, 후자는 $r!$의 상황과 완전히 동일합니다. 즉 곱의 법칙에 의해 $\NPR nr = \NCR nr \times r! \cthcn1$라 말할 수 있습니다.

교과서에서는 순열을 먼저 배우고 조합을 나중에 배우므로 $\NCR nr = \dfrac{\NPR nr}{r!} \cthcn2$이라 배우지만, 사실 의미상으로 더 자연스러운 수식은 ②보다는 ①입니다.7우리가 이렇게 느끼는 이유는, 곱의 법칙(경우의 수에서 곱셈의 의미)은 배웠지만 몫의 법칙(경우의 수에서 나눗셈의 의미)은 배우지 않았기 때문입니다. 따라서 이 책에서는 보다 자연스러운 풀이를 위하여 순열을 사용하지 않을 것입니다.8대신 사칙연산, 거듭제곱, 조합, 팩토리얼만을 사용합니다.

$\div n$은 `다른 것 $n$개'를 `같은 것 $1$개'로 간주하는 것(축소)이다.

예를 들어, $\mrm{A, \, B, \, C}$ 중에서 $2$개를 택하여 배열하는 경우는 $\mrm{AB, \, BA, \, BC, \, CB, \, AC, \, CA}$로 여섯 가지가 있습니다. 이를 `어떤 두 개를 택하였는가'를 기준으로 수형도로 나타내면 위와 같습니다. 이 상태에서 나눗셈 $\div 2$를 하는 것은, 수형도에서는 세 개의 마디 `$\mrm{A}$와 $\mrm{B}$ 선택', `$\mrm{B}$와 $\mrm{C}$ 선택', `$\mrm{C}$와 $\mrm{A}$ 선택'에 각각 달린 두 개($2!$개)의 가지를 모두 잘라냄으로써 무엇을 택하였는가만 세려는 의도로 생각할 수 있습니다.

$\times n$은 `같은 것 $1$개'를 `다른 것 $n$개'로 간주하는 것(증폭)이다.

거꾸로 $\mrm{A, \, B, \, C}$ 중에서 $2$개를 택하는 경우만 수형도로 나타내면 위와 같습니다. 이 상태에서 곱셈 $\times 2$를 하는 것은, 수형도의 각 마디에 두 개씩($2!$개씩) 가지를 새로 그려 두 개를 택하고, 택한 두 문자를 어떻게 배열하는가까지 고려하여 세는 것으로 생각할 수 있습니다.

이와 같이 순열과 조합의 관계를 통해 $\NPR nr$에 $\div r!$함으로써 $r!$배만큼 수형도가 축소되어 $\NCR nr$이 되고, $\NCR nr$에 $\times r!$함으로써 $r!$배만큼 수형도가 증폭되어 $\NPR nr$이 됨을 알 수 있었습니다. 배운 내용을 바탕으로, 앞서 두 번이나 풀이한 문제를 살짝 변형한 다음 문제를 풀어봅시다. 참고로, 원래 문제는 정답이 $30$이었습니다.

여섯 개의 알파벳 $\mrm{A}$, $\mrm{a}$, $\mrm{B}$, $\mrm{b}$, $\mrm{C}$, $\mrm{c}$를 일렬로 나열하여 문자열을 만든다. $\mrm{A}$와 $\mrm{a}$는 서로 이웃하지 않고, $\mrm{B}$와 $\mrm{b}$는 서로 이웃하지 않고, $\mrm{C}$와 $\mrm{c}$는 서로 이웃하지 않도록 배열된 문자열의 개수를 구하시오.
[여섯 개의 알파벳 $\mrm{A}$, $\mrm{a}$, $\mrm{B}$, $\mrm{b}$, $\mrm{C}$, $\mrm{c}$를 일렬로 나열하여 문자열을 만든다. $\mrm{A}$와 $\mrm{a}$는 서로 이웃하지 않고, $\mrm{B}$와 $\mrm{b}$는 서로 이웃하지 않고, $\mrm{C}$와 $\mrm{c}$는 서로 이웃하지 않도록 배열된 문자열의 개수를 구하시오.]
$\mrm{A}$, $\mrm{a}$, ㄴ, ㄴ, ㄷ, ㄷ을 일렬로 나열한다면, 하나의 경우의 수가 두 가지의 경우의 수로 증폭됩니다. 예를 들어, 하나의 경우 ㄱㄴㄷㄱㄴㄷ는 두 가지의 경우 $\mrm{A}$ㄴㄷ$\mrm{a}$ㄴㄷ, $\mrm{a}$ㄴㄷ$\mrm{A}$ㄴㄷ로 증폭됩니다. 따라서 ㄱㄱ 대신 $\mrm{A}$$\mrm{a}$로 바뀐 상황에서는 원래 수형도의 끝이 모두 새로운 마디가 되어 각자 $2$개의 가지를 새로 뻗어냄을 알 수 있습니다. 그러므로 $\mrm{A}$, $\mrm{a}$, ㄴ, ㄴ, ㄷ, ㄷ를 일렬로 나열하는 경우의 수는 $30 \times 2 = 60$입니다.
같은 논리로 ㄴㄴ과 ㄷㄷ를 각각 $\mrm{B}$$\mrm{b}$와 $\mrm{C}$$\mrm{c}$로 대체하면 역시 각각 두 개의 가지를 새로 뻗어나가게 됩니다. 따라서 구하는 경우의 수는 $30\times2\times2\times2=240$입니다.

이와 같은 곱셈과 나눗셈의 원칙을 정확히 이해해야만 고난도 경우의 수 문제를 잘 풀이할 수 있고, 향후 확률을 정확히 이해할 수 있습니다.

  1. 1. 이를 $\NCR n1$로 택하여 $1$로 배열하는 $\NCR n1 \times 1$이라 해석할 수도 있습니다.
  2. 2. 이를 $\NCR {n-1}1$로 택하여 $1$로 배열하는 $\NCR {n-1}1 \times 1$이라 해석할 수도 있습니다.
  3. 3. $6!$까지는 자주 쓰이니 수를 외워두는 것도 좋습니다. 각각 다음과 같습니다. \[\begin{alignat*}{2} 2! &= 2,\: 3!=6,\: &&4!=24\\ 5!&=120, &&6!=720 \end{alignat*}\]
  4. 4. 그러나 우리는 이 공식을 되도록 사용하지 않을 것입니다. 그 이유는 뒤에서 곧 배울 것입니다.
  5. 5. 빈칸 문제의 과정에서 저 공식을 정확히 암기해야 제대로 풀이할 수 있습니다.
  6. 6. 또한 이 내용은 곧 두 종류만 있을 때의 같있순 을 해석하며 또 다시 다룰 것입니다.
  7. 7. 우리가 이렇게 느끼는 이유는, 곱의 법칙(경우의 수에서 곱셈의 의미)은 배웠지만 몫의 법칙(경우의 수에서 나눗셈의 의미)은 배우지 않았기 때문입니다.
  8. 8. 대신 사칙연산, 거듭제곱, 조합, 팩토리얼만을 사용합니다.