수학 에서 조합 (組合, 문화어 : 무이, 영어 : combination )은 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법이다. 조합의 수는 이항 계수 로 주어진다.
5개 원소의 집합의 3원소 부분집합의 수는
(
5
3
)
=
10
{\displaystyle \textstyle {\binom {5}{3}}=10}
이다.
집합
S
{\displaystyle S}
와 자연수
k
{\displaystyle k}
가 주어졌을 때,
S
{\displaystyle S}
의 (중복 없는)
k
{\displaystyle k}
-조합 (영어 :
k
{\displaystyle k}
-combination (without repetition) )은
S
{\displaystyle S}
의
k
{\displaystyle k}
개의 원소로 이루어진 부분집합 을 일컫는다. 만약
S
=
{
s
1
,
s
2
,
…
,
s
n
}
{\displaystyle S=\{s_{1},s_{2},\dots ,s_{n}\}}
가
n
{\displaystyle n}
개 원소의 유한 집합 이며,
0
≤
k
≤
n
{\displaystyle 0\leq k\leq n}
이라면,
S
{\displaystyle S}
의
k
{\displaystyle k}
-조합의 수는 이항 계수
(
n
k
)
=
n
(
n
−
1
)
⋯
(
n
−
k
+
1
)
k
!
=
n
!
k
!
(
n
−
k
)
!
{\displaystyle {\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}={\frac {n!}{k!(n-k)!}}}
와 같다. 이항 계수
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
는 다음과 같이 다양하게 적는다.
C
k
n
{\displaystyle C_{k}^{n}}
C
n
k
{\displaystyle C_{n}^{k}}
n
C
k
{\displaystyle _{n}C_{k}}
n
C
k
{\displaystyle ^{n}C_{k}}
C
n
,
k
{\displaystyle C_{n,k}}
C
(
n
,
k
)
{\displaystyle C(n,k)}
조합의 수의 공식은 조합론 의 방법으로 쉽게 유도할 수 있다.
n
{\displaystyle n}
개의 원소의 집합에서
k
{\displaystyle k}
개의 원소를 골라 한 줄로 배열하는 방법의 가짓수를 세자.
k
{\displaystyle k}
개의 원소를 고르는 방법의 수는
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
이다. 선택된
k
{\displaystyle k}
개의 원소를 배열할 때, 첫 번째 자리에 둘 수 있는 원소는
k
{\displaystyle k}
개이며, 두 번째 자리는 남은
k
−
1
{\displaystyle k-1}
개 가운데 하나를 놓는다. 나머지 자리도 마찬가지다. 따라서,
n
{\displaystyle n}
개의 원소를 배열하는 방법은
(
n
k
)
k
!
{\displaystyle {\binom {n}{k}}k!}
가지가 있다. 다른 한편, 첫 번째 자리에 놓을 원소를
n
{\displaystyle n}
개 가운데 고르고, 두 번째 자리에 놓을 원소를
n
−
1
{\displaystyle n-1}
개 가운데 고르고, 남은 자리 역시 마찬가지로 반복하여 센 방법의 수는
n
(
n
−
1
)
⋯
(
n
−
k
+
1
)
{\displaystyle n(n-1)\cdots (n-k+1)}
이다. 세는 법이 다를 때 얻는 수가 같아야 하므로 원하는 공식을 얻는다.
이항 계수 들의 파스칼의 삼각형
이항 계수 항등식
(
n
k
)
=
(
n
n
−
k
)
{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
{\displaystyle {\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}}
역시 조합론에서 직관적으로 해석할 수 있다. 전자는
k
{\displaystyle k}
개의 원소를 고르는 방법과
n
−
k
{\displaystyle n-k}
개의 원소를 버리는 방법은 일대일 대응 함을 나타낸다. 후자는
k
{\displaystyle k}
개의 원소를 고를 때, 어떤 고정된 원소를 고르는 경우와 이 원소를 버리는 경우를 나누어 센 결과다. 즉, 고정된 원소를 제외한
n
−
1
{\displaystyle n-1}
개의 원소에서
k
{\displaystyle k}
개의 원소를 고르는 방법의 수를 세고, 고정된 원소를 고른 뒤 남은
n
−
1
{\displaystyle n-1}
개에서
k
−
1
{\displaystyle k-1}
개를 고르는 방법의 수를 세어 합하면 모든 방법의 수를 얻는다.
이항 계수 는 다음과 같이 생성 함수 를 사용하여 정의할 수 있다.
(
1
+
x
)
n
=
∑
k
=
0
n
(
n
k
)
x
k
{\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}}
조합론의 관점에서, 다항식
(
1
+
x
)
n
{\displaystyle (1+x)^{n}}
의 각 항을 얻기 위해서는
n
{\displaystyle n}
개의 이항식
1
+
x
{\displaystyle 1+x}
에서 1 또는
x
{\displaystyle x}
가운데 하나를 선택하여 곱하여야 한다. 따라서,
x
{\displaystyle x}
의 차수가
k
{\displaystyle k}
인 항은 총
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
개가 만들어진다. 즉,
x
k
{\displaystyle x^{k}}
에는 계수
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
가 붙는다.
5개의 원소의 집합의 크기 3의 중복집합의 수는
(
7
3
)
=
35
{\displaystyle \textstyle {\binom {7}{3}}=35}
이다.
집합
S
{\displaystyle S}
및 자연수
k
{\displaystyle k}
가 주어졌다고 하자.
S
{\displaystyle S}
의
k
{\displaystyle k}
-중복조합 (영어 :
k
{\displaystyle k}
-combination with repetitions )은
S
{\displaystyle S}
의 원소들로 구성된, 크기
k
{\displaystyle k}
의 중복집합 이다.
n
{\displaystyle n}
개 원소의 집합
S
=
{
s
1
,
s
2
,
…
,
s
n
}
{\displaystyle S=\{s_{1},s_{2},\dots ,s_{n}\}}
의
k
{\displaystyle k}
-중복조합의 수는
(
n
+
k
−
1
k
)
=
(
n
+
k
−
1
n
−
1
)
=
(
−
1
)
k
(
−
n
k
)
{\displaystyle {\binom {n+k-1}{k}}={\binom {n+k-1}{n-1}}=(-1)^{k}{\binom {-n}{k}}}
이다. 중복조합의 수
(
n
+
k
−
1
k
)
{\displaystyle \textstyle {\binom {n+k-1}{k}}}
의 표기로는 다음이 있다.
(
(
n
k
)
)
{\displaystyle \left(\!\!\!{\binom {n}{k}}\!\!\!\right)}
n
H
k
{\displaystyle _{n}H_{k}}
중복조합의 수가
(
n
+
k
−
1
k
)
{\displaystyle \textstyle {\binom {n+k-1}{k}}}
인 사실의 증명은 다음과 같다. 만약
{
a
1
,
⋯
,
a
k
}
{\displaystyle \{a_{1},\cdots ,a_{k}\}}
가
{
1
,
…
,
n
}
{\displaystyle \{1,\dots ,n\}}
의 원소들로 구성된 크기
k
{\displaystyle k}
의 중복집합이며,
a
1
≤
a
2
≤
⋯
≤
a
k
{\displaystyle a_{1}\leq a_{2}\leq \cdots \leq a_{k}}
라면,
{
a
1
,
a
2
+
1
,
…
,
a
k
+
k
−
1
}
{\displaystyle \{a_{1},a_{2}+1,\dots ,a_{k}+k-1\}}
는
{
1
,
…
,
n
+
k
−
1
}
{\displaystyle \{1,\dots ,n+k-1\}}
의
k
{\displaystyle k}
원소 부분집합이다. 반대로,
{
1
,
…
,
n
+
k
−
1
}
{\displaystyle \{1,\dots ,n+k-1\}}
의
k
{\displaystyle k}
원소 부분집합
{
b
1
,
…
,
b
k
}
{\displaystyle \{b_{1},\dots ,b_{k}\}}
b
1
<
b
2
<
⋯
<
b
k
{\displaystyle b_{1}<b_{2}<\cdots <b_{k}}
이 주어졌을 때,
{
b
1
,
b
2
−
1
,
…
,
b
k
−
k
+
1
}
{\displaystyle \{b_{1},b_{2}-1,\dots ,b_{k}-k+1\}}
는
{
1
,
…
,
n
}
{\displaystyle \{1,\dots ,n\}}
의 원소들로 구성된 크기
k
{\displaystyle k}
의 중복집합이다. 이는
{
1
,
…
,
n
}
{\displaystyle \{1,\dots ,n\}}
의 원소들로 구성된 크기
k
{\displaystyle k}
의 중복집합들과
{
1
,
…
,
n
+
k
−
1
}
{\displaystyle \{1,\dots ,n+k-1\}}
의 크기
k
{\displaystyle k}
의 부분집합들 사이의 일대일 대응 을 정의한다. 따라서 이들의 수는 같다. 후자의 수가
(
n
+
k
−
1
k
)
{\displaystyle \textstyle {\binom {n+k-1}{k}}}
이므로 원하는 결론을 얻는다.
이와 다른 기하학 적 증명이 존재한다.
(
n
+
k
−
1
k
)
{\displaystyle \textstyle {\binom {n+k-1}{k}}}
는
n
−
1
{\displaystyle n-1}
개의 막대와
k
{\displaystyle k}
개의 공으로 만들 수 있는 (길이
n
+
k
−
1
{\displaystyle n+k-1}
의) 문자열의 수와 같다. 이제, 이와 같은 문자열을 다음과 같이 해석하여,
{
1
,
…
,
n
}
{\displaystyle \{1,\dots ,n\}}
의 크기
k
{\displaystyle k}
의 중복집합으로 간주하자.
n
−
1
{\displaystyle n-1}
개의 막대는 두 막대 사이의 공간과 양쪽 끝의 공간을 포함하여 총
n
{\displaystyle n}
개의 공간을 만든다. 각 공간에 1부터
n
{\displaystyle n}
까지 번호를 매긴다.
i
{\displaystyle i}
번째 공간에 놓인 공의 수만큼 원소
i
{\displaystyle i}
를 중복하여 취한다. 총
k
{\displaystyle k}
개의 공이 있으므로 크기
k
{\displaystyle k}
의 중복집합이 만들어진다. 예를 들어,
n
=
3
{\displaystyle n=3}
,
k
=
5
{\displaystyle k=5}
인 경우, 문자열
|
◯
◯
◯
|
◯
◯
{\displaystyle |{\bigcirc }{\bigcirc }{\bigcirc }|{\bigcirc }{\bigcirc }}
은 중복집합
{
2
,
2
,
3
,
3
,
3
}
{\displaystyle \{2,2,3,3,3\}}
을 나타내며, 문자열
◯
|
◯
◯
◯
|
◯
{\displaystyle {\bigcirc }|{\bigcirc }{\bigcirc }{\bigcirc }|{\bigcirc }}
은 중복집합
{
1
,
2
,
2
,
2
,
3
}
{\displaystyle \{1,2,2,2,3\}}
을 나타낸다. 이는
{
1
,
…
,
n
}
{\displaystyle \{1,\dots ,n\}}
으로 구성된 크기
k
{\displaystyle k}
의 중복집합들과
n
−
1
{\displaystyle n-1}
개와
k
{\displaystyle k}
개의 두 알파벳으로 구성된 문자열 사이에 일대일 대응을 이루며, 따라서 중복조합의 수는 문자열의 수
(
n
+
k
−
1
k
)
{\displaystyle \textstyle {\binom {n+k-1}{k}}}
와 같다.
중복조합의 수의 생성 함수 는 다음과 같다.
(
1
−
x
)
−
n
=
∑
k
=
0
∞
(
−
n
k
)
(
−
x
)
k
=
∑
k
=
0
∞
(
n
+
k
−
1
k
)
x
k
{\displaystyle (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
{\displaystyle (1-x)^{-1}}
을 멱급수 로 전개하면
1
+
x
+
x
2
+
⋯
{\displaystyle 1+x+x^{2}+\cdots }
이다.
n
{\displaystyle n}
개의 멱급수에서 항
x
m
i
{\displaystyle x^{m_{i}}}
(
i
=
1
,
…
,
n
{\displaystyle i=1,\dots ,n}
)을 선택하는 방법은 각
i
{\displaystyle i}
의 중복도가
m
i
{\displaystyle m_{i}}
인 중복집합 을 선택하는 방법과 일대일 대응 한다.
n
{\displaystyle n}
개의 항의 곱이
x
k
{\displaystyle x^{k}}
인 경우는 중복도의 합이
m
1
+
⋯
+
m
n
=
k
{\displaystyle m_{1}+\cdots +m_{n}=k}
인 경우이다. 즉, 크기
k
{\displaystyle k}
의 중복집합에 대응한다. 따라서 결국
x
k
{\displaystyle x^{k}}
의 계수는
(
n
+
k
−
1
k
)
{\displaystyle \textstyle {\binom {n+k-1}{k}}}
이다.