조합

이 문서는 수학에 관한 것입니다. 다른 뜻에 대해서는 조합 (법률) 문서를 참고하십시오.

조합론에서, 조합(組合, 문화어: 무이, 영어: combination)은 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 말한다. 그 경우의 수는 이항계수이다.

n개의 원소의 k-조합

n 개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를 이항계수라 하며, _nC_k나 ⁿC_k, C(n, k), 또는 ${n \choose k}$로 나타낸다. 기호 C는 콤비네이션이라고 읽기도 한다.

그 값은 ${n \choose k}={\frac {P(n,k)}{k!}}={\frac {n!}{k!\cdot (n-k)!}}$이다.

예를 들어, 10개 중에서 3개를 뽑는 경우의 수는 ${10 \choose 3}={\frac {10!}{3!\cdot 7!}}={\frac {10\cdot 9\cdot 8}{3\cdot 2\cdot 1}}=120$이다.

성질

• ${n \choose k}={n \choose n-k}$

증명
${n \choose k}={\frac {n!}{k!\cdot (n-k)!}}={\frac {n!}{(n-k)!\cdot [n-(n-k)]!}}={n \choose n-k}$ 이 성질을 직관적으로 보일 수도 있다. n명 중 A그룹에 들어갈 k명을 뽑는 가짓수는 n명중 A그룹에 들어가지 않을 n-k명을 뽑는 가짓수와 동일하다.

• ${n \choose k}={{n-1} \choose {k-1}}+{{n-1} \choose k}$

증명: n명중 B라는 사람을 우선 빼놓고 생각하자. 그렇다면

n명중 A그룹에 들어갈 k명을 고르는 가짓수 = B를 무조건 A그룹에 포함하는 경우 + B를 무조건 배제하는 경우 = n-1명 중 k-1명 선정 + n-1명 중 k명 선정을 하는 가짓수

이다.

중복조합

중복조합 (重複組合, combination with repetition) _nH_r은 서로 다른 n 개의 원소에서 중복을 허락하여 r 개를 뽑는 경우의 수이다. _nH_r = _n+r-1C_r 이다.

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

성질

중복조합에서 다음이 성립한다.

$_{n}H_{0}=1$
$_{n}H_{1}=n$
$_{n}H_{k}=_{k+1}H_{n-1}\ ($단, $n\geq 1)$
$_{n}H_{0}+_{n}H_{1}+_{n}H_{2}+\cdots +_{n}H_{r}=_{n+1}H_{r}$

공식 유도

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

예를 들어 칸막이 기호를 /로 나타낸다면, 위의 예제에서 "A B B B C"는 "A / B B B / C"에 해당하고 "A B C C C"는 "A / B / C C C"에 해당한다.

물론 칸막이 사이에 아무 원소도 없을 수도 있는데, 이것은 그 원소가 선택되지 않은 경우에 해당한다. 예를 들어 위의 예제에서 "A A A C C"는 "A A A / / C C"에 해당하고 "B B C C C"는 "/ B B / C C C"에 해당한다.

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

바깥 고리

• “Combination”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Combination”. 《Wolfram MathWorld》 (영어). Wolfram Research. 

같이 보기

• 순열
• 뤼카의 정리