조합: 두 판 사이의 차이

이는 원래 문제인 ''n'' 개의 원소를 가지는 집합 ''S'' 의 원소를 순서와 상관없이 중복을 허용하여 선택 혹은 나열하는 경우의 수를 구하는 문제가, 원소(''k'' 개)와 칸막이(''n'' - 1 개)를 모두 센 숫자인 ''k'' + (''n'' - 1) = ''n'' + ''k'' - 1 개의 공간에서 ''k'' 개의 공간을 선택하여 * 를 넣는 문제로 바뀌는 것을 의미한다. (* 를 위한 ''k'' 개의 공간을 선택하면, 칸막이는 선택되지 않은 나머지 ''n'' - 1 개의 공간에 자동으로 배치된다.) 즉, _''n''H_''k'' = _{''k'' + (''n'' - 1)}C_''k'' 가 되는 것이 증명된다. 다르게 생각하여 ''n'' + ''k'' - 1 개의 공간에서 칸막이를 위한 ''n'' - 1 개의 공간을 선택하는 문제로 바꾸면 (* 는 선택되지 않은 나머지 공간에 자동으로 배치된다.) _''n''H_''k'' = ''_n'' _{+ ''k'' - 1}C_{''n'' - 1} 가 된다. 즉, _''n''H_''k'' = _{''n'' + ''k'' - 1}C_''k'' ''= _n'' _{+ ''k'' - 1}C_{''n'' - 1} 이 성립하고 이는 이항계수의 성질로도 증명할 수 있다.