중복조합

서로 다른 \(n\)개의 물건에서 중복을 허용하여 \(r\)개를 선택하는 경우의 수를 찾아보려 한다. 이를 위해 Mississippi problem을 활용할 것이다. 먼저 다음의 기초적인 문제의 답을 확실히 할 수 있어야 한다.

• 기둥들을 일렬로 세워 울타리를 만드는데, 인접한 두 기둥은 \(2\)m만큼 떨어져있게 심고, 맨 끝의 기둥 끼리는 \(20\)m만큼 떨어져 있게한다고 할 때, 기둥이 총 몇 개 필요한가?
• 일렬로 있는 \(10\)개의 물건을 서로 분리하기 위해, 몇 개의 칸막이가 필요한가?

이러한 “bullet problems”는 모양을 바꿔가며 계속해서 등장하곤 한다. 그 질문에 대한 마땅한 답은 없다. 언제 \(1\)을 더하고 언제 \(1\)을 빼야하나?

다음 \(10\)개의 질문을 살펴볼 때 주목해야하는 중요한 점은 첫 번째 질문 이후에 따라오는 각 질문은 바로 위의 질문과 동일한 답을 갖는다는 것이다. 따라서 어려워보이는 마지막 질문이 쉬워보이는 첫 번째 질문과 동일한 답을 갖는다는 것을 안다.

1. \(3\)개의 \(\mathrm{D}\)와 \(7\)개의 \(\mathrm{U}\)로 이루어진 word는 몇 개인가? (\(\mathrm{D}\)는 Dividers에서, \(\mathrm{U}\)는 Units에서 따왔다.)
2. \(3\)개의 \(\vert\)와 \(7\)개의 \(\star\)로 이루어진 열은 몇 개인가? (Bar와 Star를 생각하라.)
3. \(3\)개의 \(+\)와 \(7\)개의 \(1\)로 이루어진 열은 몇 개인가?
4. 방정식
\[ x_{1}+x_{2}+x_{3}+x_{4}=7 \] 의 음이 아닌 정수해는 몇 개인가?

예를 들어 \(3\)번에서의 하나의 열 \(1\ 1\ 1\ +\ +\ 1\ 1\ +\ 1\ 1\)은 \(4\)번에서의 하나의 해 \(3+0+2+2=7\)에 대응된다. 마찬가지로 \(4\)번에서의 \(0+0+2+5=7\)은 \(3\)번에서의 \(+\ +\ 1\ 1\ +\ 1\ 1\ 1\ 1\ 1\)에 대응된다. 이 대응은 \(4\)번의 답이 \(3\)의 답과 일치함을 보여준다.

미지수 \(x_{1}, x_{2}, x_{3}, x_{4}\)를 일렬로 있는 상자들로 생각하여, 이들 상자에 \(7\)개의 \(1\)을 넣는 것으로 생각할 수 있으며 이로부터 \(4\)번과 \(5\)번의 답이 일치함을 알 수 있다. 아마도 이러한 관찰이 없었다면 \(5\)번의 답을 찾기가 어려웠을 수 있겠다. 지금 나열하고 있는 질문들이 모두 동일한 답을 갖는다는 것을 다시 한 번 상기하자.

5. 일렬로 나열된 \(4\)개의 상자에 \(7\)개의 공을 넣는 경우의 수는?
6. 서로 다른 \(4\)개의 상자에 \(7\)개의 공을 넣는 경우의 수는?
7. 오렌지 \(7\)개를 \(4\)명의 어린이에게 나눠주는 경우의 수는?
8. 동일한 카드 \(7\)개를 “I CHOOSE YOU”라 말하며 \(4\)명의 사람에게 나눠주는 경우의 수는?
9. \(4\)종류의 과일들이 각 종류마다 충분히 많이 있다고 할 때, \(7\)개의 과일을 뽑는 경우의 수는?
10. 서로 다른 \(4\)개의 대상에서 중복을 허용하여 \(7\)개를 택하는 경우의 수는?

이제 다음 \(10\)개의 질문을 살펴보자. 이들은 위의 질문들에서 \(4\)와 \(7\)을 각각 \(n\)과 \(r\)로 바꿔쓴 것이다. 다시 한 번 지금 나열하고 있는 질문들이 모두 동일한 답을 갖는다는 것을 상기하자. 우리는 자명한 Mississippi problem에서 시작하여 목표를 이루는 것이다.

1. \((n-1)\)개의 \(\mathrm{D}\)와 \(r\)개의 \(\mathrm{U}\)로 이루어진 word는 몇 개인가?
2. \((n-1)\)개의 \(\vert\)와 \(r\)개의 \(\star\)로 이루어진 열은 몇 개인가?
3. \((n-1)\)개의 \(+\)와 \(r\)개의 \(1\)로 이루어진 열은 몇 개인가?
4. 방정식
\[ x_{1}+x_{2}+x_{3}+\cdots +x_{n-1}+x_{n}=r \] 의 음이 아닌 정수해는 몇 개인가?
5. 일렬로 나열된 \(n\)개의 상자에 \(r\)개의 공을 넣는 경우의 수는?
6. 서로 다른 \(n\)개의 상자에 \(r\)개의 공을 넣는 경우의 수는?
7. 오렌지 \(r\)개를 \(n\)명의 어린이에게 나눠주는 경우의 수는?
8. 동일한 카드 \(r\)개를 “I CHOOSE YOU”라 말하며 \(n\)명의 사람에게 나눠주는 경우의 수는?
9. \(n\)종류의 과일들이 각 종류마다 충분히 많이 있다고 할 때, \(r\)개의 과일을 뽑는 경우의 수는?
10. 서로 다른 \(n\)개의 대상에서 중복을 허용하여 \(r\)개를 택하는 경우의 수는?

마지막 \(10\)번 문제의 답은 \(1\)번 문제의 답과 일치하며 이는 사실 매우 쉬운 Mississippi 문제의 답이다. 그 답은 \(\frac{(n-1+r)!}{r!(n-1)!}\)이며 이는 \(\binom{n+r-1}{r}\)로 쓸 수 있음을 주목하자. 이로부터 다음을 얻는다.

이 관찰에서 얻은 공식은 \(\binom{n+r-1}{r}\)의 의미를 알고 있다면 기억만할 가치가 있다. 이 관찰을 토대로 아래의 표를 얻는다.

표기법에 관한 몇 가지 첨언을 하고자 한다. “\(\binom{n+r-1}{r}\)”를 “\(n\) choose \(r\) with repetition”이라 읽을 수 있다. 또한 우리나라 고등학교에서는 이를 “중복조합”이라고 부른다.¹ 여기서 “selecting with repetition”, 그리고 “중복”을 이야기할 때는 선택을 함에 있어서 중복이 허용된다(allowed)는 뜻이지 선택에 있어서 중복이 요구된다(requiresd)는 뜻은 아니다. 오렌지, 바나나, 복숭아, 사과들이 있을 때, 과일 \(3\)개를 중복을 허용하여 선택할 때, 오렌지 \(3\)개를 선택할 수도 있고 혹은 오렌지 \(1\)개, 바나나 \(1\)개, 복숭아 \(1\)개를 선택할 수도 있다. 이때의 가능한 선택은 몇 가지인가? 그 답은 \(20\)이나 \(\binom{6}{3}\)이나 \(\binom{4+3-1}{3}\) 중 어느 것으로 써도 무방하지만, 공부하는 입장에서는 가장 많은 정보를 드러내는 맨 마지막 형태를 선호한다. 또한 “picking with replacement”와 “picking with repetition”은 언어는 다르게 표현되었지만 수학적으로는 동일한 뜻임에 유의하자. 하나의 카드 덱에서 \(5\)개의 카드를 뽑는 경우의 수는 카드를 하나 뽑은 후에 카드가 탁자 위에서 교체된다면 물론 \(\binom{52+5-1}{5}\)이다. 아이스크림 콘을 고를 때의 언어는 “with replacement”이 아니라 “with repetition”을 써야하는 것 같다.

셈하기 문제에서 wedge \({}_{\wedge}\)가 아주 요긴한 도구임을 알고 있다. 다음 문제에서 wedge를 활용하는 예를 추가로 살펴본다. 단어 \[ \mathrm{NASHVILLETENNESSEE} \] 에 있는 글자를 일렬로 나열할 때, 처음의 \(\mathrm{N}\)이 처음의 \(\mathrm{S}\)보다 앞에 있고, 처음의 \(\mathrm{E}\)가 \(\mathrm{T}\)보다 앞에 있게 나열하는 경우의 수는?

어떤 순서로 글자를 두며 배열하느냐에 따라 이 문제를 공략하는 여러 가지 접근 방법을 말할 수 있다. 어느 경우든 다음 그림을 만드는 것으로 시작할 수 있겠다. \[ \begin{array}{ccccccccc} \mathrm{N} & \mathrm{A} & \mathrm{S} & \mathrm{H} & \mathrm{V} & \mathrm{I} & \mathrm{L} & \mathrm{E} & \mathrm{T} \\ \mathrm{N} & & \mathrm{S} & & & & \mathrm{L} & \mathrm{E} & \\ \mathrm{N} & & \mathrm{S} & & & & & \mathrm{E} & \\ & & & & & & & \mathrm{E} & \\ & & & & & & & \mathrm{E} & \end{array} \] 먼저 \(3\)개의 \(\mathrm{N}\)과 \(3\)개의 \(\mathrm{S}\)를 배열하는 문제를 생각해보자. 우선 \(3\)개의 \(\mathrm{S}\)를 쓰는 것으로 시작하는데 이는 한 가지 방법으로 쓸 수 있다. 이어서 그림 \({}_{\wedge}\mathrm{S}_{\wedge}\mathrm{S}_{\wedge}\mathrm{S}_{\wedge}\)를 보면 \(3\)개의 \(\mathrm{N}\)를 써넣을 수 있는 공간을 \(4\)개의 wedge들이 나타내고 있다고 생각할 수 있다. 주어진 조건에 따라 가장 왼쪽의 공간에는 적어도 하나의 \(\mathrm{N}\)을 써넣어야 한다. 따라서 이에 맞게 \(\mathrm{N}\)과 \(3\)개의 \(\mathrm{S}\)를 둔 그림 \(\mathrm{N}_{\wedge}\mathrm{S}_{\wedge}\mathrm{S}_{\wedge}\mathrm{S}_{\wedge}\)를 고려하여 남은 두 개의 \(\mathrm{N}\)을 써넣을 wedge를 선택하는 것을 생각하면 된다. (\(\mathrm{N}\)의 왼쪽에는 왜 wedge가 없는가?) 남은 두 개의 \(\mathrm{N}\)을 wedge에 써넣는 경우의 수는 \(\binom{4+2-1}{2}\)이다.

한편 \(\mathrm{N}\)을 먼저 한 가지 방법으로 정렬한 후, 그림 \(\mathrm{N}_{\wedge}\mathrm{N}_{\wedge}\mathrm{N}_{\wedge}\)에서 \(3\)개의 \(\mathrm{S}\)를 배열하는 경우의 수를 구하는 방식으로 접근해도 된다. 이 방식에 따라 계산하여 \(\binom{3+3-1}{2}\)를 얻는다.

또한 완전히 다른 접근방식으로 \(\mathrm{N}\)을 맨 앞에 고정시켜두고, 남은 두 개의 \(\mathrm{N}\)과 \(3\)개의 \(\mathrm{S}\)를 배열하는 Mississippi 문제를 생각하는 것으로 이에 따라 구하는 수가 \(\frac{5!}{2!3!}\)임을 바로 얻을 수 있다. 물론 \(\binom{4+2-1}{2}, \binom{3+3-1}{2}, \frac{5!}{2!3!}\)는 모두 동일한 수를 나타내며 조건에 따라 \(3\)개의 \(\mathrm{N}\)과 \(3\)개의 \(\mathrm{S}\)를 배열하는 경우의 수가 \(10\)임을 얻는다.

이때, 예를 들어, \(\mathrm{N}\)과 \(\mathrm{S}\)들이 그림 \({}_{\wedge}\mathrm{N}_{\wedge}\mathrm{N}_{\wedge}\mathrm{S}_{\wedge}\mathrm{S}_{\wedge}\mathrm{S}_{\wedge}\mathrm{N}_{\wedge}\)과 같이 있을 때, \(\mathrm{T}\)와 \(\mathrm{E}\)가 어디에 있을 수 있는지 살펴보자. 먼저 \(\mathrm{T}\)는 한 개, \(\mathrm{E}\)는 다섯 개인데, \(7\)개의 wedge 중 이 \(6\)개의 글자를 써넣을 wedge를 택하는 경우의 수가 \(\binom{7+6-1}{6}\)임을 얻는다. 그리고 이 선택된 wedge들에 \(\mathrm{T}\)와 \(\mathrm{E}\)를 넣는 경우의 수는, 주어진 \(\mathrm{T}\)의 위치에 관한 조건에 의하여 \(\mathrm{E}_{\wedge}\mathrm{E}_{\wedge}\mathrm{E}_{\wedge}\mathrm{E}_{\wedge}\mathrm{E}_{\wedge}\)를 고려하여, \(\binom{5}{1}\)임을 알 수 있다. 이제 지금까지 배열하는 경우의 수를 센 \(12\)-letter word가, 예를 들어, \({}_{\wedge}\mathrm{N}_{\wedge}\mathrm{N}_{\wedge}\mathrm{S}_{\wedge}\mathrm{T}_{\wedge}\mathrm{S}_{\wedge}\mathrm{E}_{\wedge}\mathrm{E}_{\wedge}\mathrm{S}_{\wedge}\mathrm{N}_{\wedge}\mathrm{E}_{\wedge}\mathrm{E}_{\wedge}\mathrm{E}_{\wedge}\)와 같이 있다고 하자. \(13\)개의 wedge들에 \(6\)개의 글자를 배열할 곳을 택하는 경우의 수는 \(\binom{13+6-1}{6}\)이며, 이 선택된 \(6\)개의 wedge에 남은 \(6\)개의 글자를 배열하는 것은 Mississippi 문제로 그 경우의 수가 \(\frac{6!}{2!}\)임을 얻는다. 따라서 최종적으로 우리가 구하는 답은 \[ 1\binom{3+3-1}{2}1\cdot\binom{7+6-1}{6}\binom{5}{1}\cdot\binom{13+6-1}{6}\frac{6!}{2!} \] 임을 알 수 있다.

Problems for Class.

1. 주사위 \(k\)개를 한꺼번에 던졌을 때, 결과는 몇 가지인가?
2. 알파벳 순서대로 이루어진 \(4\)-letter word는 몇 개인가?
3. 남자 \(10\)명과 여자 \(7\)명을 일렬로 앉히되 이웃하여 앉는 두 명의 여자가 없도록 앉히는 경우의 수는?
4. 남자 \(10\)명과 여자 \(7\)명을 원탁에 앉히되 이웃하여 앉는 두 명의 여자가 없도록 앉히는 경우의 수는?
5. RECURRENCERELATION의 글자를 배열하되 모음은 이웃하지 않도록 배열하는 경우의 수는?
6. RECURRENCERELATION의 글자를 배열하되 모음은 알파벳 순서대로 배열하는 경우의 수는?
7. 오직 A, B, C, D들만 이용하여 만든 \(5\)-letter word 중 단어 BAD를 포함하지 않는 \(5\)-letter word는 몇 개인가?
8. Peter와 Paul을 포함한 \(8\)명의 사람을 일렬로 앉히되 Peter와 Paul은 서로 이웃하지 않도록 앉히는 경우의 수는?
9. Peter와 Paul을 포함한 \(8\)명의 사람을 원탁에 앉히되 Peter와 Paul은 서로 이웃하지 않도록 앉히는 경우의 수는?
10. 총 \(n\)개의 나라에서 온 \(4\)명의 사람을 일렬로 앉히되 같은 나라에서 온 사람끼리는 이웃하지 않도록 앉히는 경우의 수는?
11. 서로 구별되는 \(20\)개의 장난감을 \(5\)명의 어린이 각각에게 \(4\)개씩 나눠주는 경우의 수는?
12. 총 \(18\)명의 사람을 각각 \(5\)명, \(6\)명, \(7\)명으로 이루어진 세 개의 조로 나누는 경우의 수는?
13. 총 \(18\)명의 사람을 \(6\)명으로 이루어진 세 개의 조로 나누는 경우의 수는?
14. \(7\)개의 R과 \(11\)개의 B를 배열하되 서로 이웃한 R이 없도록 배열하는 경우의 수는?
15. MISSISSIPPI의 글자를 배열하되 이웃한 I는 없도록 배열하는 경우의 수는?
16. 방정식
\[ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=67 \] 의 음이 아닌 정수해의 개수는?
17. \(30\)개의 초록색 공을 \(4\)명에게 분배할 때, Alice와 Eve가 받은 공의 개수의 합이 \(20\)을 넘지 않고 Lucky는 적어도 \(7\)개의 공을 받는 경우의 수는?
18. \(7\)개의 A, \(8\)개의 B, \(9\)개의 C에서 \(18\)개의 글자를 뽑는 경우의 수는?

Ten Problems for Homework.

1. 알파벳 순서대로 배열된 \(4\)-letter words는 몇 개인가?
2. 알파벳 순서대로 배열된 \(4\)-letter words 중 중복된 글자가 없는 것은 몇 개인가?
3. \(5\)장의 포커 카드를 받을 때, \(2\) pair를 받는 경우의 수는?
4. \(4\)-letter words 중 중복된 글자가 없으며 가운데 글자가 모음인 것은 몇 개인가?
5. MISSISSIPPI의 글자를 배열할 때, 적어도 두 개의 I가 인접하도록 배열하는 경우의 수는?
6. \(1\)부터 \(12\)까지의 수가 각 면에 하나씩 적혀있는 정십이면체 주사위 한 쌍을 던졌을 때, 결과는 몇 가지인가?
7. 총 \(18\)명의 사람을 각각 \(5\)명, \(5\)명, \(4\)명, \(4\)명으로 이루어진 네 개의 조로 나누는 경우의 수는?
8. 서로 구별되는 \(mn\)개의 물건을 각각 \(n\)개씩의 물건으로 이루어진 \(m\)개의 묶음으로 분류하는 경우의 수는?
9. \(5\)개의 오랜지와 \(7\)개의 사과 중 몇 개를 택하여 하나의 접시에 담는 경우의 수는?
10. \(3\)개의 A, \(3\)개의 B를 이용하여 만들 수 있는 word의 개수는? (단, word는 적어도 하나의 글자는 포함하여야 한다.)

독자는 아마도 “\(n\) choose \(r\) with repetition”을 나타내는 기호를 하나 정하고 싶어졌을 것이다. 새로운 기호를 이제야 도입하는 것은, 물론, “\(n\) choose \(r\) with repetition”을 말할 때마다, \(\binom{n+r-1}{r}\)을 떠올리게 하려는 의도이다. 아래의 다섯 문제를 지금 도입한 새로운 기호 없이 풀어보는 것도 좋다. 어쨋든, “\(n\) choose \(r\) with repetition”을 나타내는 기호를 \[ \left\langle\!{{n}\atop{r}}\!\right\rangle=\binom{n+r-1}{r} \] 로 정의한다. 참고로 우리나라 학교수학에서는 \(\left\langle\!{{n}\atop{r}}\!\right\rangle\)을 주로 \({}_{n}\mathrm{H}_{r}\)로 나타내며 이를 '서로 다른 \(n\)개에서 \(r\)개를 택하는 중복조합'이라한다. 즉 \[ {}_{n}\mathrm{H}_{r}=\left\langle\!{{n}\atop{r}}\!\right\rangle=\binom{n+r-1}{r}={}_{n+r-1}\mathrm{C}_{r} \] 이다.

Five Problems for Homework.

1. MISSISSIPPI의 글자들을 배열할 때, P가 S와 인접하지 않도록 배열하는 경우의 수는? (힌트: 사실상 동일한 문제임에도 불구하고 S가 P와 인접하지 않는 배열을 고려하는 것이 훨씬 쉽다.)
2. 방정식
\[ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=32 \] 의 음이 아닌 정수해의 개수는?
3. 방정식
\[ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=32 \] 의 양의 정수해의 개수는?
4. 부등식
\[ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}<32 \] 의 양의 정수해의 개수는? (힌트: \(x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}=32\)을 생각해보라.)
5. 부등식
\[ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}<32 \] 의 음이 아닌 정수해의 개수는?

1. 중복을 허용한 순서를 고려한 선택은 “중복순열”이라 부른다.