조합

수학에서 조합(組合, , )은 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법이다. 조합의 수는 이항 계수로 주어진다.

 조합 
 정의 
섬네일|5개 원소의 집합의 3원소 부분집합의 수는 이다.
집합 와 자연수 가 주어졌을 때, 의 (중복 없는) -조합()은 의 개의 원소로 이루어진 부분집합을 일컫는다. 만약

가 개 원소의 유한 집합이며, 이라면, 의 -조합의 수는 이항 계수

와 같다. 이항 계수 는 다음과 같이 다양하게 적는다.






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

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

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

 항등식 
섬네일|이항 계수들의 파스칼의 삼각형
이항 계수 항등식

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

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

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

 중복조합 
 정의 
섬네일|370픽셀|5개의 원소의 집합의 크기 3의 중복집합의 수는 이다.
집합  및 자연수 가 주어졌다고 하자. 의 -중복조합()은 의 원소들로 구성된, 크기 의 중복집합이다. 개 원소의 집합 의 -중복조합의 수는

이다. 중복조합의 수 의 표기로는 다음이 있다.


중복조합의 수가 인 사실의 증명은 다음과 같다. 만약 가 의 원소들로 구성된 크기 의 중복집합이며,

라면,

는 의 원소 부분집합이다. 반대로, 의 원소 부분집합

이 주어졌을 때,

는 의 원소들로 구성된 크기 의 중복집합이다. 이는 의 원소들로 구성된 크기 의 중복집합들과 의 크기 의 부분집합들 사이의 일대일 대응을 정의한다. 따라서 이들의 수는 같다. 후자의 수가 이므로 원하는 결론을 얻는다.

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

은 중복집합 을 나타내며, 문자열

은 중복집합 을 나타낸다. 이는 으로 구성된 크기 의 중복집합들과 개와 개의 두 알파벳으로 구성된 문자열 사이에 일대일 대응을 이루며, 따라서 중복조합의 수는 문자열의 수 와 같다.

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

좌변의 을 멱급수로 전개하면 이다. 개의 멱급수에서 항  ()을 선택하는 방법은 각 의 중복도가 인 중복집합을 선택하는 방법과 일대일 대응한다. 개의 항의 곱이 인 경우는 중복도의 합이

인 경우이다. 즉, 크기 의 중복집합에 대응한다. 따라서 결국 의 계수는 이다.

 참고 문헌 


 외부 링크 



 같이 보기 
 순열
 뤼카의 정리

분류:조합론