중복조합

위키백과 ― 우리 모두의 백과사전.

중복조합 (重複組合, combination with repetition) nHr은 서로 다른 n 개의 원소에서 r 개를 뽑는 경우의 수이다. nHr = n+r-1Cr 이다.

예를 들어, 세개의 문자 A,B,C에서 중복을 허용하여 5개를 뽑는 경우의 수는 3H5 = 7C5 = 21이므로 21가지가 된다. 실제 경우의 수를 따져보면 다음과 같다.

  1. A A A A A
  2. B B B B B
  3. C C C C C
  4. A B B B B
  5. A A B B B
  6. A A A B B
  7. A A A A B
  8. A C C C C
  9. A A C C C
  10. A A A C C
  11. A A A A C
  12. B C C C C
  13. B B C C C
  14. B B B C C
  15. B B B B C
  16. A B B C C
  17. A A B C C
  18. A A B B C
  19. A A A B C
  20. A B B B C
  21. A B C C C

[편집] 중복조합 공식 유도

위에서 예에서 나열한 방법으로 중복조합의 공식을 유도할 수도 있지만, 다른 방법으로 설명하도록 하겠다. 중복조합 nHrr 개의 원소들을 순서에 상관없이 나열하는 것이므로, r 개의 빈칸에 중복을 허용하여 n개의 원소를 넣는 개수를 구하는 문제로 생각할 수 있다. 여기에 n 가지의 경우로 구분할 수 있는 원소들을 순서에 상관없이 집어 넣어야 하므로, n-1 개의 칸막이를 두고 n 가지 경우를 임의의 순서로 배열한다고 할 수 있다.

예를 들어 칸막이 기호를 /로 나타낸다면, 위의 예제에서 "A B B B C"는 "A / B B B / C"에 해당하고 "A B C C C"는 "A / B / C C C"에 해당한다.

물론. 이 경우 칸막이 사이에 아무 원소도 없을 수도 있다. 이것은 그 원소가 선택되지 않은 경우에 해당한다. 예를 들어 위의 예제에서 "A A A C C"는 "A A A / / C C"에 해당하고 "B B C C C"는 "/ B B / C C C"에 해당한다.

이제 중복조합의 문제는 원래 문자가 들어갈 r 개의 빈칸과 n-1 개의 칸막이가 들어갈 빈칸을 모두 합한 n+r-1 개의 빈칸에서, 칸막이가 들어갈 n-1개의 칸을 선택하는 문제로 변형되었다. 결국 중복조합 nHrn+r-1Cn-1이 된다. 한편, nCr = nCn-r이므로 nHr= n+r-1Cr이 된다.

[편집] 참고