카탈랑 수 (Catalan Number)
쉽게 풀면
여는 괄호 "("와 닫는 괄호 ")"를 각각 3개씩, 총 6개를 나열해서 짝이 맞는 올바른 괄호식을 만드는 방법이 몇 가지나 될지 생각해봅시다. 무작정 아무렇게나 나열하면 "())((" 처럼 중간에 짝이 깨지는 경우도 생깁니다. 이렇게 "항상 여는 괄호 수가 닫는 괄호 수보다 앞서가야 한다"는 조건을 만족하는 배열의 개수를 세면 1, 1, 2, 5, 14, 42, ... 처럼 특정한 수열이 나오는데, 이것이 바로 카탈랑 수입니다. 신기하게도 이 수열은 괄호 짝맞추기뿐 아니라 이진트리를 만드는 방법의 수, 다각형을 삼각형으로 나누는 방법의 수 등 겉보기에 전혀 달라 보이는 여러 조합론 문제에서 똑같이 등장합니다.
왜 중요한가
카탈랑 수는 이진트리, 괄호식, 다각형 분할처럼 서로 다른 문제들이 사실 동일한 조합론적 구조를 공유한다는 것을 보여주는 대표적인 사례이기 때문에 자주 다뤄집니다. 알고리즘 분야에서는 트리 형태의 자료구조나 재귀적으로 정의되는 문제의 경우의 수를 정확히 세는 근거로 쓰이며, 이는 탐색 공간의 크기를 추정하거나 알고리즘의 시간 복잡도를 분석하는 데 직접 연결됩니다. 또한 파싱, 동적 계획법, 확률론적 모델링 등 여러 하위 분야에서 반복적으로 등장하기 때문에, 카탈랑 수를 알아두면 겉보기에 무관해 보이는 문제들 사이의 구조적 유사성을 빠르게 파악할 수 있습니다.
논문에서는 이렇게 쓰입니다
이 문장은 어떤 알고리즘이 다뤄야 할 트리 구조나 괄호 구조의 경우의 수가 카탈랑 수로 정확히 계산되며, 그 값이 노드 개수가 늘어날수록 매우 빠르게 커진다는 점을 지적한 것입니다. 알고리즘의 계산 복잡도나 탐색 공간의 크기를 분석할 때 조합론적 근거로 자주 인용됩니다.
자연어 처리나 컴파일러 이론에서 문장 하나에 여러 해석(파스 트리)이 가능한 경우, 그 개수가 카탈랑 수 규모로 폭발적으로 늘어난다는 점을 지적하는 문장입니다. 이는 모호성이 큰 문법을 다룰 때 효율적인 파싱 전략이 필요한 이유를 뒷받침하는 근거로 쓰입니다.
여러 개의 부분 계산을 어떤 순서로 결합할지에 따라 결과나 비용이 달라지는 최적화 문제(예: 행렬 곱셈 순서 결정)에서, 가능한 결합 순서의 수가 카탈랑 수로 세어진다는 점을 밝히는 문장입니다. 이런 경우 순진한 완전 탐색이 비효율적임을 보이고, 동적 계획법 같은 개선된 접근이 필요함을 정당화하는 데 활용됩니다.
조금 더 깊게 보면
카탈랑 수는 이항계수를 이용한 닫힌 형태의 공식으로 표현될 뿐 아니라, 앞선 항들의 곱을 이용한 점화식으로도 정의됩니다. 이 점화식은 "전체 구조를 왼쪽 부분과 오른쪽 부분으로 나누어 재귀적으로 센다"는 조합론적 아이디어를 그대로 반영하는데, 이 분할 방식이 동적 계획법의 부분 문제 분할 방식과 본질적으로 닮아 있어 알고리즘 설계에서 자주 응용됩니다. 또한 카탈랑 수는 이진트리, 균형 괄호식, 다각형 삼각분할, 격자 경로 등 여러 겉보기에 다른 조합론적 대상들 사이에 일대일 대응이 존재함을 보여주는 통로 역할을 하기 때문에, 논문에서 어떤 대상의 경우의 수가 카탈랑 수로 표현된다는 서술을 볼 때는 그 대상이 이런 재귀적 분할 구조를 가지고 있다는 신호로 읽으면 이해가 수월합니다.
주의할 점
카탈랑 수는 순열과 조합의 이항계수를 이용한 공식으로 표현되지만, 단순한 조합 개수가 아니라 "순서상의 균형 제약"이 걸린 특수한 경우의 수라는 점에서 다릅니다. 또한 카탈랑 수는 인접한 항들 사이의 점화식으로도 정의할 수 있어, 직접 조합 공식을 계산하기 번거로울 때는 점화식을 이용해 순차적으로 구하기도 합니다.