조합: 두 판 사이의 차이

503 바이트 추가됨 ,  6개월 전
→‎공식 유도: 중복조합의 경우의 수의 공식의 다른 표현에 대한 증명을 추가함.
(→‎공식 유도: 중복조합 경우의 수의 공식의 증명을 보다 이해하기 쉽게 바꿈.)
태그: 시각 편집 nowiki 추가됨
(→‎공식 유도: 중복조합의 경우의 수의 공식의 다른 표현에 대한 증명을 추가함.)
 
 
이는 원래 문제인 ''n'' 개의 원소를 가지는 집합 ''S'' 의 원소를 순서와 상관없이 중복을 허용하여 선택 혹은 나열하는 경우의 수를 구하는 문제가, 원소(''k'' 개)와 칸막이(''n'' - 1 개)를 모두 센 숫자인 ''k'' + (''n'' - 1) = ''n'' + ''k'' - 1 개의 공간에서 ''k'' 개의 공간을 선택하여 * 를 넣는 문제로 바뀌는 것을 의미한다. (* 를 위한 ''k'' 개의 공간을 선택하면, 칸막이는 선택되지 않은 나머지 ''n'' - 1 개의 공간에 자동으로 배치된다.) 즉, <sub>''n''</sub>H<sub>''k''</sub> = <sub>''k'' + (''n'' - 1)</sub>C<sub>''k''</sub> 가 되는 것이 증명된다. 다르게 생각하여 ''n'' + ''k'' - 1 개의 공간에서 칸막이를 위한 ''n'' - 1 개의 공간을 선택하는 문제로 바꾸면 (* 는 선택되지 않은 나머지 공간에 자동으로 배치된다.) <sub>''n''</sub>H<sub>''k''</sub> = ''<sub>n</sub>'' <sub>+ ''k'' - 1</sub>C<sub>''n'' - 1</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> 이 성립하고 이는 이항계수의 성질로도 증명할 수 있다.
 
 
한편, 이항계수의 성질에서 <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> 이 된다.
 
== 외부 링크 ==

편집

13