조합론

**조합론**(組合論, ) 또는 **조합수학**(組合數學)은 유한하거나 가산적인 구조들에 대하여, 어떤 주어진 성질을 만족시키는 것들의 가짓수나 어떤 주어진 성질을 극대화하는 것을 연구하는 수학 분야이다.

## 분류
조합론에서는 다양한 종류의 조합론적 구조들을 다루며, 이들은 다음을 들 수 있다.
* **[[순열]]**과 **[[조합]]**. 이들을 세는 문제는 12정도라는 이름으로 체계화되어 있다.
* **[[집합의 분할]]**, 특히 자연수의 분할
* **문자열**()
* **[[부분 순서 집합]]**은 순서로 생각할 수 있는 관계를 부여한 집합이며, 특수한 경우로 전순서 집합이나 격자 등이 있다. 이들을 연구하는 분야를 순서론이라고 한다.
* **[[그래프]]**는 일련의 꼭짓점들과 이들 사이를 잇는 변들로 구성된 조합론적 구조이다. 이들을 다루는 분야를 그래프 이론이라고 한다.
* **[[매트로이드]]**는 그래프를 일반화한 개념이다.
* **유한 기하**()는 유한한 수의 점과 선 등으로 구성된 기하학적 공간이다. 이에 대하여 다양한 열거 문제를 고려할 수 있다.
* **계획**()은 원래 통계학의 실험계획법에서 유래한 개념이다. 라틴 방진이 이의 특수한 경우이다. 계획 이론은 유한 기하학과 코드 이론()과 밀접하게 연관되어 있다.

조합론은 다루는 대상 대신 사용하는 기법 또는 목표로서 분류할 수도 있다.
* **계수적 조합론**()은 주어진 조건을 만족하는 대상의 수를 세는 것을 목표로 한다.
* **해석적 조합론**()은 해석학적 기법을 조합론에 응용하며, 보통 주어진 대상의 정확한 수보다는 이들의 수의 점근적 공식()을 목표로 한다. 계승의 스털링 공식이 대표적인 예이다.
* **극대 조합론**()은 주어진 조건을 만족시키는 대상 가운데 "가장 큰" 또는 "가장 작은" 것 따위의 문제를 다룬다. 극대 그래프 이론은 그래프 이론에서 중요한 연구 분야의 하나이다. 다른 방향으로, 램지 이론도 이에 속한다.
* **위상수학적 조합론**()은 그래프 따위의 조합론적 구조에 위상을 주어, 보르수크-울람 정리나 호몰로지 대수학을 조합론적 문제에 응용한다. 로바스 라슬로는 보르수크-울람 정리를 사용하여 크네저 그래프()에 대한 크네저 추측을 증명하였다.

### 관련 분야
조합론은 대수학, 확률론, 에르고딕 이론, 기하학 등 수학의 여러 분야와 관련되어 있다. 또한, 전산학, 통계 물리학 같은 분야와도 관계가 있다.

## 역사
### 고대
[섬네일|right|《[역경》에 등장하는 64괘]]
조합론의 기초 개념은 고대 수학에서부터 시작하였다. 기원전 10세기~기원전 4세기 주나라에서 집필된 《역경》은 양(⚊) 또는 음(⚋)의 값을 가질 수 있는 6개의 효(爻)로부터 64 = 26개의 괘(卦)를 구성하였다. 기원전 6세기에 인도의 외과의사 수슈루타()는 의학서 《수슈루타상히타》()에서, 6개의 기본 맛(단맛, 신맛, 짠맛, 쓴맛, 매운 맛, 떫은 맛)을 63 = 26 &minus; 1가지로 조합할 수 있다고 서술하였다. 이는 6개의 원소로 만들 수 있는 집합 가운데 공집합을 제외한 것들의 가짓수이다.

기원후 1세기 고대 그리스에서, 플루타르코스(46~120)는 에세이집 《윤리학》()의 49번째 에세이 〈잡담〉() 8권에서 다음과 같이 적었다.

여기서 "긍정적 합성 명제"의 수
:103\,049=s_{10}
는 10번째 슈뢰더 수() s_{10}이며, 10개의 글자로 구성된 문자열에 괄호를 삽입할 수 있는 가짓수이다. "부정적 합성 명제"의 수
:310\,952=(s_{10}+s_{11})/2
는 10번째와 11번째 슈뢰더 수의 평균이다.

### 중세
[섬네일|right|양휘가 지은 《상해구장산법》(詳解九章算法)에 수록된 [파스칼 삼각형]]
850년 경에 인도의 수학자 마하비라()는 《산법 요론(要論)》()에서 순열과 조합의 수에 대한 공식을 제시하였다.

아랍 세계에서는 중세 스페인의 랍비 아브라함 이븐 에즈라(, , 1089~1167)는 이항 계수의 대칭성
:\binom{n+k}n=\binom{n+k}k
을 증명하였다. 1321년에 랍비 레비 벤 게르숀(, , 1288~1344)은 순열과 조합의 수에 대한 공식을 제시하였다.

송나라의 양휘는 《구장산술》에 대한 주석인 《상해구장산법》(詳解九章算法)에서 파스칼 삼각형을 제시하였다. 이는 전대의 수학자인 가헌의 업적을 바탕으로 한 것으로 보이나, 가헌의 저서들은 현존하지 않는다.

인도와 아랍 수학은 13세기에 유럽에 소개되었다. 이탈리아의 수학자 요르다누스 데 네모레(, , 13세기 경)는 《산술》() 명제 70번에서 이항 계수를 삼각형으로 배열하였는데, 이는 훗날 파스칼 삼각형으로 불리게 되었다.

중세 일본에는 벨 수가 최초로 등장하였다. 《겐지모노가타리》에서의 한 일화로부터 겐지코()라는 놀이가 등장했는데, 이 놀이에서는 5개의 향 가운데 어떤 것들이 같은 냄새의 향인지 구별하는 것이 목표이다. 가능한 해의 수는 5차 벨 수 B_5=52가지다. 이 52가지의 집합의 분할은 겐지몬()이라는 문양으로 나타내어져, 겐지모노가타리의 54개의 장의 각 표지에 표시되었다. (이 가운데 2개의 겐지몬은 벨 수와 관계없다.)

### 근세
블레즈 파스칼(1623~1662)과 아이작 뉴턴(1643~1727), 야코프 베르누이(1655~1705) 등은 조합론을 포함한 수학에 다방면으로 기여하였다. 파스칼은 1665년 사후에 출판된 저서 《산술 삼각형에 대하여》()에서 (이미 중세부터 알려져 있던) 파스칼 삼각형을 연구하였다. 1666년에 고트프리트 라이프니츠는 박사 학위 논문 《조합술에 대하여》()를 출판하였다.  이 책에서 라이프니츠는 "조합술"()이라는 용어를 최초로 사용하였다. 라이프니츠는 이 책에서 다음과 같은 용어를 사용하였다.
:순열:  ("순서의 차이·변화")
:두 개의 원소로 구성된 조합:  (이음)
:세 개의 원소로 구성된 조합:  (세 개로 구성된 것,  +  + )
:(일반적인) 조합:  (연결·연합·복합)

레온하르트 오일러(1707~1783)는 오일러 수를 연구하였고, 쾨니히스베르크의 다리 문제를 풀어 그래프 이론을 창시하였다.

19세기 말~20세기 초에 제임스 조지프 실베스터와 퍼시 알렉산더 맥메이헌은 대수적 조합론을 창시하였고, 이 시기에 그래프 이론 역시 급속히 발달하였다. 20세기 후반에 기하학적·위상수학적 기법들이 조합론에 사용되기 시작하였다.

## 같이 보기
* 조합론적 게임 이론
* 이산수학
* 계통학

## 각주

* 
* 
* 
* 
* 

## 외부 링크

* 
* 
* 
* 
* 

분류:이산수학