앞으로 종종 각 문제가 다음 문제로 이어지는 일련의 문제를 나열할 것이다. 이들을 처음 읽을 때는 마지막 질문에 답할 수 없을지라도, 다른 질문들을 해결해보며 차분히 읽어나가면 마지막 질문에 대한 답도 “분명히” 눈에 보일 수 있을 것이다. 앞으로 \(\mathrm{A_{1}, A_{2}, A_{3}}\)는 각각 하나의 letter로 여긴다. 아마 먼저 세 개의 \(\mathrm{A}\)를 서로 다른 색의 \(\mathrm{A}\)로 여기고 나중에는 구별할 수 없는 \(\mathrm{A}\)로 여기는 것이 도움이 될 수 있을 것이다. 마찬가지로 먼저 \(\mathrm{E_{4}, E_{5}}\)를 서로 다른 색의 \(\mathrm{E}\)로 여겨 보아라.
- \(\mathrm{ABCDEF}\)의 \(6\)개의 letter들을 배열하는 경우의 수는?
- \(\mathrm{A_{1}A_{2}A_{3}E_{4}E_{5}}\)의 \(6\)개의 letter들을 배열하는 경우의 수는?
- \(\mathrm{A_{1}A_{2}A_{3}EEF}\)의 \(6\)개의 letter들을 배열하는 경우의 수는?
- \(\mathrm{AAAE_{4}E_{5}F}\)의 \(6\)개의 letter들을 배열하는 경우의 수는?
- \(\mathrm{AAAEEF}\)의 \(6\)개의 letter들을 배열하는 경우의 수는?
- \(\mathrm{BANANA}\)의 letter들을 배열하는 경우의 수는?
- \(\mathrm{AAABBCCCCD}\)의 letter들을 배열하는 경우의 수는?
- \(\mathrm{MATHEMATICS}\)의 letter들을 배열하는 경우의 수는?
- \(\mathrm{MISSISSIPPI}\)의 letter들을 배열하는 경우의 수는?
- \(\mathrm{A}\)가 \(4\)개, \(\mathrm{G}\)가 \(3\)개, \(\mathrm{U, V, W, X, Y, Z}\)가 각각 \(6\)개 씩 있을 때, 이를 배열하는 경우의 수는?
- 동일한 \(4\)권의 대수책, 동일한 \(3\)권의 기하책, 서로 다른 \(6\)권의 소설책이 있을 때, 이들을 책장 한 칸에 일렬로 배열하는 경우의 수는?
- 서로 다른 \(4\)권의 대수학 책, 서로 다른 \(3\)권의 기하학 책, 서로 다른 \(6\)권의 미적분학 책이 있을 때, 이들을 책장 한 칸에 일렬로 배열하되 같은 과목끼리는 함께 묶여 있도록하는 경우의 수는?
- \(r\)개의 \(\mathrm{C}\), \(n-r\)개의 \(\mathrm{R}\)을 갖는 \(n\)-letter word는 몇 개가 있는가?
- \(n\geq r\)일 때, \(n\)명의 사람 중 \(r\)명의 사람을 택하는 경우의 수는?
- \(n\geq r\)일 때, 서로 다른 \(n\)개의 대상에서 서로 다른 \(r\)개의 대상을 택하는 경우의 수는?
9번 문제를 해결하기 위해 먼저 \[ \begin{array}{cccc} \mathrm{M} & \mathrm{I} & \mathrm{S} & \mathrm{P} \\ & \mathrm{I} & \mathrm{S} & \mathrm{P} \\ & \mathrm{I} & \mathrm{S} & \\ & \mathrm{I} & \mathrm{S} & \end{array} \] 처럼 차례로 각 글자를, 글자마다 열로 구분지어 써보자. (이처럼 글자를 나열한 그림을 자주 사용하게 될 것이다.) 총 글자 수를 기억하기 위해 오른쪽 하단에 “\(11\)”이라 써 놓을 수도 있겠다. 각 열에는 \(1, 4, 4, 2\)개의 글자가 있으므로 구하는 답은 \(11!/(1!4!4!2!)\)임을 알 수 있다. 물론 분모의 “\(1!\)”는 생략해도 된다.
앞으로 5, 6, 7, 8, 9번과 같은 문제를 Mississippi problem이라 부르자. 이러한 문제는 더 큰 문제의 일부로 자주 등장하곤 한다. 이제 어떤 단어가 주어지든지 Mississippi problem은 잘 다룰 수 있다고 가정한다.
13번에서 \(\mathrm{C}\)를 “choose”로 생각하고, \(\mathrm{R}\)은 “reject”으로 생각하여, 13번의 해를 \(14\)번에 적용해보아라. 즉 \(n\)명의 사람을 일렬로 세워 놓고, 13번에서의 \(n\)-letter word 하나를 이 \(n\)명의 사람에서 \(r\)명의 사람을 택하는 경우 하나로 생각해 보아라.
\(15\)번의 각각의 선택을 \(n\)개의 원소의 \(r\)-조합(\(r\)-combination)이라 부른다.1 \(r\)-순열은 순서가 있는 반면 \(r\)-조합은 순서가 없다. \(r\)-조합 각각은 정확히 \(r!\)개의 \(r\)-순열과 대응함에 유의하자. 따라서 \(n\)개의 원소의 \(r\)-조합의 개수를 \(\binom{n}{r}\)로 나타내기로 하면 \(\binom{n}{r}r!\)은 반드시 \(n!/(n-r)!\), 즉 [\(n\)개의 원소의 \(r\)-순열의 개수]와 같아야만 한다. 종종 \(\binom{n}{r}\)은 “(the number of) combinations of \(n\) things taken \(r\) at a time”으로 읽으며 때로는 “\(n\) above \(r\)”로 읽기도 한다. \(n/r\)로 나타내는 “\(n\) over \(r\)”과 \(n\) above \(r\)은 서로 다른 것임에 유의하자. 무엇보다 \(\binom{n}{r}\)은 “\(n\) choose \(r\)”로 읽는 것이 가장 일반적이며 이같이 읽는 것을 추천한다.
관찰 서로 다른 \(n\)개의 대상의 \(r\)-조합의 개수는 \(n!/r!(n-r)!\)과 같으며 이를 \(\binom{n}{r}\)로 나타낸다. 우리나라 고등학교 교과서에서는 이를 \({}_{n}\mathrm{C}_{r}\)로 나타낸다. 즉 \[ \binom{n}{r}={}_{n}\mathrm{C}_{r}=\frac{n!}{r!(n-r)!} \] 이다. 명백히 \[ \binom{n}{r}=\binom{n}{n-r} \] 가 성립한다.
두 정수 \(n\)과 \(r\)이 \(0 < r < n\)를 만족시킬 때, 다음 관계식을 설명하는 이야기를 하나 생각할 수 있겠는가? \[ \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r} \] 앞으로 종종 등장할 우리의 편한 친구 Lucky Pierre를 소개하는 다음 이야기는 어떨런지? Lucky Pierre를 포함해서 총 \(n\)명이 있는 모임이 있는데, 이 모임의 구성원 중 \(r\)명으로 이루어진 위원회를 뽑는다고 해보자. 먼저 Lucky Pierre가 포함된 위원회를 뽑는 방법은 \(\binom{n-1}{r-1}\)가지가 있다. 그리고 Lucky Pierre가 포함되지 않는 위원회를 뽑는 방법은 \(\binom{n-1}{r}\)가지가 있다. 이 두 개의 수를 합한 것은 위원회를 뽑는 경우의 수인 \(\binom{n}{r}\)과 같아야만 한다. (물론 보이고자하는 등식의 양변을 각각 전개하여 보일 수도 있다.)
위에 나타낸 등식을 활용하면 아래의 표에 나타낸 것처럼 Pascal의 삼각형이라 부르는 배열을 계속 만들어 갈 수 있다. Pascal의 삼각형에서 \(1\)을 제외한 각 성분은 그 성분이 있는 위치 바로 위 왼쪽과 바로 위 오른쪽에 있는 두 정수의 합이다.
