중복조합

중복조합은 보통의 조합과 비슷하지만, 바탕이 되는 집합 M의 원소가 되풀이될 수 있다.

정의와 공식

좋은 예로 시작하자. 캠핑을 가려고 가게에서 음료수 열두 병을 사려고 한다. 진열대에는 서로 다른 음료수가 네 종류 있다. 음료수를 사는 방법은 여러 가지이다. 예를 들어 사이다 5병, 콜라 2병, 식혜 1병, 주스 4병을 살 수도 있고, 종류마다 세 병씩 살 수도 있다. 음료수를 모두 열두 병 사는 방법은 몇 가지일까?

바탕이 되는 집합은 M = {사이다, 콜라, 식혜, 주스}이고, 집합 M의 원소로 이루어지고 순서가 상관없는 k개(k = 12)의 묶음이 몇 가지인지 묻는 것이다.

공식을 이끌어 내는 과정은 다른 경우의 수 문제보다 조금 복잡하다. 먼저 장보기를 0과 1의 나열로 나타낸다. 1의 개수는 그 종류의 음료수를 산 병 수이고, 0은 종류 사이를 나눈다. 그래서 111011101111101은 사이다 세 병(처음 세 개의 1), 콜라 세 병(0이 구분자이고, 그다음 1 세 개), 식혜 다섯 병(0이 구분자이고, 그다음 1 다섯 개), 마지막으로 주스 한 병을 샀다는 뜻이다. 다음 그림이 원리를 보여 준다.

$$\underset{\text{사이다}}{\underbrace{111}}0\underset{\text{콜라}}{\underbrace{111}}0\underset{\text{식혜}}{\underbrace{11111}}0\underset{\text{주스}}{\underbrace{1}}$$

사이다 6병, 콜라 4병, 주스 2병을 사고 식혜는 사지 않는다면 나열은 다음과 같다.

$$\underset{\text{사이다}}{\underbrace{111111}}0\underset{\text{콜라}}{\underbrace{1111}}00\underset{\text{주스}}{\underbrace{11}}$$

이 나열의 길이는 언제나 15라는 것에 주목하자. 음료수를 모두 12병 사야 하므로 1이 12개 있어야 한다. 그리고 서로 다른 네 종류를 나누려면 구분자가 세 개 있어야 한다. 그러면 0을 정확히 세 개 포함하는 길이 15인 나열이 모두 몇 가지인지만 구하면 된다.

0의 위치만 정하면 된다. 12개의 1 사이에 0 세 개를 배치하면 음료수를 사는 방법 하나가 정해진다. 다시 말해 칸이 모두 15개 있고, 그 가운데 3개에 0을 넣어야 한다. 나머지 칸에는 저절로 1이 들어간다.

이제는 중복이 없는 간단한 조합 문제이다. 칸 15개에 번호 {1, …, 15}를 붙이고, 이 집합에서 수 세 개를 고르면 0을 넣을 위치 세 개가 정해진다. 예를 들어 조합 {2, 4, 7}이면 나열 101011011111111을 얻는다. 2번째, 4번째, 7번째 자리가 0이고 나머지는 1이다. 따라서 모두 다음과 같다.

$${}_{15}{\mathrm{C}}_3=455$$

즉 칸 15개에 0을 배치하는 방법은 455가지이고, 따라서 음료수가 네 종류일 때 음료수 12병을 사는 방법도 455가지이다.

앞의 생각을 일반화할 수 있다. 원소가 n개인 집합 M에서 원소가 되풀이될 수 있도록 k개를 고르면, 길이가 n + k − 1인 0과 1의 나열(1이 k개, 0이 n − 1개)을 만들고 0 n − 1개를 배치하는 방법의 수를 구하게 된다. 그래서 중복조합의 수를 {}_nH_k로 나타내면 다음과 같다.

$${}_n{\mathrm{H}}_k={}_{n+k-1}{\mathrm{C}}_{n-1}={}_{n+k-1}{\mathrm{C}}_k.$$

마지막 변형은 이항계수의 기본 관계 덕분에 할 수 있다.

풀이가 있는 예제

1. 영화 시사회 초대권 20장을 할머니 10명에게 나누어 주는 방법은 몇 가지일까? 할머니 한 명이 여러 장, 많게는 모든 초대권을 받을 수도 있으므로 중복조합 문제이다. n과 k가 무엇인지만 정확히 알면 된다. 실제로는 할머니 10명 가운데에서 중복을 허락하여 20번 고르는 중복조합이다. 다시 말해 1이 20개, 0이 9개인 길이 29의 나열을 만드는 것이다. 따라서 n = 10, k = 20이다. 결과는 다음과 같다.

$${}_{10}{\mathrm{H}}_{20}={}_{10+20-1}{\mathrm{C}}_{20}=\mathrm{10,015,005.}$$