MISSISSIPPI 문제

앞으로 종종 각 문제가 다음 문제로 이어지는 일련의 문제를 나열할 것이다. 이들을 처음 읽을 때는 마지막 질문에 답할 수 없을지라도, 다른 질문들을 해결해보며 차분히 읽어나가면 마지막 질문에 대한 답도 “분명히” 눈에 보일 수 있을 것이다. 앞으로 $A_{1}, A_{2}, A_{3}$ 는 각각 하나의 letter로 여긴다. 아마 먼저 세 개의 $A$ 를 서로 다른 색의 $A$ 로 여기고 나중에는 구별할 수 없는 $A$ 로 여기는 것이 도움이 될 수 있을 것이다. 마찬가지로 먼저 $E_{4}, E_{5}$ 를 서로 다른 색의 $E$ 로 여겨 보아라.

$ABCDEF$ 의 $6$ 개의 letter들을 배열하는 경우의 수는?
$A_{1} A_{2} A_{3} E_{4} E_{5}$ 의 $6$ 개의 letter들을 배열하는 경우의 수는?
$A_{1} A_{2} A_{3} EEF$ 의 $6$ 개의 letter들을 배열하는 경우의 수는?
${AAAE}_{4} E_{5} F$ 의 $6$ 개의 letter들을 배열하는 경우의 수는?
$AAAEEF$ 의 $6$ 개의 letter들을 배열하는 경우의 수는?
$BANANA$ 의 letter들을 배열하는 경우의 수는?
$AAABBCCCCD$ 의 letter들을 배열하는 경우의 수는?
$MATHEMATICS$ 의 letter들을 배열하는 경우의 수는?
$MISSISSIPPI$ 의 letter들을 배열하는 경우의 수는?

9번 문제를 해결하기 위해 먼저 $\begin{array}{cccc} M & I & S & P \\ I & S & P \\ I & S \\ I & S \end{array}$ 처럼 차례로 각 글자를, 글자마다 열로 구분지어 써보자. (이처럼 글자를 나열한 그림을 자주 사용하게 될 것이다.) 총 글자 수를 기억하기 위해 오른쪽 하단에 “ $11$ ”이라 써 놓을 수도 있겠다. 각 열에는 $1, 4, 4, 2$ 개의 글자가 있으므로 구하는 답은 $11! / (1! 4! 4! 2!)$ 임을 알 수 있다. 물론 분모의 “ $1!$ ”는 생략해도 된다.

앞으로 5, 6, 7, 8, 9번과 같은 문제를 Mississippi problem이라 부르자. 이러한 문제는 더 큰 문제의 일부로 자주 등장하곤 한다. 이제 어떤 단어가 주어지든지 Mississippi problem은 잘 다룰 수 있다고 가정한다.

$A$ 가 $4$ 개, $G$ 가 $3$ 개, $U, V, W, X, Y, Z$ 가 각각 $6$ 개 씩 있을 때, 이를 배열하는 경우의 수는?
동일한 $4$ 권의 대수책, 동일한 $3$ 권의 기하책, 서로 다른 $6$ 권의 소설책이 있을 때, 이들을 책장 한 칸에 일렬로 배열하는 경우의 수는?
서로 다른 $4$ 권의 대수학 책, 서로 다른 $3$ 권의 기하학 책, 서로 다른 $6$ 권의 미적분학 책이 있을 때, 이들을 책장 한 칸에 일렬로 배열하되 같은 과목끼리는 함께 묶여 있도록하는 경우의 수는?
$r$ 개의 $C$ , $n - r$ 개의 $R$ 을 갖는 $n$ -letter word는 몇 개가 있는가?

13번에서 $C$ 를 “choose”로 생각하고, $R$ 은 “reject”으로 생각하여, 13번의 해를 $14$ 번에 적용해보아라. 즉 $n$ 명의 사람을 일렬로 세워 놓고, 13번에서의 $n$ -letter word 하나를 이 $n$ 명의 사람에서 $r$ 명의 사람을 택하는 경우 하나로 생각해 보아라.

$n \geq r$ 일 때, $n$ 명의 사람 중 $r$ 명의 사람을 택하는 경우의 수는?
$n \geq r$ 일 때, 서로 다른 $n$ 개의 대상에서 서로 다른 $r$ 개의 대상을 택하는 경우의 수는?

$15$ 번의 각각의 선택을 $n$ 개의 원소의 $r$ -조합( $r$ -combination)이라 부른다.¹ $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} C_{r}$ 로 나타낸다. 즉 $(\binom{n}{r}) =_{n} 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$ 을 제외한 각 성분은 그 성분이 있는 위치 바로 위 왼쪽과 바로 위 오른쪽에 있는 두 정수의 합이다.

앞으로 '조합'이라고도 쓰고, 'combination'이라고도 쓸 것이다.

combination combinatorics Mississippi Problem Pascal's Triangle 조합 파스칼의 삼각형

비둘기집의 원리

행렬식과 체적

Leave a Comment Cancel Reply