개념
1, 2, 5, 14, 42, 132, 429, ... 수많은 조합 문제의 답이 같은 이 수열. 괄호 짝짓기·이진트리·도시 격자 경로 — 전혀 달라 보이는 문제들이 같은 수열을 낳는 신비.
한 호흡으로 이해하기
서로 달라 보이는 여러 세기 문제에서 같은 수열이 나타난다. n쌍의 균형 잡힌 괄호 문자열, n개의 내부 노드를 가진 완전 이진트리, (n+2)각형의 삼각분할 가짓수는 모두 Cₙ이다. 대상 사이에 전단사가 있다는 사실이 조합론의 재미를 보여 준다.
한눈에 보기
n | Cₙ | 의미 (예시) |
|---|---|---|
| 0 | 1 | 빈 식 |
| 1 | 1 | () |
| 2 | 2 | ()(), (()) |
| 3 | 5 | 균형 괄호 5가지 |
| 4 | 14 | 이진트리 14모양 |
| 5 | 42 | 7각형 삼각분할 42 |
| 6 | 132 | |
| 7 | 429 | |
| 8 | 1430 |
한 수열이 수십 가지 다른 문제의 답.
핵심 식
Cₙ = 1, 1, 2, 5, 14, 42, 132, ...
핵심 순간
AD 1751
오일러 — 다각형 분할
오일러가 n각형을 삼각형으로 분할하는 방법의 수를 셈. 1, 2, 5, 14, 42... 등장.
AD 1838
카탈란 — 괄호 문제
벨기에 수학자 카탈란이 (())()같은 균형 잡힌 괄호의 개수가 같음을 발견. 그의 이름이 붙음.
AD 2015
214가지 다른 정의
리처드 스탠리가 카탈란 수의 214가지 서로 다른 조합적 정의를 정리. 모두 같은 수열.
오늘날의 응용
컴파일러의 구문 분석 트리, 이진 검색 트리 카운팅, 알고리즘 분석, RNA 2차 구조 예측, 게임 트리.
MathVoyage 너머로
불러오는 중…