중복조합

중복조합이란 중복을 허용해서 조합하는 것이다.

일반적인 조합(${}_n\mathrm{C}_r$)은 중복을 허용하지 않는다. 가령 A, B, C 중 2개를 고를 때 AB나 BC만 가능하여 AA를 고를 수는 없다.

하지만 중복조합은 이미 고른 것을 또 고르는 것이 가능하다. A, B, C를 중복조합으로 조합하면 다음과 같이 여섯 가지 경우가 있다.

AA, AB, AC, BB, BC, CC

 

중복조합은 다음과 같이 표기한다.

$n$개중 $r$개를 중복을 허용하여 뽑는 경우의 수는 ${}_n\mathrm{H}_r$이다.

중복조합은 조합으로 바꾸어 계산하며 바꾸는 방법은 다음과 같다.

${}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r$

이것이 성립하는 이유는 다음과 같다.

 

가령 4개의 공을 뽑는다고 해보자. 공은 빨간색, 파란색, 노란색이 있으며, 각 색깔의 공은 한 천 개쯤 있다. 같은 색의 공은 구분되지 않는다.

우리는 이 상황을 공을 뽑는 대신 4개의 흰 공을 일렬로 놓고 몇 개는 빨간색, 몇개는 파란색, 또 몇개는 노란색으로 색칠하는 것으로 생각할 수 있다.

어차피 몇 번째 공이 어떤 색으로 칠해지는가는 중요한 것이 아니기 때문에 생각을 편하게 하기 위해 흰 공 사이에 칸막이를 두어 구분된 각 칸들을 같은 색으로 칠하기로 약속하자.

위 그림은 흰색 공 사이에 두 개의 칸막이를 두고 나눠진 각 칸을 빨강, 파랑, 노랑으로 칠한 것이다. 만약 칸막이를 다른 곳에 설치하면 각 공에 칠해지는 색은 달라질 것이다. 그리고 하나의 칸막이 배치는 하나의 공을 조합하는 경우와 대응된다. 가령 위의 예시에서는 빨간 공 하나, 파란 공 하나, 노란 공 두 개로 조합되었다.

 

칸막이로 공을 나누는 방법의 수는 똑같은 칸막이와 똑같은 공을 일렬로 나열하는 방법의 수이다. 따라서 같은 것이 있는 순열을 사용해서 다음과 같이 구할 수 있다.

$\frac{6!}{4!2!}=15$

 

이상의 논의를 일반화하자. 공의 색이 $n$가지 있는데 공 $r$개를 뽑고 싶다. 그럼 흰 공은 $r$개, 칸막이는 $n-1$개 준비하면 된다. 이것으로 같은 것이 있는 순열을 사용하면 다음과 같다.

$\frac{(r+n-1)!}{r!(n-1)!}$

이것을 조합의 계산방법과 대조해보면 위 식은 아래 조합식과 같음을 알 수 있다.

${}_{n+r-1}\mathrm{C}_r$

결론적으로 다음 식이 성립한다.

${}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r$

 

중복조합은 조합과는 달리 $n \geq r$이라는 조건이 없다. 즉 ${}_2\mathrm{H}_5$과 같이 2개 중 5개를 고르는 것도 가능하다.

 

중복조합은 아래 부정방정식의 해와 아주 연관 깊다.

$x_1+x_2+\cdots+x_n=r$

이 식을 만족하는 음이 아닌 정수해의 개수는 ${}_n\mathrm{H}_r$개이다.

처음부터 모든 $x_i$의 값을 0으로 세팅하고 $n$개의 미지수 중 하나의 값을 1 올리는 시행을 $r$번 반복하면 해를 하나 얻을 수 있고, 이 시행이 일어날 수 있는 경우의 수는 $x_1$부터 $x_n$까지 1을 올려줄 $r$개를 고르는 것과 같은 것이기 때문이다.

 

가령 동일한 책 10권을 3개의 서로 다른 상자에 넣는다면 각 상자에 들어가는 책의 권수를 $b_1$, $b_2$, $b_3$라고 하면 다음과 같은 식이 성립한다.

$b_1+b_2+b_3=10$

이 식의 음이 아닌 정수해의 개수는 ${}_3\mathrm{H}_10=66$개이다. 따라서 책을 상자에 넣는 경우의 수는 66가지이다.

 

만약 각 상자에 적어도 한 개 이상의 책을 넣어야 해서 미지수의 범위가 자연수 범위 내로 줄어들어도 같은 방법을 사용할 수 있다. 다음과 같이 새로운 변수들을 정의하고

$b^{\prime}_i=b_i-1$

아래와 같이 식을 다시 쓰는 것이다.

$b^{\prime}_1+b^{\prime}_2+b^{\prime}_3=10-3=7$

그럼 1 이상의 정수 조건이 0 이상의 정수 조건으로 바뀌었고, 앞선 방법대로 중복조합을 사용할 수 있다.

 

만약 한 상자에 넣을 수 있는 책의 개수에 제한이 있다면, 가령 어느 상자에도 책을 6권 이상 넣을 수 없다면 포함 배제의 원리를 사용할 수 있다.

전체 경우의 수는 ${}_3\mathrm {H}_{10}$이다.

만약 첫 번째 상자에 6권의 책이 들어가서 조건을 위반하는 경우 우리는 처음부터 첫번째 상자에 책이 6권 있었다고 치고 다음 식에서 중복조합을 사용함으로써 위반하는 경우의 수를 구할 수 있다.

$b^{\prime}_1+b_2+b_3=10-6=4$, $b^{\prime}_1=b_1$

세 개의 상자가 각각 조건을 위반할 수 있기 때문에 3을 곱해서 전체에서 빼주면 된다.

${}_3\mathrm{H}_{10}-3\times {}_3\mathrm{H}_4$

 

만약 방정식이 아닌 부등식을 풀어야 한다면, 가령 다음 부등식을 만족하는 음이 아닌 정수의 개수를 구하기 위하여

$a+b+c \geq 7$

좌변에 임의의 변수 $t$를 추가하여 다음과 같이 쓸 수 있다.

$a+b+c+t = 7$

여기서 $t$는 변수 $a$, $b$, $c$에 더하여 좌우변을 맞춰주기 위해 추가한 변수이다. 쉽게 말해 $a$, $b$, $c$에 1을 더하고 남는 것을 $t$에 버리는 것이다.

결국 위 부등식의 해는 ${}_4\mathrm{H}_7$이 된다.