조합론

조합론에서는 다양한 종류의 조합론적 구조들을 다루며, 이들은 다음을 들 수 있다.

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

조합론은 다루는 대상 대신 사용하는 기법 또는 목표로서 분류할 수도 있다.

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

관련 분야

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

고대

 

조합론의 기초 개념은 고대 수학에서부터 시작하였다. 기원전 10세기~기원전 4세기 주나라에서 집필된 《역경》은 양(⚊) 또는 음(⚋)의 값을 가질 수 있는 6개의 효(爻)로부터 64 = 2⁶개의 괘(卦)를 구성하였다. 기원전 6세기에 인도의 외과의사 수슈루타(산스크리트어: सुश्रुत)는 의학서 《수슈루타상히타》(산스크리트어: सुश्रुतसंहिता)에서, 6개의 기본 맛(단맛, 신맛, 짠맛, 쓴맛, 매운 맛, 떫은 맛)을 63 = 2⁶ − 1가지로 조합할 수 있다고 서술하였다. 이는 6개의 원소로 만들 수 있는 집합 가운데 공집합을 제외한 것들의 가짓수이다.

기원후 1세기 고대 그리스에서, 플루타르코스(46~120)는 에세이집 《윤리학》(고대 그리스어: Ἠθικά 에티카^[*])의 49번째 에세이 〈잡담〉(고대 그리스어: Συμποσιακά 심포시아카^[*]) 8권에서 다음과 같이 적었다.

여기서 "긍정적 합성 명제"의 수

${\displaystyle 103\,049=s_{10}}$ 

는 10번째 슈뢰더 수(영어: Schröder number) ${\displaystyle s_{10}}$ 이며, 10개의 글자로 구성된 문자열에 괄호를 삽입할 수 있는 가짓수이다. "부정적 합성 명제"의 수

${\displaystyle 310\,952=(s_{10}+s_{11})/2}$ 

는 10번째와 11번째 슈뢰더 수의 평균이다.

중세

 

850년 경에 인도의 수학자 마하비라(산스크리트어: महावीर)는 《산법 요론(要論)》(산스크리트어: गणितसारसंग्रह 가니타사라상그라하)에서 순열과 조합의 수에 대한 공식을 제시하였다.

아랍 세계에서는 중세 스페인의 랍비 아브라함 이븐 에즈라(히브리어: אברהם אבן עזרא, 라틴어: Abenezra 아베네즈라^[*], 1089~1167)는 이항 계수의 대칭성

${\displaystyle {\binom {n+k}{n}}={\binom {n+k}{k}}}$ 

을 증명하였다. 1321년에 랍비 레비 벤 게르숀(히브리어: לוי בן גרשום‏, 라틴어: Gersonides 게르소니데스^[*], 1288~1344)은 순열과 조합의 수에 대한 공식을 제시하였다.

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

인도와 아랍 수학은 13세기에 유럽에 소개되었다. 이탈리아의 수학자 요르다누스 데 네모레(라틴어: Jordanus de Nemore, 이탈리아어: Giordano di Nemi 조르다노 디 네미^[*], 13세기 경)는 《산술》(라틴어: De elementis arithmetice artis 데 엘레멘티스 아리트메티케 아르티스^[*]) 명제 70번에서 이항 계수를 삼각형으로 배열하였는데, 이는 훗날 파스칼 삼각형으로 불리게 되었다.

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

근세

블레즈 파스칼(1623~1662)과 아이작 뉴턴(1643~1727), 야코프 베르누이(1655~1705) 등은 조합론을 포함한 수학에 다방면으로 기여하였다. 파스칼은 1665년 사후에 출판된 저서 《산술 삼각형에 대하여》(프랑스어: Traité du triangle arithmétique)에서 (이미 중세부터 알려져 있던) 파스칼 삼각형을 연구하였다. 1666년에 고트프리트 라이프니츠는 박사 학위 논문 《조합술에 대하여》(라틴어: Dissertatio de arte combinatoria)를 출판하였다. 이 책에서 라이프니츠는 "조합술"(라틴어: ars combinatoria)이라는 용어를 최초로 사용하였다. 라이프니츠는 이 책에서 다음과 같은 용어를 사용하였다.

순열: 라틴어: variātiō ōrdinis 바리아티오 오르디니스^[*] ("순서의 차이·변화")
두 개의 원소로 구성된 조합: 라틴어: combīnātiō 콤비나티오^[*] (이음)
세 개의 원소로 구성된 조합: 라틴어: conternātiō 콘테르나티오^[*] (세 개로 구성된 것, 라틴어: con- + 라틴어: ternī + 라틴어: -ātiō)
(일반적인) 조합: 라틴어: complexiō 콤플렉시오^[*] (연결·연합·복합)

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

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