조합: 두 판 사이의 차이

''<math>n'' </math>개의 원소를 가지는 집합에서 ''<math>k''</math>개의 부분집합을 고르는 조합의 경우의 수를 [[이항계수]]라 하며, _''n''C_''k''나 ^''n''C_''k'', C(''n'', ''k''), 또는 <math>{n \choose k}</math>로 나타낸다. 기호 C는 콤비네이션이라고 읽기도 한다.

'''중복조합'''(重複組合, combination with repetition) _nH_rk은 서로 다른 ''<math>n'' </math>개의 원소에서 중복을 허락하여 ''r'' <math>k</math>개를 뽑는 경우의 수이다. 이는 크기가 <math>n</math>인 집합에서, 크기가 <math>k</math>인 [[중복집합]]을 고를 수 있는 가짓수와 같다. _nH_r = _n+rk-1C_rk 이다.

<math>_n H _0 + _n H _1 + _n H _2 + \cdots + _nH_r_nH_k = _{n+1}H_rH_k</math>

모든 경우를 직접 나열하는 방법으로 중복조합의 공식을 유도할 수도 있으나, 여기서는 다른 방법으로 설명한다. 중복조합 nHr은 rnHk는 <math>k</math>개의 원소들을 순서에 상관없이 나열하는 것이므로, r <math>k</math>개의 빈칸에 중복을 허용하여 n개의<math>n</math>개의 원소를 넣는 개수를 구하는 문제로 생각할 수 있다. 여기에 <math>n </math>가지의 경우로 구분할 수 있는 원소들을 순서에 상관없이 집어 넣어야 하므로, <math>n-1 </math>개의 칸막이를 두고 <math>n </math>가지 경우를 임의의 순서로 배열한다고 할 수 있다.

이제 중복조합의 문제는 원래 문자가 들어갈 r <math>k</math>개의 빈칸과 <math>n-1 </math>개의 칸막이가 들어갈 빈칸을 모두 합한 <math>n+rk-1 </math>개의 빈칸에서, 칸막이가 들어갈 <math>n-1개의1</math>개의 칸을 선택하는 문제로 변형되었다. 결국 중복조합 nHr은nHk은 n+rk-1Cn1Ck-1이 된다. 한편, nCrnCk = nCn-r이므로k이므로 nHrnHk= n+rk-1Cr이1Ck이 된다.