조합

조합은 어떤 대상의 집합에서 몇 개를 고를 때, 고르는 순서가 중요하지 않은 경우에 쓴다. 전형적인 예는 49개의 수 가운데 6개를 고르는 복권이다. 추첨함에 공이 49개 있고 그 가운데 6개를 뽑는데, 어떤 순서로 뽑히든 상관없다.

공식 이끌어 내기

행운의 바퀴

어떤 집합 M, 예를 들어 M = {a, b, c, d, e}가 있다고 하자. 이때 k개의 원소로 이루어진 조합은 원소를 정확히 k개 가진 부분집합 K ⊆ M이다. K는 집합이므로 당연히 순서는 상관없다. 즉 집합 M에서 세 원소를 고른 조합은 {a, b, d}나 {b, c, d}가 될 수 있다.

순열과 다른 점은 순열에서는 순서가 중요했다는 것이다. 그래서 (a, b, e)와 (e, b, a)는 서로 다른 순열이지만 같은 조합이다. (a, b, e)와 (e, b, a)에는 같은 원소가 들어 있고, 순서가 다르다는 것은 조합에서는 신경 쓰지 않기 때문이다.

하지만 순열을 이용해 서로 다른 조합의 수를 구하는 공식을 얻을 수 있다. 원소가 n개인 집합에서 k개를 고르는 순열의 수는 다음과 같다는 것을 알고 있다.

$_{n} P_{k} = \frac{n!}{(n - k)!} .$

앞의 집합 M = {a, b, c, d, e}에서 세 원소를 고르는 순열의 수를 모두 구하면 서로 다른 순열 {}₅P₃ = 60가지를 얻는다. 그런데 여기에는 세 원소로 이루어진 각 묶음의 모든 순열이 들어 있다. 즉 abc뿐 아니라 acb, bac, bca, cab, cba도 들어 있다. 이들은 서로 다른 순열 여섯 개이지만, 원소가 모두 같으므로 조합으로는 하나이다.

그러면 세 원소로 이루어진 묶음 하나에 대해 서로 다른 순열은 몇 가지일까? 3!가지이다. 다시 말해 세 원소를 고르는 순열은 세 원소를 고르는 조합보다 3!배 많다. 조합 하나로 세지 않고, 그 세 원소의 각 순열마다 하나씩 3!배 많은 순열로 세는 것이다. 그래서 순열의 수를 3!로 나누면 조합의 수를 얻는다.

앞의 방법을 일반화해 보자. 크기가 n인 집합에서 k개를 고르는 서로 다른 조합의 수를 {}_nC_k로 나타내면 다음과 같다.

$_{n} C_{k} = \frac{_{n} P_{k}}{k!},$

즉 순열의 수를, k개로 이루어진 각 묶음을 늘어놓는 방법의 수인 k!로 나눈 것이다. 순열의 공식을 풀어 쓰면 공식을 정리할 수 있다.

$_{n} C_{k} = \frac{_{n} P_{k}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

예: 집합 {a, b, c}에서 두 원소를 고르는 조합의 수는 다음과 같다.

$_{3} C_{2} = \frac{3!}{1! \cdot 2!} = 3$

이 조합은 {a, b}, {a, c}, {b, c}이다. 원래 집합 M = {a, b, c, d, e}에서 세 원소를 고르는 조합이라면 다음 개수를 얻는다.

$_{5} C_{3} = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

이 조합은 {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}이다.

이항계수

앞에서 쓴 {}_nC_k 대신 이항계수로 나타내기도 한다. 이항계수는 다음과 같이 쓴다.

$(\binom{n}{k})$

분수선이 없는 분수 같은 모양이고(습관 때문에 분수선을 그리고 싶어지겠지만), 괄호로 감싼다(괄호는 생략할 수 없다). 영어로는 “n choose k”라고 읽는다. 이항계수의 값은 {}_nC_k와 같다.

$_{n} C_{k} = \frac{n!}{(n - k)! \cdot k!}$

따라서 원소가 5개인 집합에서 네 개를 고르는 조합의 수는 모두 다음과 같다.

$_{5} C_{4} = \frac{5!}{1! \cdot 4!} = 5.$

기본 관계

이항계수에 대해 n ∈ ℕ이면 다음이 성립한다.

$\begin{array}{rcl} _{n} C_{0} =_{n} C_{n} =_{0} C_{0} & = & 1 \\ _{n} C_{1} & = & n \end{array}$

또 n, k ∈ ℕ₀이고 k ≤ n이면 다음이 성립한다.

$\begin{array}{rcl} _{n} C_{n - k} & = & _{n} C_{k} . \end{array}$

그리고 n, k ∈ ℕ₀이고 k < n이면 다음이 성립한다.

$\begin{array}{rcl} _{n} C_{k} +_{n} C_{k + 1} & = & _{n + 1} C_{k + 1} . \end{array}$

계산기

다음 계산기는 n개에서 k개를 고르는 조합의 수를 구해 준다.

풀이가 있는 예제

앞에서 말한 복권부터 시작하자. 공이 49개 들어 있는 추첨함에서 공을 모두 6개 뽑는다. 나올 수 있는 경우는 몇 가지일까?

먼저, 공을 뽑는 순서가 중요할까? 중요하지 않다. 수만 맞히면 되고 순서는 맞힐 필요가 없다. 따라서 조합을 쓴다. 공이 모두 49개이고 6개를 뽑으므로 다음 이항계수를 얻는다.

$_{49} C_{6} = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13,983,816$

뽑힐 수 있는 경우는 모두 13 983 816가지이다. 덧붙이면, 한 번 걸 때 당첨될 확률은 1/13,983,816, 즉 0.00000715112%이다.
아이스크림 가게에 맛이 13가지 있다. 서연이는 서로 다른 맛 4가지를 골라 한 통에 담으려고 한다. 서연이가 고를 수 있는 네 가지 맛의 조합은 몇 가지일까?

이것도 간단한 조합의 예이다. 한 통에 함께 담으므로 순서는 상관없다. 즉 맛 13가지에서 4가지를 고르므로 다음 이항계수를 얻는다.

$_{13} C_{4} = 715.$
남자와 여자가 반씩 섞인 50명이 있다. 한 성별로만 이루어지지 않도록(즉 남자 세 명이나 여자 세 명이 되지 않도록) 세 명을 고르는 방법은 몇 가지일까?

조금 더 복잡한 조합이다. 한 성별로만 이루어진 세 명을 빼면 세 명을 고르는 방법은 두 가지뿐이다. 남자 두 명과 여자 한 명, 또는 남자 한 명과 여자 두 명이다. 첫 번째 경우(남자 두 명과 여자 한 명)의 조합의 수는 두 번째 경우의 조합의 수와 같다. 그래서 첫 번째 경우의 조합의 수만 구해서 2를 곱하면 된다. 이제는 쉽다. 남자 두 명을 고르는 조합의 수, 즉 25개에서 2개를 고르는 조합의 수를 구하고, 여자 한 명을 고르는 조합의 수(앞의 기본 관계의 두 번째 줄에 따라 25)를 곱한다. 이 결과에 2를 곱하면 최종 결과를 얻는다.

$2 \cdot_{25} C_{2} \cdot_{25} C_{1} = 15000.$
상자에 제품이 15개 있고, 그 가운데 4개가 불량품이다. 다음과 같이 제품 6개를 고르는 방법은 몇 가지일까?
- 불량품이 하나도 없도록. 이때는 불량품이 아닌 15 − 4 = 11개에서 6개를 고른다. 그러면 다음 이항계수를 얻는다.
  
  $_{11} C_{6} = 462.$
- 불량품이 정확히 하나이도록. 정상품 5개와 불량품 1개로 이루어진 집합을 고르는 것이다. 정상품은 모두 11개, 불량품은 4개이다. 곱의 법칙을 쓰면 다음 결과를 얻는다.
  
  $_{11} C_{5} \cdot_{4} C_{1} = 1848$
- 불량품이 많아야 하나이도록. 앞의 결과를 이용해 푼다. 정상품만 6개 고르는 방법이 모두 462가지이고, 정상품 5개와 불량품 1개를 고르는 방법이 1848가지이다. 합의 법칙을 써서 두 결과를 더하면 원하는 결과, 즉 불량품이 많아야 하나(불량품이 없거나 정확히 하나)인 경우를 얻는다. 결과는 462 + 1848 = 2310이다.

목차: 경우의 수, 순열, 모두 늘어놓는 순열(팩토리얼), 조합, 중복순열, 중복조합, 비밀번호(PIN)는 몇 가지일까?

« 이전: 모두 늘어놓는 순열(팩토리얼)

다음: 중복순열 »