중복조합
위키백과 ― 우리 모두의 백과사전.
중복조합 (重複組合, combination with repetition) nHr은 서로 다른 n 개의 원소에서 r 개를 뽑는 경우의 수이다. nHr = n+r-1Cr 이다.
예를 들어, 세개의 문자 A,B,C에서 중복을 허용하여 5개를 뽑는 경우의 수는 3H5 = 7C5 = 21이므로 21가지가 된다. 실제 경우의 수를 따져보면 다음과 같다.
- A A A A A
- B B B B B
- C C C C C
- A B B B B
- A A B B B
- A A A B B
- A A A A B
- A C C C C
- A A C C C
- A A A C C
- A A A A C
- B C C C C
- B B C C C
- B B B C C
- B B B B C
- A B B C C
- A A B C C
- A A B B C
- A A A B C
- A B B B C
- A B C C C
[편집] 중복조합 공식 유도
위에서 예에서 나열한 방법으로 중복조합의 공식을 유도할 수도 있지만, 다른 방법으로 설명하도록 하겠다. 중복조합 nHr은 r 개의 원소들을 순서에 상관없이 나열하는 것이므로, 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개의 칸을 선택하는 문제로 변형되었다. 결국 중복조합 nHr은 n+r-1Cn-1이 된다. 한편, nCr = nCn-r이므로 nHr= n+r-1Cr이 된다.