조합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 조합
3. 중복조합
4. k-조합 열거
5. 모든 k에 대한 k-조합의 수
6. 확률: 무작위 조합 샘플링
7. 상자에 물건 넣기
8. 조합 관련 추가 정보 (한국 관련)
참조

1. 개요

조합은 주어진 집합에서 특정 개수의 원소를 선택하는 방법의 수를 다루는 수학 개념이다. 조합에는 중복을 허용하지 않는 k-조합과 중복을 허용하는 k-중복조합이 있으며, k-조합의 수는 이항 계수를 통해, k-중복조합의 수는 $\binom{n+k-1}k$ 를 통해 계산된다. 조합은 이항 정리, 생성 함수 등과 관련이 있으며, k-조합을 열거하는 다양한 방법이 존재한다. 또한, 모든 k에 대한 k-조합의 개수는 $2^n$ 으로, 집합의 부분집합 개수와 같다. 확률, 상자에 물건 넣기 등 다양한 분야에 활용되며, 무작위 조합 샘플링 알고리즘과 다항 계수를 이용한 경우의 수도 계산할 수 있다.

더 읽어볼만한 페이지

조합론 - 집합의 분할
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.
조합론 - 계승 (수학)
계승은 음이 아닌 정수 n에 대해 1부터 n까지의 자연수를 곱한 값으로, 0의 계승은 1로 정의되며, 대칭군의 크기와 같다는 성질을 통해 기수로 확장될 수 있고, 다중 계승, 지수 계승 등으로 확장 및 응용되어 다양한 분야에서 활용된다.

조합
수학적 조합
설명	집합에서 순서를 고려하지 않고 항목을 선택하는 방법
다른 이름	조합, 선택
종류	조합 중복 조합
기호	C(n, r) nCr nC_r (n
공식	n! / (r! * (n-r)!)
관련 개념	순열 이항 계수 파스칼의 삼각형
응용	확률론 통계학 이산수학 컴퓨터 과학 암호학
조합 (조합론)
설명	집합에서 순서를 고려하지 않고 일부 원소를 선택하는 방법.
로마자 표기	jophab
수학 분야	조합론
관련 개념	순열 이항 계수 파스칼의 삼각형
용어	조합론에서 조합은 집합에서 순서를 고려하지 않고 원소를 선택하는 방법을 의미한다. 순열과 달리 순서가 중요하지 않다. 예를 들어, 집합 {A, B, C}에서 2개의 원소를 선택하는 조합은 {A, B}, {A, C}, {B, C} 세 가지이다. 순열이라면 AB와 BA를 다른 것으로 취급하지만, 조합에서는 같은 것으로 취급한다. 조합은 여러 분야에서 응용된다. 확률에서 조합은 특정 사건이 발생할 확률을 계산하는 데 사용되며, 통계에서는 표본을 선택하는 데 사용된다. 컴퓨터 과학에서는 조합은 알고리즘의 성능을 분석하는 데 사용된다.
조합 (수학)
정의	주어진 집합에서 원소의 순서를 고려하지 않고 선택하는 방법.
예시	{1, 2, 3}에서 두 개를 선택하는 조합은 {1, 2}, {1, 3}, {2, 3} 총 3가지.
조합 수 계산	n개에서 r개를 선택하는 조합의 수 = n! / (r!(n-r)!)
관련 용어	순열 이항 계수 파스칼의 삼각형
응용 분야	확률 통계 이산수학 컴퓨터 과학 암호학
중복 조합	중복 조합은 같은 원소를 여러 번 선택할 수 있는 조합.

2. 조합

주어진 ''n''개의 원소를 갖는 집합에서 순서를 고려하지 않고 ''k''개의 원소를 선택하는 것을 ''k''-조합이라고 한다. 이는 이항 계수와 밀접하게 관련되어 있으며, $C(n,k)$ , $C^n_k$ , ${}_nC_k$ , ${}^nC_k$ , $C_{n,k}$ 또는 $C_n^k$ 와 같이 표현한다.^[5]^[6]^[7]

이항 계수는 이항 정리에서 계수로 나타나기 때문에 사용되며, 모든 자연수 ''k''에 대해 다음 관계식으로 정의할 수 있다.

$(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,$

여기서 $\binom{n}{0} = \binom{n}{n} = 1$ 이고, ''k'' > ''n''이면 $\binom{n}{k} = 0$ 이다.

이항 계수는 다음의 재귀적 관계를 통해 파스칼의 삼각형을 구성할 수 있다.

$\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k},$ (단, 0 < ''k'' < ''n'')

개별 이항 계수를 계산할 때는 다음 공식을 사용하면 편리하다.

$\binom nk = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.$

이 공식에서 분자는 ''n''개의 원소에서 ''k''개를 순서대로 나열하는 ''k''-순열의 수를 나타내고, 분모는 순서를 무시했을 때 같은 ''k''-조합을 나타내는 ''k''-순열의 수를 나타낸다.

''k''가 ''n''/2보다 큰 경우에는 다음 관계를 이용하여 계산할 수 있다.

$\binom nk = \binom n{n-k},$ (단, 0 ≤ ''k'' ≤ ''n'')

또한, 다음 공식도 기억해두면 유용하다.

$\binom nk = \frac{n!}{k!(n-k)!},$

여기서 ''n''!는 ''n''의 팩토리얼을 의미한다.

2. 1. 정의

집합

S

와 자연수

k

가 주어졌을 때,

S

의 '''(중복 없는)

k

-조합'''(

k

-combination (without repetition)^영어)은

S

의

k

개의 원소로 이루어진 부분집합을 말한다. 만약

:

S=\{s_1,s_2,\dots,s_n\}

가

n

개 원소의 유한 집합이며,

0\le k\le n

이라면,

S

의

k

-조합의 수는 이항 계수

:

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

와 같다.

\textstyle\binom nk

는 다음과 같이 다양하게 적는다.

$C^n_k$
$C_n^k$
$_nC_k$
$^nC_k$
$C_{n,k}$
$C(n,k)$

조합의 수 공식은 조합론의 방법으로 쉽게 유도할 수 있다.

n

개의 원소의 집합에서

k

개의 원소를 골라 한 줄로 배열하는 방법의 가짓수를 세자.

k

개의 원소를 고르는 방법의 수는

\textstyle\binom nk

이다. 선택된

k

개의 원소를 배열할 때, 첫 번째 자리에 둘 수 있는 원소는

k

개이며, 두 번째 자리는 남은

k-1

개 가운데 하나를 놓는다. 나머지 자리도 마찬가지다. 따라서,

n

개의 원소를 배열하는 방법은

:

\binom nkk!

가지가 있다. 다른 한편, 첫 번째 자리에 놓을 원소를

n

개 가운데 고르고, 두 번째 자리에 놓을 원소를

n-1

개 가운데 고르고, 남은 자리 역시 마찬가지로 반복하여 센 방법의 수는

:

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

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

2. 2. 조합의 수

집합 ''S''와 자연수 ''k''가 주어졌을 때, ''S''의 '''(중복 없는) ''k''-조합'''(''k''-combination (without repetition)^영어)은 ''S''의 ''k''개의 원소로 이루어진 부분집합을 말한다. ''n''개 원소의 유한 집합 ''S''에서 (중복 없이) ''k''개를 선택하는 조합의 수는 이항 계수

:

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

와 같다. (단,

0\le k\le n

).

이항 계수

\textstyle\binom nk

는 ''n''개 중에서 ''k''개를 택하는 방법"으로 읽으며, 다음과 같이 다양하게 적는다.

$C^n_k$
$C_n^k$
$_nC_k$
$^nC_k$
$C_{n,k}$
$C(n,k)$

이 공식은 조합론의 방법으로 쉽게 유도할 수 있다. ''n''개의 원소의 집합에서 ''k''개의 원소를 골라 한 줄로 배열하는 방법의 가짓수를 생각해보자. ''k''개의 원소를 고르는 방법의 수는

\textstyle\binom nk

이다. 선택된 ''k''개의 원소를 배열할 때, 첫 번째 자리에 둘 수 있는 원소는 ''k''개, 두 번째 자리는 남은 ''k''-1개 가운데 하나를 놓는 식으로 계산할 수 있다. 따라서, ''k''개의 원소를 배열하는 방법은

:

\binom nkk!

가지가 된다.

다른 방법으로, 첫 번째 자리에 놓을 원소를 ''n''개 가운데 고르고, 두 번째 자리에 놓을 원소를 ''n''-1개 가운데 고르는 식으로 ''k''번째 자리까지 반복하여 센 방법의 수는

:

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

이다. 두 가지 방법으로 센 수는 같아야 하므로 원하는 공식을 얻는다.^[5]^[6]^[7]

\tbinom nk

는 이항 정리의 계수로 나타나므로 이항 계수라고 한다. 모든 자연수 ''k''에 대해 다음 관계식으로 정의할 수 있다.

(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,

이 식에서 다음이 성립한다.

\binom{n}{0} = \binom{n}{n} = 1,

그리고 ''k'' > ''n''일 때,

\binom{n}{k} = 0

이다.

이항 계수는 여러 가지 방법으로 계산할 수 있다. 0 < ''k'' < ''n''일 때, 다음과 같은 재귀 관계를 사용할 수 있다.

\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k},

이는 파스칼의 삼각형을 구성하게 된다.

개별 이항 계수를 결정하려면 다음 공식을 사용하는 것이 더 실용적이다.

\binom nk = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.

''k''가 ''n''/2를 초과하는 경우 위 공식에는 분자와 분모에 공통적인 인수가 포함되며, 이를 약분하면 다음 관계를 얻는다.

\binom nk = \binom n{n-k},

(0 ≤ ''k'' ≤ ''n'')

기억하기 쉬운 공식은 다음과 같다.

\binom nk = \frac{n!}{k!(n-k)!},

여기서 ''n''!는 ''n''의 팩토리얼을 나타낸다.

2. 2. 1. 조합의 수 계산 예시 (한국 관련)

52장의 표준 카드 덱에서 5장의 카드를 뽑는 경우의 수는 다음과 같이 계산할 수 있다.^[8]

:

이는 포커에서 가능한 패의 가짓수가 된다.

45개의 숫자 중 6개를 맞추는 경우의 수는 다음과 같이 계산할 수 있다.

:

이는 로또에서 1등 당첨 확률을 계산하는 데 사용될 수 있다.

20명의 후보 중 3명의 대표를 선출하는 경우의 수는 다음과 같이 계산할 수 있다.

:

이는 한국의 정당, 조합, 시민단체 등에서 대표를 선출할 때 나올 수 있는 경우의 수를 나타낸다.

2. 3. 여러 가지 표현

이항 계수

\textstyle\binom nk

는 다음과 같이 다양하게 적는다.

$C^n_k$
$C_n^k$
$_nC_k$
$^nC_k$
$C_{n,k}$
$C(n,k)$

2. 4. 조합과 관련된 항등식

이항 계수 항등식

:

\binom nk=\binom n{n-k}

^[21]

:

\binom nk=\binom{n-1}k+\binom{n-1}{k-1}

은 조합론에서 직관적으로 해석할 수 있다.

$\binom nk=\binom n{n-k}$

:

k

개의 원소를 고르는 방법과

n-k

개의 원소를 버리는 방법은 일대일 대응함을 나타낸다.^[5] 즉, k개를 선택하는 것과 n-k개를 남기는 것은 같다.

$\binom nk=\binom{n-1}k+\binom{n-1}{k-1}$

:

k

개의 원소를 고를 때, 어떤 고정된 원소를 고르는 경우와 이 원소를 버리는 경우를 나누어 센 결과다. 즉, 고정된 원소를 제외한

n-1

개의 원소에서

k

개의 원소를 고르는 방법의 수를 세고, 고정된 원소를 고른 뒤 남은

n-1

개에서

k-1

개를 고르는 방법의 수를 세어 합하면 모든 방법의 수를 얻는다. 이는 파스칼의 삼각형을 구성하는 점화식에 해당한다.^[5]

2. 5. 생성 함수

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

:

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

^[5]^[6]^[7]^[18]^[19]^[20]

조합론적 관점에서, 다항식

(1+x)^n

의 각 항을 얻으려면

n

개의 이항식

1+x

에서 1 또는

x

중 하나를 선택하여 곱해야 한다. 따라서

x

의 차수가

k

인 항은 총

\textstyle\binom nk

개 만들어지며,

x^k

에는 계수

\textstyle\binom nk

가 붙는다.

3. 중복조합

'''중복조합'''은 집합에서 중복을 허용하여 원소를 선택하는 방법이다.

크기가 ''k''인 집합 ''S''(크기 ''n'')의 ''k''-'''중복 조합'''은 순서를 고려하지 않고 ''S''의 ''k''개의 원소를 선택하는 것이며, 중복이 허용된다. 예를 들어 {2, 1, 2}와 {1, 2, 2}는 같은 중복조합으로 취급된다. ''S''의 각 원소에 인덱스를 할당하고 ''S''의 원소를 대상의 ''종류''로 생각하면, $x_i$ 는 다중 부분집합에서 ''i'' 종류의 원소 수를 나타낼 수 있다. 크기 ''k''의 다중 부분집합의 수는 다음 디오판토스 방정식의 음이 아닌 정수 해의 수와 같다.^[11]

: $x_1 + x_2 + \ldots + x_n = k.$

''S''에 ''n''개의 원소가 있는 경우, ''k''-다중 부분집합의 수는 다음과 같이 나타낸다.

: $\left(\!\!\binom{n}{k}\!\!\right),$

이는 이항 계수와 유사한 표기법이며, 다음과 같이 이항 계수로도 표현할 수 있다.

: $\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.$

이 관계는 별과 막대기 표현을 사용하여 증명할 수 있다.^[13] 예를 들어 ''n'' = 4, ''k'' = 10 인 경우, 방정식의 해는 다음과 같이 표현할 수 있다.

: $\bigstar \bigstar \bigstar | \bigstar \bigstar | | \bigstar \bigstar \bigstar \bigstar \bigstar.$

이는 13개의 위치에 10개의 별을 배치하는 방법의 수와 같으므로, 4개의 원소를 가진 집합의 10-다중 부분집합의 수는 $\binom{13}{10} = \binom{13}{3} = 286$ 이다.^[14]

이항 계수와 마찬가지로,

n \ge 1, k \ge 0

인 경우, 다음과 같은 관계가 성립한다.

:

\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).

이 항등식은 위 표현에서 별과 막대기를 바꾸어 얻을 수 있다.^[15]

3. 1. 정의

집합 ${\displaystyle S}$ 및 자연수 ${\displaystyle k}$가 주어졌을 때, ${\displaystyle S}$의 '''${\displaystyle k}$'''-중복조합'''은 ${\displaystyle S}$의 원소들로 구성된, 크기 ${\displaystyle k}$의 중복집합이다.^[11] ${\displaystyle n}$개 원소의 집합 ${\displaystyle S=\{s_{1},s_{2},\dots ,s_{n}\}}$의 ${\displaystyle k}$-중복조합의 수는 다음과 같다.

:

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

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

${\displaystyle \left(\!\!\!\binom nk\!\!\!\right)}$^[12]
${\displaystyle _{n}H_{k}}$

중복조합의 수가 ${\displaystyle \textstyle \binom{n+k-1}k}$인 것은 다음과 같이 증명할 수 있다. ${\displaystyle \{a_{1},\cdots ,a_{k}\}}$가 ${\displaystyle \{1,\dots ,n\}}$의 원소들로 구성된 크기 ${\displaystyle k}$의 중복집합이고,

:

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

라면,

:

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

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

:

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

:

b_{1}

이 주어졌을 때,

:

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

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

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

:

|{\bigcirc}{\bigcirc}{\bigcirc}|{\bigcirc}{\bigcirc}

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

:

{\bigcirc}|{\bigcirc}{\bigcirc}{\bigcirc}|{\bigcirc}

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

3. 2. 중복조합의 수

집합

S

와 자연수

k

가 주어졌을 때,

S

의 '''

k

-중복조합'''은

S

의 원소들로 구성된 크기

k

의 중복집합이다. 이는 중복을 허용하여

S

에서

k

개의 원소를 선택하는 방법으로, 순서는 고려하지 않는다. 예를 들어, {1, 2, 2}는 {2, 1, 2}와 같은 중복조합으로 취급한다.

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

중복조합의 수는

\left(\!\!\!\binom nk\!\!\!\right)

또는

_nH_k

등으로 표기한다.

S

의 각 원소에 인덱스를 할당하고,

S

의 원소를 대상의 ''종류''로 생각하면,

x_i

는 다중 부분집합에서 ''i'' 종류의 원소 수를 나타낼 수 있다. 그러면 크기

k

의 다중 부분집합의 수는 다음 디오판토스 방정식의 음이 아닌 정수 해의 수와 같다.^[11]

:

x_1 + x_2 + \ldots + x_n = k.

3. 2. 1. 중복조합의 수 증명

''S''에 ''n''개의 원소가 있을 때, ''k''-다중 부분집합의 수를 나타내는 식은 다음과 같다.

:

\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.

이 관계는 별과 막대기 표현을 사용하여 쉽게 증명할 수 있다.^[13]

위 디오판토스 방정식의 해는

x_1

개의 '별', 구분 기호('막대기'), 그 다음

x_2

개의 별, 다른 구분 기호 등으로 나타낼 수 있다. 이 표현에서 별의 총 개수는 ''k''이고 막대기의 개수는 ''n'' - 1이다(n개의 부분으로 나누려면 n-1개의 구분 기호가 필요). 따라서 ''k'' + ''n'' - 1 (또는 ''n'' + ''k'' - 1)개의 기호(별과 막대기) 문자열은 문자열에 ''k''개의 별이 있는 경우 해에 해당한다. 어떤 해든 ''k'' + ''n'' − 1개의 위치 중에서 ''k''개의 위치를 선택하여 별을 배치하고 나머지 위치를 막대로 채움으로써 나타낼 수 있다. 예를 들어, 방정식

x_1 + x_2 + x_3 + x_4 = 10

( ''n'' = 4이고 ''k'' = 10)의 해

x_1 = 3, x_2 = 2, x_3 = 0, x_4 = 5

는 ^[14]

:

\bigstar \bigstar \bigstar | \bigstar \bigstar | | \bigstar \bigstar \bigstar \bigstar \bigstar.

로 나타낼 수 있다. 이러한 문자열의 수는 13개의 위치에 10개의 별을 배치하는 방법의 수인

\binom{13}{10} = \binom{13}{3} = 286

이며, 이는 4개의 원소를 가진 집합의 10-다중 부분집합의 수이다.

이항 계수와 마찬가지로 이러한 다중 선택 표현식 사이에는 여러 관계가 있다. 예를 들어,

n \ge 1, k \ge 0

인 경우,

:

\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).

이 항등식은 위 표현에서 별과 막대기를 바꾸어 얻을 수 있다.^[15]

3. 3. 생성 함수

중복조합의 수를 나타내는 생성 함수는 다음과 같다.^[11]^[12]^[13]^[14]^[15]

:

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

좌변의

(1-x)^{-1}

을 멱급수로 전개하면

1+x+x^2+\cdots

이다.

n

개의 멱급수에서 항

x^{m_i}

(

i=1,\dots,n

)을 선택하는 방법은 각

i

의 중복도가

m_i

인 중복집합을 선택하는 방법과 일대일 대응한다.

n

개의 항의 곱이

x^k

인 경우는 중복도의 합이

:

m_1+\cdots+m_n=k

인 경우이다. 즉, 크기

k

의 중복집합에 대응한다. 따라서

x^k

의 계수는

\textstyle\binom{n+k-1}k

이다.

4. k-조합 열거

주어진 집합 ''S''(원소의 개수 ''n'')의 모든 ''k''-조합은 특정 순서로 열거할 수 있으며, 이는 $\tbinom nk$ 개의 정수 구간과 해당 ''k''-조합 집합 사이의 전단사 함수를 설정하는 것이다. ''S''가 이미 정렬되어 있다고 가정하면(예: ''S'' = {1, 2, ..., ''n''}), ''k''-조합을 정렬하는 두 가지 자연스러운 방법이 있는데, 가장 작은 원소부터 비교하거나 가장 큰 원소부터 비교하는 것이다. 후자는 ''S''에 가장 큰 원소를 추가하면 열거의 초기 부분이 변경되지 않고 이전 ''k''-조합 뒤에 더 큰 집합의 새로운 ''k''-조합만 추가된다는 장점이 있다. 이 과정을 반복하면 더 큰 집합의 ''k''-조합을 사용하여 열거를 무한정 확장할 수 있다. 또한 정수 구간이 0부터 시작한다면, 열거의 특정 위치 ''i''에 있는 ''k''-조합을 ''i''에서 쉽게 계산할 수 있으며, 이렇게 얻은 전단사 함수를 조합 수 체계라고 한다. 계산 수학에서는 "순위"/"순위 매기기"와 "역순위 매기기"라고도 부른다.^[9]^[10]

''k''-조합을 열거하는 방법에는 여러 가지가 있다. 한 가지 방법은 선택된 원소의 ''k''개의 색인 번호를 추적하는 것이다. {0 .. ''k''−1}(0-based) 또는 {1 .. ''k''}(1-based)를 첫 번째 허용되는 ''k''-조합으로 시작하고, 그 다음 두 개의 동일한 색인 번호가 생성되지 않도록 가장 작은 색인 번호를 반복적으로 증가시키면서 동시에 더 작은 모든 색인 번호는 초기 값으로 재설정하여 다음 허용되는 ''k''-조합으로 이동한다.

5. 모든 k에 대한 k-조합의 수

n개의 원소를 가진 집합의 모든 부분집합의 수는 $2^n$ 이다. 조합의 관점에서, $\sum_{0\leq{k}\leq{n}}\binom n k = 2^n$ 는 파스칼의 삼각형에서 이항 계수의 ''n''번째 행(0부터 세기 시작)의 합이다. 이러한 조합(부분집합)은 0부터 2^''n'' − 1까지 세는 2진수의 1의 자릿수로 열거할 수 있는데, 여기서 각 자릿수 위치는 n개의 원소 집합의 원소이다.^[5]

예를 들어 1부터 3까지 번호가 매겨진 3장의 카드가 주어지면, 공집합을 포함하여 다음과 같이 8개의 서로 다른 조합(부분집합)이 있다.

$| \{ \{\} ; \{1\} ; \{2\} ; \{1, 2\} ; \{3\} ; \{1, 3\} ; \{2, 3\} ; \{1, 2, 3\} \}| = 2^3 = 8$

이러한 부분집합을 (같은 순서로) 2진수로 나타내면 다음과 같다.

0 – 000
1 – 001
2 – 010
3 – 011
4 – 100
5 – 101
6 – 110
7 – 111

6. 확률: 무작위 조합 샘플링

주어진 집합에서 무작위로 조합을 선택하는 여러 알고리즘이 있다. 기각 샘플링은 큰 표본 크기의 경우 매우 느리다. 크기 ''n''의 모집단에서 ''k''-조합을 효율적으로 선택하는 한 가지 방법은 모집단의 각 요소를 반복하고 각 단계에서 $\frac{k-\#\text{samples chosen}}{n- \#\text{samples visited}}$ 의 동적으로 변하는 확률로 해당 요소를 선택하는 것이다(저수지 샘플링 참조). 또 다른 방법은 $\textstyle\binom nk$ 보다 작은 무작위 음이 아닌 정수를 선택하고 조합 수 체계를 사용하여 조합으로 변환하는 것이다.

7. 상자에 물건 넣기

조합을 일반화하여 ''n''개의 물건을 여러 상자에 넣는 방법을 고려할 수 있다. 이때 각 상자에 들어가는 물건의 수는 다항 계수로 주어진다. 다항 계수는 다음과 같이 표현된다.

${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!},$

여기서 ''n''은 물건의 총 개수, ''m''은 상자의 개수, $k_i$ 는 ''i''번째 상자에 들어가는 물건의 개수를 의미한다.^[5]^[6]^[7]

이러한 다항 계수는 다음과 같이 이해할 수 있다. 먼저 ''1''부터 ''n''까지 번호가 매겨진 ''n''개의 물건을 준비한다. $1, 2, \ldots, k_1$ 번호가 매겨진 항목을 순서대로 첫 번째 상자에 넣고, $k_1+1, k_1+2, \ldots, k_2$ 번호가 매겨진 항목을 순서대로 두 번째 상자에 넣는 식으로 진행한다. 이 경우 ''n''개의 서로 다른 물건을 배열하는 방법은 ''n!''가지가 된다. 하지만, 상자 안의 물건 순서는 중요하지 않으므로 중복이 발생한다. 각 상자 안에서 물건을 배열하는 경우의 수는 $k_1!\, k_2! \cdots k_m!$ 이므로, 전체 경우의 수를 이 값으로 나누어 다항 계수를 얻는다.

예를 들어, 5개의 물건을 3개의 상자에 각각 2개, 2개, 1개씩 넣는 경우의 수는 다음과 같이 계산된다.

${5 \choose 2, 2, 1} = \frac{5!}{2!\, 2!\, 1!} = 30$

이항 계수는 다항 계수의 특수한 경우로, 두 개의 상자에 물건을 넣는 경우를 나타낸다. 예를 들어, ''n''개의 물건 중 ''k''개를 선택하는 조합의 수는 다음과 같이 표현할 수 있다.

$\binom nk = {n \choose k, n-k} = \frac{n!}{k!(n-k)!}.$

이는 ''k''개의 물건은 선택된 상자에, 나머지 ''n-k''개의 물건은 선택되지 않은 상자에 넣는 경우로 해석할 수 있다.

8. 조합 관련 추가 정보 (한국 관련)

주어진 원본 소스에 내용이 없으므로, 작성할 내용이 없습니다.

참조

_[1] 서적 A Modern Course in Statistical Physics WILEY-VCH
_[2] harvnb
_[3] harvnb
_[4] harv
_[5] harvnb
_[6] 서적 High School Textbook for full-time student (Required) Mathematics Book II B People's Education Press 2006-06-00
_[7] 서적 人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press) http://www.shuxue9.c[...] People's Education Press
_[8] harvnb
_[9] 웹사이트 Generating Elementary Combinatorial Objects http://www.site.uott[...] 2017-04-10
_[10] 웹사이트 SAGE : Subsets http://www.sagemath.[...] 2017-04-10
_[11] harvnb
_[12] harvnb
_[13] Wiki Stars and bars (combinatorics)
_[14] harvnb
_[15] harvnb
_[16] harvnb
_[17] harvnb
_[18] 서적 Analyse combinatoire élémentaire https://books.google[...]
_[19] 서적 Problèmes choisis de mathématiques supérieures https://books.google[...]
_[20] 서적 なっとくする数学記号講談社
_[21] 웹사이트 Binomial coefficients algorithm https://gmplib.org/m[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com