조합론(組合論, Combinatorics)이란, 수학의 한 갈래로서 유한하거나 가산적인[1] 이산구조에 대해 연구하는 분야...이지만 사실 하나로 딱잘라 정의하기는 어려울 정도로 다양한 주제를 포함하고 있다. 그 많은 주제 중에서 공통적인 것을 뽑아보자면 최적화, 극대화, 극소화가 있으며, 이 셋은 실생활과 크게 연결되어 있기 때문에 수학을 싫어하는 학생들도 이 분야만큼은 쓸모있다고 생각하는 경우가 많다. 당장 한국 스포츠 해설위원들이 줄기차게 찾는 경우의 수도 조합론의 대표적인 분야이다(...). 물론 실생활이 아닌 학문적인 측면에서도 상당히 쓸모가 많은 학문인데, 그래프 이론은 컴퓨터 과학, 기하학, 위상수학에서, 순열, 조합과 같은 수를 세는 기법은 통계학과 확률론과 수학의 정석에서, 생성함수나 점화식 같은 것들은 대수학에서 쓰이는 등, 여러 학문 분야에서 심심하면 튀어나온다. 심지어는 연구 분야로써는 정 반대에 해당되는 해석학에서도[2]집합 파트나 함수의 개수등 감초처럼 쓰인다.
역사[편집 | 원본 편집]
조합론은 다른 수학 분야에 비하면 역사가 조금 짧다는 인식이 있는데, 반은 맞고 반은 틀린 소리이다. 조합론을 배우면 보통 가장 먼저 배우는 것이 수를 세는 기법인데, 상식적으로 생각해서 수를 세는 기법의 역사가 짧겠는가? 하지만 그래프 이론이나 알고리즘 같은 것들은 수천년의 역사를 자랑하는 기하학이나 대수학에 비하면 확실히 초라할 정도로 역사가 짧다.
조합론의 기초에 해당하는 수를 세는 기법에 대한 역사는 기원전에서부터 시작한다. 기원전 6세기의 인도나 고대 그리스 시절의 여러 수학자로부터 수를 세는 기법에 대한 연구가 이루어졌다는 내용이 남아있다. 수를 세는 기법에 대한 연구는 중세 시대에도 이어졌으며, 인도에서는 순열과 조합에 관한 공식이, 일본에서는 벨 수에 관한 내용이, 영국에서는 해밀턴 경로에 관한 내용이 발견된다.
근세에는 파스칼의 삼각형과 같은 수를 세는 기법뿐만 아니라 본격적인 그래프 이론에 관한 연구가 시작되었다. 그래프 이론의 시작은 쾨니히스베르크 다리 건너기 문제를 처음 해결한 레온하르트 오일러라는 것이 일반적인 의견. 19세기 말에는 대수적 조합론의 창시로 조합론이 한층 더 발전하였으며, 20세기에는 컴퓨터의 등장으로 더더욱 빠른 속도로 발전하고 있다.
주요 분야[편집 | 원본 편집]
- 수를 세는 기법 (Counting Problem)
- 순열
- 조합
- 구성 (Composition, 한국에서는 중복조합)
- 분할 (Partition)
- 포함과 배제의 원리
- 카탈란 수
- 생성함수 (Generating Function)
- 그래프 이론 (Graph Theory)