조합

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

조합론에서, 조합(組合, 영어: combination)은 집합에서 일부 원소를 취해 부분집합을 만드는 것을 말한다. n 개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수는 이항계수라 하며, nCknCk, C(n, k), 또는

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

nCk의 값은

 {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명 선정을 하는 가지수

이다.

바깥 고리[편집]

같이 보기[편집]