조합

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

조합론에서 조합(Combination)은 집합에서 일부 원소를 취해 부분집합을 만드는 것을 말한다. n 개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수는 이항계수라 하며, _nC_k나 ⁿC_k, C(n, k), 또는

${n \choose k}$로 나타낸다. C는 콤비네이션이라고 읽기도 한다.(예: ₅C₃은 "5 콤비네이션 3")

_nC_k의 값은

${n \choose 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명중 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명 선정을 하는 가지수와 동일하다

참고

• 순열
• 중복순열
• 중복조합
• 뤼카의 정리