조합: 두 판 사이의 차이

'''중복조합'''(重複組合, combination with repetition)은 서로 다른 <math>n</math>개의 원소에서 중복을 허락하여 <math>k</math>개를 뽑는 경우의 수이다경우이다. 이는가능한 중복조합의 수는, 크기가 <math>n</math>인 집합에서, 만들 수 있는 크기가 <math>k</math>인 [[중복집합]]을의 고를수와 수 있는 가짓수와 같다.같으며 기호로는 <math>\left(\!\!\!\binom{n}{k}\!\!\!\right)</math> 또는 _''n''H_''k''로 표기하며, 그 값은 _''n''H_''k'' = _{''k'' + (''n'' - 1)}C_''k''이다.

예를 들어, 세개의 문자 A,B,C에서 (''n'' = 3) 중복을 허용하여 5개를 뽑는 (''k'' = 5) 경우의 수는 ₃H₅ = ₇C₅ = 21이므로 21가지가 된다21이다.

이제 중복조합의 문제는 원래 문자가 들어갈 <math>k</math>개의 빈칸과 <math>n-1</math>개의 칸막이가 들어갈 빈칸을 모두 합한 <math>n+k-1</math>개의 빈칸에서, 칸막이가 들어갈 <math>n-1</math>개의 칸을 선택하는 문제로 변형되었다. 결국 중복조합의 경우의 수 _''n''H_''k'' = _{''n'' + ''k'' - 1}C_{''n'' - 1}이 된다. 한편, 이항계수의 성질에서 _''n''H_''k'' = _{''n'' + ''k'' - 1}C_''k''이 된다.