조합

다른 뜻에 대해서는 조합 (동음이의) 문서를 참고하십시오.

조합론에서 조합(組合, 문화어: 무이, 영어: combination)은 서로 다른 n개의 원소를 가지는 어떤 집합 (사실, 집합은 서로 다른 원소의 모임으로 정의된다.)에서 순서에 상관없이 r개의 원소를 선택하는 것이며, (즉, 선택의 순서와 상관없이 같은 원소들이 선택되었다면 같은 조합이며 다른 원소들이 선택되었다면 다른 조합이다.) 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다. 가능한 조합의 수는 이항계수와 같다.

n개의 원소의 k-조합

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

그 값은 $C(n,k)={n \choose k}={\frac {P(n,k)}{k!}}={\frac {n!}{k!\cdot (n-k)!}}$이다. 즉, $P(n,k)=C(n,k)\times {k!}$ 인데, 이는 각 조합에서의 가능한 순열의 수가 $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)은 서로 다른 $n$개의 원소에서 중복을 허락하여 $k$개를 뽑는 경우이다. 가능한 중복조합의 수는, 크기가 $n$인 집합에서 만들 수 있는 크기가 $k$인 중복집합의 수와 같으며 기호로는 $\left(\!\!\!{\binom {n}{k}}\!\!\!\right)$ 또는 _nH_k로 표기하며, 그 값은 _nH_k = _{k + (n - 1)}C_k이다.

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

성질

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

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

공식 유도

n 개의 원소를 가지는 집합 S 의 원소를, 순서와 상관없이 중복을 허용하여 선택 혹은 나열하는 경우의 수가 중복 조합의 수, 즉 $_{n}H_{k}$이다. 예를 들어, 크기 n = 3 인 집합 S = {A, B, C} 에서 만들 수 있는 크기 k = 5 인 중복조합 혹은 중복집합을 생각해보자. 그러한 중복조합은 칸막이 / 의 도움을 받아 다음과 같이 표현할 수 있다.

A / / CCCC,

A / B / CCC,

A / BB / CC,

A / BBB / C,

A / BBBB / ,

AA / / CCC,

AA / B / CC,

...

여기서는 칸막이로 구분된 첫번째 공간을 A 에 배정하였고, 칸막이로 구분된 두번째 공간을 B, 그리고 세번째 공간을 C 에 배정하였다. 조합은 순열과 달리 원소의 나열 순서를 상관하지 않기 때문에, 칸막이로 구분된 어떤 공간을 S 의 어떤 원소에 배정할 지는 중요하지 않다. 각 칸막이로 구분된 공간, 즉 각 칸막이 공간이 S 의 어떤 원소에 배정될 지를 정하고 이를 기억한다면 위의 예제는 아래와 같이 표현될 수 있다.

* / / ****,

* / * / ***,

* / ** / **,

* / *** / *,

* / **** / ,

** / / ***,

** / * / **,

...

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

외부 링크

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

같이 보기

• 순열
• 뤼카의 정리