조합

틀:위키데이터 속성 추적 틀:다른 뜻 수학에서 조합(組合, 틀:문화어, 틀:Llang)은 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법이다. 조합의 수는 이항 계수로 주어진다.

조합

정의

집합 $S$ 와 자연수 $k$ 가 주어졌을 때, $S$ 의 (중복 없는) $k$ -조합(틀:Llang)은 $S$ 의 $k$ 개의 원소로 이루어진 부분집합을 일컫는다. 만약

S = {s_{1}, s_{2}, \dots, s_{n}}

가 $n$ 개 원소의 유한 집합이며, $0 \leq k \leq n$ 이라면, $S$ 의 $k$ -조합의 수는 이항 계수

(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k!} = \frac{n!}{k! (n - k)!}

와 같다. 이항 계수 $(\binom{n}{k})$ 는 다음과 같이 다양하게 적는다.

$C_{k}^{n}$
$C_{n}^{k}$
$_{n} C_{k}$
$n C_{k}$
$C_{n, k}$
$C (n, k)$

조합의 수의 공식은 조합론의 방법으로 쉽게 유도할 수 있다. $n$ 개의 원소의 집합에서 $k$ 개의 원소를 골라 한 줄로 배열하는 방법의 가짓수를 세자. $k$ 개의 원소를 고르는 방법의 수는 $(\binom{n}{k})$ 이다. 선택된 $k$ 개의 원소를 배열할 때, 첫 번째 자리에 둘 수 있는 원소는 $k$ 개이며, 두 번째 자리는 남은 $k - 1$ 개 가운데 하나를 놓는다. 나머지 자리도 마찬가지다. 따라서, $n$ 개의 원소를 배열하는 방법은

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

가지가 있다. 다른 한편, 첫 번째 자리에 놓을 원소를 $n$ 개 가운데 고르고, 두 번째 자리에 놓을 원소를 $n - 1$ 개 가운데 고르고, 남은 자리 역시 마찬가지로 반복하여 센 방법의 수는

n (n - 1) \dots (n - k + 1)

이다. 세는 법이 다를 때 얻는 수가 같아야 하므로 원하는 공식을 얻는다.

항등식

이항 계수 항등식

(\binom{n}{k}) = (\binom{n}{n - k})

(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1})

역시 조합론에서 직관적으로 해석할 수 있다. 전자는 $k$ 개의 원소를 고르는 방법과 $n - k$ 개의 원소를 버리는 방법은 일대일 대응함을 나타낸다. 후자는 $k$ 개의 원소를 고를 때, 어떤 고정된 원소를 고르는 경우와 이 원소를 버리는 경우를 나누어 센 결과다. 즉, 고정된 원소를 제외한 $n - 1$ 개의 원소에서 $k$ 개의 원소를 고르는 방법의 수를 세고, 고정된 원소를 고른 뒤 남은 $n - 1$ 개에서 $k - 1$ 개를 고르는 방법의 수를 세어 합하면 모든 방법의 수를 얻는다.

생성 함수

이항 계수는 다음과 같이 생성 함수를 사용하여 정의할 수 있다.

(1 + x)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k}

조합론의 관점에서, 다항식 $(1 + x)^{n}$ 의 각 항을 얻기 위해서는 $n$ 개의 이항식 $1 + x$ 에서 1 또는 $x$ 가운데 하나를 선택하여 곱하여야 한다. 따라서, $x$ 의 차수가 $k$ 인 항은 총 $(\binom{n}{k})$ 개가 만들어진다. 즉, $x^{k}$ 에는 계수 $(\binom{n}{k})$ 가 붙는다.

중복조합

정의

집합 $S$ 및 자연수 $k$ 가 주어졌다고 하자. $S$ 의 $k$ -중복조합(틀:Llang)은 $S$ 의 원소들로 구성된, 크기 $k$ 의 중복집합이다. $n$ 개 원소의 집합 $S = {s_{1}, s_{2}, \dots, s_{n}}$ 의 $k$ -중복조합의 수는

(\binom{n + k - 1}{k}) = (\binom{n + k - 1}{n - 1}) = (- 1)^{k} (\binom{- n}{k})

이다. 중복조합의 수 $(\binom{n + k - 1}{k})$ 의 표기로는 다음이 있다.

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

중복조합의 수가 $(\binom{n + k - 1}{k})$ 인 사실의 증명은 다음과 같다. 만약 ${a_{1}, \dots, a_{k}}$ 가 ${1, \dots, n}$ 의 원소들로 구성된 크기 $k$ 의 중복집합이며,

a_{1} \leq a_{2} \leq \dots \leq a_{k}

라면,

{a_{1}, a_{2} + 1, \dots, a_{k} + k - 1}

는 ${1, \dots, n + k - 1}$ 의 $k$ 원소 부분집합이다. 반대로, ${1, \dots, n + k - 1}$ 의 $k$ 원소 부분집합

{b_{1}, \dots, b_{k}}

b_{1} < b_{2} < \dots < b_{k}

이 주어졌을 때,

{b_{1}, b_{2} - 1, \dots, b_{k} - k + 1}

는 ${1, \dots, n}$ 의 원소들로 구성된 크기 $k$ 의 중복집합이다. 이는 ${1, \dots, n}$ 의 원소들로 구성된 크기 $k$ 의 중복집합들과 ${1, \dots, n + k - 1}$ 의 크기 $k$ 의 부분집합들 사이의 일대일 대응을 정의한다. 따라서 이들의 수는 같다. 후자의 수가 $(\binom{n + k - 1}{k})$ 이므로 원하는 결론을 얻는다.

이와 다른 기하학적 증명이 존재한다. $(\binom{n + k - 1}{k})$ 는 $n - 1$ 개의 막대와 $k$ 개의 공으로 만들 수 있는 (길이 $n + k - 1$ 의) 문자열의 수와 같다. 이제, 이와 같은 문자열을 다음과 같이 해석하여, ${1, \dots, n}$ 의 크기 $k$ 의 중복집합으로 간주하자. $n - 1$ 개의 막대는 두 막대 사이의 공간과 양쪽 끝의 공간을 포함하여 총 $n$ 개의 공간을 만든다. 각 공간에 1부터 $n$ 까지 번호를 매긴다. $i$ 번째 공간에 놓인 공의 수만큼 원소 $i$ 를 중복하여 취한다. 총 $k$ 개의 공이 있으므로 크기 $k$ 의 중복집합이 만들어진다. 예를 들어, $n = 3$ , $k = 5$ 인 경우, 문자열

| ◯ ◯ ◯ | ◯ ◯

은 중복집합 ${2, 2, 3, 3, 3}$ 을 나타내며, 문자열

◯ | ◯ ◯ ◯ | ◯

은 중복집합 ${1, 2, 2, 2, 3}$ 을 나타낸다. 이는 ${1, \dots, n}$ 으로 구성된 크기 $k$ 의 중복집합들과 $n - 1$ 개와 $k$ 개의 두 알파벳으로 구성된 문자열 사이에 일대일 대응을 이루며, 따라서 중복조합의 수는 문자열의 수 $(\binom{n + k - 1}{k})$ 와 같다.

생성 함수

중복조합의 수의 생성 함수는 다음과 같다.

(1 - x)^{- n} = \sum_{k = 0}^{\infty} (\binom{- n}{k}) (- x)^{k} = \sum_{k = 0}^{\infty} (\binom{n + k - 1}{k}) x^{k}

좌변의 $(1 - x)^{- 1}$ 을 멱급수로 전개하면 $1 + x + x^{2} + \dots$ 이다. $n$ 개의 멱급수에서 항 $x^{m_{i}}$ ( $i = 1, \dots, n$ )을 선택하는 방법은 각 $i$ 의 중복도가 $m_{i}$ 인 중복집합을 선택하는 방법과 일대일 대응한다. $n$ 개의 항의 곱이 $x^{k}$ 인 경우는 중복도의 합이

m_{1} + \dots + m_{n} = k

인 경우이다. 즉, 크기 $k$ 의 중복집합에 대응한다. 따라서 결국 $x^{k}$ 의 계수는 $(\binom{n + k - 1}{k})$ 이다.

참고 문헌

틀:서적 인용

외부 링크

같이 보기

조합

목차

조합

정의

항등식

생성 함수

중복조합

정의

생성 함수

참고 문헌

외부 링크

같이 보기

둘러보기 메뉴

조합

조합

정의

항등식

생성 함수

중복조합

정의

생성 함수

참고 문헌

외부 링크

같이 보기

둘러보기 메뉴

검색