조합 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻}}
[[수학]]에서 '''조합'''(組合, {{문화어|무이}}, {{llang|en|combination}})은 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법이다. 조합의 수는 [[이항 계수]]로 주어진다.

== 조합 ==
=== 정의 ===
[[파일:Combinations without repetition; 5 choose 3.svg|섬네일|5개 원소의 집합의 3원소 부분집합의 수는 <math>\textstyle\binom 53=10</math>이다.]]
[[집합]] <math>S</math>와 [[자연수]] <math>k</math>가 주어졌을 때, <math>S</math>의 '''(중복 없는) <math>k</math>-조합'''({{llang|en|<math>k</math>-combination (without repetition)}})은 <math>S</math>의 <math>k</math>개의 원소로 이루어진 [[부분집합]]을 일컫는다. 만약
:<math>S=\{s_1,s_2,\dots,s_n\}</math>
가 <math>n</math>개 원소의 [[유한 집합]]이며, <math>0\le k\le n</math>이라면, <math>S</math>의 <math>k</math>-조합의 수는 [[이항 계수]]
:<math>\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}=\frac{n!}{k!(n-k)!}</math>
와 같다. 이항 계수 <math>\textstyle\binom nk</math>는 다음과 같이 다양하게 적는다.
* <math>C^n_k</math>
* <math>C_n^k</math>
* <math>_nC_k</math>
* <math>^nC_k</math>
* <math>C_{n,k}</math>
* <math>C(n,k)</math>
조합의 수의 공식은 [[조합론]]의 방법으로 쉽게 유도할 수 있다. <math>n</math>개의 원소의 집합에서 <math>k</math>개의 원소를 골라 한 줄로 배열하는 방법의 가짓수를 세자. <math>k</math>개의 원소를 고르는 방법의 수는 <math>\textstyle\binom nk</math>이다. 선택된 <math>k</math>개의 원소를 배열할 때, 첫 번째 자리에 둘 수 있는 원소는 <math>k</math>개이며, 두 번째 자리는 남은 <math>k-1</math>개 가운데 하나를 놓는다. 나머지 자리도 마찬가지다. 따라서, <math>n</math>개의 원소를 배열하는 방법은
:<math>\binom nkk!</math>
가지가 있다. 다른 한편, 첫 번째 자리에 놓을 원소를 <math>n</math>개 가운데 고르고, 두 번째 자리에 놓을 원소를 <math>n-1</math>개 가운데 고르고, 남은 자리 역시 마찬가지로 반복하여 센 방법의 수는
:<math>n(n-1)\cdots(n-k+1)</math>
이다. 세는 법이 다를 때 얻는 수가 같아야 하므로 원하는 공식을 얻는다.

=== 항등식 ===
[[파일:PascalTriangleAnimated2.gif|섬네일|[[이항 계수]]들의 [[파스칼의 삼각형]]]]
[[이항 계수]] 항등식
:<math>\binom nk=\binom n{n-k}</math>
:<math>\binom nk=\binom{n-1}k+\binom{n-1}{k-1}</math>
역시 조합론에서 직관적으로 해석할 수 있다. 전자는 <math>k</math>개의 원소를 고르는 방법과 <math>n-k</math>개의 원소를 버리는 방법은 [[일대일 대응]]함을 나타낸다. 후자는 <math>k</math>개의 원소를 고를 때, 어떤 고정된 원소를 고르는 경우와 이 원소를 버리는 경우를 나누어 센 결과다. 즉, 고정된 원소를 제외한 <math>n-1</math>개의 원소에서 <math>k</math>개의 원소를 고르는 방법의 수를 세고, 고정된 원소를 고른 뒤 남은 <math>n-1</math>개에서 <math>k-1</math>개를 고르는 방법의 수를 세어 합하면 모든 방법의 수를 얻는다.

=== 생성 함수 ===
[[이항 계수]]는 다음과 같이 [[생성 함수]]를 사용하여 정의할 수 있다.
:<math>(1+x)^n=\sum_{k=0}^n\binom nkx^k</math>
조합론의 관점에서, 다항식 <math>(1+x)^n</math>의 각 항을 얻기 위해서는 <math>n</math>개의 이항식 <math>1+x</math>에서 1 또는 <math>x</math> 가운데 하나를 선택하여 곱하여야 한다. 따라서, <math>x</math>의 차수가 <math>k</math>인 항은 총 <math>\textstyle\binom nk</math>개가 만들어진다. 즉, <math>x^k</math>에는 계수 <math>\textstyle\binom nk</math>가 붙는다.

== 중복조합 ==
=== 정의 ===
[[파일:Combinations with repetition; 5 multichoose 3.svg|섬네일|370픽셀|5개의 원소의 집합의 크기 3의 중복집합의 수는 <math>\textstyle\binom 73=35</math>이다.]]
[[집합]] <math>S</math> 및 [[자연수]] <math>k</math>가 주어졌다고 하자. <math>S</math>의 '''<math>k</math>-중복조합'''({{llang|en|<math>k</math>-combination with repetitions}})은 <math>S</math>의 원소들로 구성된, 크기 <math>k</math>의 [[중복집합]]이다. <math>n</math>개 원소의 집합 <math>S=\{s_1,s_2,\dots,s_n\}</math>의 <math>k</math>-중복조합의 수는
:<math>\binom{n+k-1}k=\binom{n+k-1}{n-1}=(-1)^k\binom{-n}k</math>
이다. 중복조합의 수 <math>\textstyle\binom{n+k-1}k</math>의 표기로는 다음이 있다.
* <math>\left(\!\!\!\binom nk\!\!\!\right)</math>
* <math>_nH_k</math>
중복조합의 수가 <math>\textstyle\binom{n+k-1}k</math>인 사실의 증명은 다음과 같다. 만약 <math>\{a_1,\cdots,a_k\}</math>가 <math>\{1,\dots,n\}</math>의 원소들로 구성된 크기 <math>k</math>의 중복집합이며,
:<math>a_1\le a_2\le\cdots\le a_k</math>
라면,
:<math>\{a_1,a_2+1,\dots,a_k+k-1\}</math>
는 <math>\{1,\dots,n+k-1\}</math>의 <math>k</math>원소 부분집합이다. 반대로, <math>\{1,\dots,n+k-1\}</math>의 <math>k</math>원소 부분집합
:<math>\{b_1,\dots,b_k\}</math>
:<math>b_1<b_2<\cdots<b_k</math>
이 주어졌을 때,
:<math>\{b_1,b_2-1,\dots,b_k-k+1\}</math>
는 <math>\{1,\dots,n\}</math>의 원소들로 구성된 크기 <math>k</math>의 중복집합이다. 이는 <math>\{1,\dots,n\}</math>의 원소들로 구성된 크기 <math>k</math>의 중복집합들과 <math>\{1,\dots,n+k-1\}</math>의 크기 <math>k</math>의 부분집합들 사이의 [[일대일 대응]]을 정의한다. 따라서 이들의 수는 같다. 후자의 수가 <math>\textstyle\binom{n+k-1}k</math>이므로 원하는 결론을 얻는다.

이와 다른 [[기하학]]적 증명이 존재한다. <math>\textstyle\binom{n+k-1}k</math>는 <math>n-1</math>개의 막대와 <math>k</math>개의 공으로 만들 수 있는 (길이 <math>n+k-1</math>의) 문자열의 수와 같다. 이제, 이와 같은 문자열을 다음과 같이 해석하여, <math>\{1,\dots,n\}</math>의 크기 <math>k</math>의 중복집합으로 간주하자. <math>n-1</math>개의 막대는 두 막대 사이의 공간과 양쪽 끝의 공간을 포함하여 총 <math>n</math>개의 공간을 만든다. 각 공간에 1부터 <math>n</math>까지 번호를 매긴다. <math>i</math>번째 공간에 놓인 공의 수만큼 원소 <math>i</math>를 중복하여 취한다. 총 <math>k</math>개의 공이 있으므로 크기 <math>k</math>의 중복집합이 만들어진다. 예를 들어, <math>n=3</math>, <math>k=5</math>인 경우, 문자열
:<math>|{\bigcirc}{\bigcirc}{\bigcirc}|{\bigcirc}{\bigcirc}</math>
은 중복집합 <math>\{2,2,3,3,3\}</math>을 나타내며, 문자열
:<math>{\bigcirc}|{\bigcirc}{\bigcirc}{\bigcirc}|{\bigcirc}</math>
은 중복집합 <math>\{1,2,2,2,3\}</math>을 나타낸다. 이는 <math>\{1,\dots,n\}</math>으로 구성된 크기 <math>k</math>의 중복집합들과 <math>n-1</math>개와 <math>k</math>개의 두 알파벳으로 구성된 문자열 사이에 일대일 대응을 이루며, 따라서 중복조합의 수는 문자열의 수 <math>\textstyle\binom{n+k-1}k</math>와 같다.

=== 생성 함수 ===
중복조합의 수의 [[생성 함수]]는 다음과 같다.
:<math>(1-x)^{-n}=\sum_{k=0}^\infty\binom{-n}k(-x)^k=\sum_{k=0}^\infty\binom{n+k-1}kx^k</math>
좌변의 <math>(1-x)^{-1}</math>을 [[멱급수]]로 전개하면 <math>1+x+x^2+\cdots</math>이다. <math>n</math>개의 멱급수에서 항 <math>x^{m_i}</math> (<math>i=1,\dots,n</math>)을 선택하는 방법은 각 <math>i</math>의 중복도가 <math>m_i</math>인 [[중복집합]]을 선택하는 방법과 [[일대일 대응]]한다. <math>n</math>개의 항의 곱이 <math>x^k</math>인 경우는 중복도의 합이
:<math>m_1+\cdots+m_n=k</math>
인 경우이다. 즉, 크기 <math>k</math>의 중복집합에 대응한다. 따라서 결국 <math>x^k</math>의 계수는 <math>\textstyle\binom{n+k-1}k</math>이다.

== 참고 문헌 ==
* {{서적 인용
|url=http://math.mit.edu/~rstan/ec/ec1/
|성=Stanley
|이름=Richard P.
|제목=Enumerative Combinatorics. Volume 1
|언어=en
|판=2
|총서=Cambridge Studies in Advanced Mathematics
|권=49
|출판사=Cambridge University Press
|위치=Cambridge
|날짜=2012
|mr=2868112
|zbl=1247.05003
|isbn=978-1-107-60262-5
}}

== 외부 링크 ==
* {{eom|title=Combination}}
* {{매스월드|id=Combination|title=Combination}}

== 같이 보기 ==
* [[순열]]
* [[뤼카의 정리]]

[[분류:조합론]]