중복조합

중복조합

서로다른 $n$개에서 $r$개를 중복하여 택하는 조합의 경우의 수를 $_nH_r$로 나타낸다. 서로 다른 $n$개에서 $r$개를 택하는 중복조합의 수는

$$_nH_r = _{n+r-1}C_r$$

이다. 

예를 들어, $1,2,3$ 중에서 $2$개를 중복하여 택하는 조합의 경우의 수 $_3H_2$는 $11, 12, 13, 22, 23, 33$ 으로 $6$가지이다. 이 $6$가지의 두번째 숫자에 $1$을 더하면 $12, 13, 14, 23, 24, 34$ 이다. 이것은 $1,2,3,4$중에서 2개를 택하는 조합의 수 $_4C_2$와 같다.

또 다른 예를 생각해보자. $1,2$중에서 $3$개를 중복하여 택하는 조합의 경우의 수 $_2H_3$는 $111, 112, 122, 222$ 으로 4가지 이다. 이 $4$가지의 두번째 숫자에 $1$, 세번째 숫자에 $2$를 더하면 $123, 124, 134, 234$ 이다. 이것은 $1,2,3,4$중에서 3개를 택하는 조합의 수 $_4C_3$와 같다.

이제 집합 $\{a,b,c,d\}$중에서 중복하여 $10$개를 택하는 방법을 생각해보자. 만약 $a$ $3$개 $b$ $2$개 $c$ $4$개 $d$ $1$개 있는 경우를 나타내면

$\{a,a,a,b,b,c,c,c,c,d\}=\{\bullet \bullet \bullet | \bullet \bullet | \bullet \bullet \bullet \bullet | \bullet\}$ 이다. 이것은 점 $10$개 막대 $3$개 합해 총 $13$개를 택하여 배열하는 중복조합과 일대일대응된다.

부정방정식

자연수 $r$에 대하여 부정방정식 $x_i\ge 0$인 정수해의 개수를 구해보자. $x_0 + x_1 + \cdots + x_n = r$ 의 해이 개수는 $n+1$개에서 $r$개를 중복하여 택하는 조합의 수와 같다. 즉, 해의 갯수는 $_{n+1}H_r$ 이다.