2021년 11월 20일 (토) 09:26 판 편집 Goodphy (토론 \| 기여) 18 편집 →‎중복조합: 변수를 기울임체 글꼴로 변경하여 가독성을 높임. 태그: 시각 편집 ← 이전 편집		2021년 11월 20일 (토) 22:24 판 편집 편집 취소 Goodphy (토론 \| 기여) 18 편집 →‎공식 유도: 중복조합 경우의 수의 공식의 증명을 보다 이해하기 쉽게 바꿈. 태그: nowiki 추가됨 시각 편집 다음 편집 →
36번째 줄: === 공식 유도 === ''n'' 개의 원소를 가지는 집합 ''S'' 의 원소를, 순서와 상관없이 중복을 허용하여 선택 혹은 나열하는 경우의 수가 중복 조합의 수, 즉 <math>_{n}H_{k}</math>이다. 예를 들어, 크기 ''n'' = 3 인 집합 ''S'' = {A, B, C} 에서 만들 수 있는 크기 ''k'' = 5 인 중복조합 혹은 중복집합을 생각해보자. 그러한 중복조합은 칸막이 / 의 도움을 받아 다음과 같이 표현할 수 있다. 모든 경우를 직접 나열하는 방법으로 중복조합의 공식을 유도할 수도 있으나, 여기서는 다른 방법으로 설명한다. 중복조합 <math>_{n}H_{k}</math>는 <math>k</math>개의 원소들을 순서에 상관없이 나열하는 것이므로, <math>k</math>개의 빈칸에 중복을 허용하여 <math>n</math>개의 원소를 넣는 개수를 구하는 문제로 생각할 수 있다. 여기에 <math>n</math>가지의 경우로 구분할 수 있는 원소들을 순서에 상관없이 집어 넣어야 하므로, <math>n-1</math>개의 칸막이를 두고 <math>n</math>가지 경우를 임의의 순서로 배열한다고 할 수 있다. ~~예를 들어 칸막이 기호를 /로 나타낸다면, 위의 예제에서 "A B B B C"는 "A / B B B / C"에 해당하고 "A B C C C"는 "A / B / C C C"에 해당한다.~~ A / / CCCC, 물론 칸막이 사이에 아무 원소도 없을 수도 있는데, 이것은 그 원소가 선택되지 않은 경우에 해당한다. 예를 들어 위의 예제에서 "A A A C C"는 "A A A / / C C"에 해당하고 "B B C C C"는 "/ B B / C C C"에 해당한다. A / B / CCC, 이제 중복조합의 문제는 원래 문자가 들어갈 <math>k</math>개의 빈칸과 <math>n-1</math>개의 칸막이가 들어갈 빈칸을 모두 합한 <math>n+k-1</math>개의 빈칸에서, 칸막이가 들어갈 <math>n-1</math>개의 칸을 선택하는 문제로 변형되었다. 결국 중복조합의 경우의 수 <sub>''n''</sub>H<sub>''k''</sub> = <sub>''n'' + ''k'' - 1</sub>C<sub>''n'' - 1</sub>이 된다. 한편, 이항계수의 성질에서 <sub>''n''</sub>H<sub>''k''</sub> = <sub>''n'' + ''k'' - 1</sub>C<sub>''k''</sub>이 된다. A / BB / CC, A / BBB / C, A / BBBB / , AA / / CCC, AA / B / CC, ... 여기서는 칸막이로 구분된 첫번째 공간을 A 에 배정하였고, 칸막이로 구분된 두번째 공간을 B, 그리고 세번째 공간을 C 에 배정하였다. 조합은 [[순열]]과 달리 원소의 나열 순서를 상관하지 않기 때문에, 칸막이로 구분된 어떤 공간을 ''S'' 의 어떤 원소에 배정할 지는 중요하지 않다. 각 칸막이로 구분된 공간, 즉 각 칸막이 공간이 ''S'' 의 어떤 원소에 배정될 지를 정하고 이를 기억한다면 위의 예제는 아래와 같이 표현될 수 있다. <nowiki></nowiki> / / **, <nowiki></nowiki> / * / **, <nowiki></nowiki> / / , <nowiki></nowiki> / ** / , <nowiki></nowiki> / ** / , <nowiki></nowiki> / / *, <nowiki></nowiki> / * / *, ... 이는 원래 문제인 ''n'' 개의 원소를 가지는 집합 ''S'' 의 원소를 순서와 상관없이 중복을 허용하여 선택 혹은 나열하는 경우의 수를 구하는 문제가, 원소(''k'' 개)와 칸막이(''n'' - 1 개)를 모두 센 숫자인 ''k'' + (''n'' - 1) = ''n'' + ''k'' - 1 개의 공간에서 ''k'' 개의 공간을 선택하여 를 넣는 문제로 바뀌는 것을 의미한다. 즉, <sub>''n''</sub>H<sub>''k''</sub> = <sub>''k'' + (''n'' - 1)</sub>C<sub>''k''</sub> 가 되는 것이 증명된다. 한편, 이항계수의 성질에서 <sub>''n''</sub>H<sub>''k''</sub> = <sub>''n'' + ''k'' - 1</sub>C<sub>''k''</sub> ''= <sub>n</sub>'' <sub>+ ''k'' - 1</sub>C<sub>''n'' - 1</sub> 이 된다. == 외부 링크 ==

조합: 두 판 사이의 차이