카탈란 수
괄호 열고 닫는 짝을 맞춰 보세요
여는 괄호 '(' 3개와 닫는 괄호 ')' 3개로 올바르게 짝이 맞는 괄호 식을 만들어 보세요. ((())), ()(()), ()()(), (())()처럼 직접 적어보면 딱 5가지가 나옵니다.
괄호가 4쌍이면 14가지, 5쌍이면 42가지가 됩니다. 다각형을 삼각형으로 자르기, 대각선을 넘지 않는 최단 경로가 왜 모조리 이 마법의 수열 1, 2, 5, 14, 42로 똑같이 귀결될까요?
이야기
Émile Delperée
Public domain · 위키미디어 공용
1838년 파리, 벨기에 출신의 외젠 카탈란이 이 수들을 다루는 글을 냅니다. 그는 정치 때문에 여러 번 교수 자리에서 쫓겨난 사람이었습니다.
그런데 이 수를 처음 만난 사람은 그가 아닙니다. 1751년 오일러가 골드바흐에게 보낸 편지에서 이미 「다각형을 삼각형으로 자르는 방법의 수」를 묻고 답했고, 그보다 더 앞서 1730년대 중국에서 몽골 출신 수학자 밍안투가 같은 수를 계산에 쓰고 있었습니다. 이름만 카탈란에게 붙었습니다.
왜 전혀 다른 문제들의 답이 같을까요. 서로 바꿔 놓을 수 있기 때문입니다. 여는 괄호를 「오른쪽으로 한 칸」, 닫는 괄호를 「위로 한 칸」으로 읽어 보십시오. 괄호의 짝이 맞는다는 조건은 곧 길이 대각선 위로 올라가지 않는다는 조건이 됩니다.
다각형 자르기도 마찬가지입니다. 자르는 차례를 괄호로 적으면 그대로 괄호식이 됩니다. 그래서 겉모습만 다르고 속은 같은 문제인 것이고, 답이 같을 수밖에 없습니다.
컴파일러가 괄호를 검사하는 방식, 데이터베이스가 질의 순서를 고르는 방식이 이 수와 닿아 있습니다.
이진 트리의 모양 수, 다각형 나누기, RNA 접힘 구조가 모두 카탈란 수로 세어집니다.
계단 넷 — 같은 사실을 네 깊이로
괄호 짝을 그려 세어 본다
여는 괄호와 닫는 괄호 쌍을 맞추는 놀이입니다. 1쌍은 () 1가지, 2쌍은 ()(), (()) 2가지, 3쌍은 5가지입니다.
정오각형을 대각선으로 잘라 삼각형 3개로 쪼개는 방법도 5가지, 바둑판에서 대각선을 침범하지 않고 (3,3)까지 가는 길도 5가지입니다. 겉모습은 전혀 다른 수많은 퍼즐의 정답이 신기하게도 모두 똑같은 숫자로 수렴합니다.
괄호를 맞춰 보세요
「닫는 괄호가 여는 괄호를 앞지르면 안 된다」는 조건이 1/(n+1) 로 줄입니다.
⭐ 항이 하나 늘 때마다 거의 4 배씩 커집니다.
길 세기로 옮기기
이 수열을 카탈란 수(Catalan numbers) 이라 부릅니다. 1, 1, 2, 5, 14, 42, 132, 429... 로 이어집니다.
격자 경로에서 대각선 를 넘지 않고 에서 까지 가는 최단 경로의 수와 같습니다. 전체 경로의 수 에서 대각선을 침범하는 잘못된 경로의 수를 빼면 일반항 이 깔끔하게 유도됩니다.
다각형을 삼각형으로
괄호 문제와 같은 수가 나옵니다 — 오일러가 1751 년에 알아챘습니다.
점화식과 일반항
잘못된 경로를 대각선 에 대해 대칭 이동시키는 앙드레의 반사 원리(Reflection Principle)로 대각선 침범 경로 수가 임을 직관적으로 증명합니다.
점화식 을 만족하며, 생성함수 를 풀면 에서 라는 아름다운 대수적 해를 얻습니다.
격자 위 길
빼면 카탈란 수 — 반사 원리라 부릅니다.
생성함수·반사 원리
리처드 스탠리의 명저 『조합론(Enumerative Combinatorics)』에는 카탈란 수로 세어지는 서로 다른 조합론적 대상이 200가지 넘게 정리되어 있습니다.
이진 트리의 개수, 스택 순열의 수, 비교차 분할, 리 대수의 근계(Root system), 자유 확률론(Free Probability)의 비가환 반원 법칙(Wigner semicircle law)의 모멘트 수열로 깊게 연결됩니다.
얼마나 빨리 커지나
카탈란 수는 200 가지가 넘는 서로 다른 문제에서 똑같이 나타납니다.
풀어 보기
카탈란 수와 조합 구조. 카탈란 수는 일반항 로 주어진다.
(1) 괄호 3쌍으로 만들 수 있는 올바른 괄호 문자열의 수 을 계산하시오.
(2) 정육각형을 서로 교차하지 않는 대각선으로 잘라 4개의 삼각형으로 분할하는 방법의 수 를 구하시오.
(3) 점화식 에 를 대입하여 (1)의 결과와 일치함을 보이시오.
(1) , (2) 입니다.
답과 풀이 보기
(1) 가지입니다.
실제로 적어 보면
— 다섯 가지입니다.
(2) 가지입니다.
⭐ 볼록 각형을 삼각형으로 자르는 방법이 가지입니다. 육각형은 이므로 14 가지입니다.
(3)
(1) 의 결과와 같습니다.
⭐ 점화식의 뜻 — 괄호 문자열의 맨 앞 여는 괄호가 어디서 닫히는지로 갈라 보면, 그 안쪽과 바깥쪽이 각각 더 작은 같은 문제가 됩니다. 그래서 곱해서 더하면 됩니다.
차례로 늘어놓으면 입니다.
이 수는 200 가지가 넘는 서로 다른 문제에서 똑같이 나옵니다 — 괄호 짝 맞추기, 다각형 자르기, 이진 트리, 산 모양 그리기, 선거에서 한 후보가 한 번도 뒤지지 않는 개표 순서까지.
겉모습은 다 다른데 속에 든 뼈대가 같습니다. 수학이 하는 일이 바로 그 뼈대를 알아보는 것입니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
카탈란 수는 예상 밖의 곳에서 계속 나타납니다.
- 이진 트리 — n개 마디로 만들 수 있는 모양의 수입니다
- 산 모양 그리기 — 오르내리는 길의 수가 카탈란 수입니다
- 직접 세기 — 괄호 네 쌍으로 해 보세요. 열네 가지입니다
이어지는 장
괄호 쌍 맞추기·격자길 최단 경로·다각형 자르기 등 겉보기에 전혀 다른 문제들이 모두 같은 수열로 귀결되는 원리는, 이항계수를 피라미드처럼 쌓아 올린 파스칼 삼각형 속 대칭과 깊이 이어져 있습니다 — 제44장 에서 조합의 마르지 않는 샘을 다시 찾아보세요.
영감을 받은 곳
레온하르트 오일러가 1751년 볼록다각형의 삼각분할을 연구하며 처음 발견하고, 1838년 외젠 샤를 카탈란(Eugène Charles Catalan)이 괄호 짝짓기 문제로 일반화한 수열입니다.