중복조합(重複組合, combination with repetition)은 서로 다른 n개의 원소에서 중복을 허락하여 k개를 뽑는 경우의 수이다.
기호로는 nHk로 표기하며, 그 값은 nHk = n+k-1Ck 이다.
예를 들어, 세개의 문자 A,B,C에서 중복을 허용하여 5개를 뽑는 경우의 수는 3H5 = 7C5 = 21이므로 21가지가 된다.
공식을 유도하자면, 중복조합 nHk는 k개의 원소들을 중복을 허용하여 순서에 상관없이 나열하는 것으로 볼 수 있다.
따라서 k개의 빈칸에 중복을 허용하여 n개의 원소(n개 종류의 원소)를 넣는 개수를 구하는 문제로 생각할 수 있다.
이 떄, n가지의 원소를 순서에 상관없이 나열해야 하므로, n - 1개의 칸막이를 두고 나열하는 것으로 생각할 수 있다.
예를 들어, A,B,C 세개의 문자에서 중복을 허용하여 5개를 뽑는 경우의 수를 생각해보자.
1. A A A A A / /
2. A A A A / B
3. A A A / B B /
4. A A / B B B /
5. A / B B B B /
6. B B B B B / /
7. / B B B B / C
8. / B B B / C C
9. / B B / C C C
10. / B / C C C C
11. / / C C C C C
12. A A A A / / C
13. A A A / / C C
14. A A / / C C C
15. A / / C C C C
16. A / B / C C C
17. A / B B / C C
18. A / B B B / C
19. A A / B / C C
20. A A A / B / C
21. A A / B B / C
이런식으로 총 k + n - 1 개의 칸에서 n - 1개의 칸막이를 배치하는 경우의 수로 생각할 수 있다.
따라서 nHk = n+k-1Cn-1 = n+k-1Ck가 된다. 따라서 위의 예는 n = 3이고, k = 5 이므로 3H5 = 3+5-1C5 = 7C5 = 7C2 = 21이 된다.