조합: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
영어 위백을 참고하여 문서 다듬음 |
중복조합 문서에서 가져옴 |
||
17번째 줄:
: n명중 A그룹에 들어갈 k명을 고르는 가지수 = B를 무조건 A그룹에 포함하는 경우 + B를 무조건 배제하는 경우 = n-1명 중 k-1명 선정 + n-1명 중 k명 선정을 하는 가지수
이다.
'''중복조합''' (重複組合, combination with repetition) <sub>n</sub>H<sub>r</sub>은 서로 다른 ''n'' 개의 원소에서 중복을 허락하여 ''r'' 개를 뽑는 경우의 수이다. <sub>n</sub>H<sub>r</sub> = <sub>n+r-1</sub>C<sub>r</sub> 이다.
예를 들어, 세개의 문자 A,B,C에서 중복을 허용하여 5개를 뽑는 경우의 수는 <sub>3</sub>H<sub>5</sub> = <sub>7</sub>C<sub>5</sub> = 21이므로 21가지가 된다.
=== 성질 ===
중복조합에서 다음이 성립한다.
<math>_n H _0 = 1</math><br>
<math>_n H _1 = n</math><br>
<math>_n H _k = _{k+1} H _{n-1}\ (</math>단, <math> n\ge1) </math><br>
<math>_n H _0 + _n H _1 + _n H _2 + \cdots + _nH_r = _{n+1}H_r</math>
=== 공식 유도 ===
모든 경우를 직접 나열하는 방법으로 중복조합의 공식을 유도할 수도 있으나, 여기서는 다른 방법으로 설명한다. 중복조합 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이 된다.
== 바깥 고리 ==
줄 24 ⟶ 46:
== 같이 보기 ==
* [[순열]]
▲* [[중복조합]]
* [[뤼카의 정리]]
| |||