괄호를 짝 맞추는 방법의 수와, 다각형을 대각선으로 삼각형들로 나누는 방법의 수는 언뜻 아무 관계도 없어 보여요. 그런데 놀랍게도 둘 다 정확히 같은 수열(1, 1, 2, 5, 14, 42...)이 돼요. 이 신기한 수를 카탈랑 수라고 해요.
카탈랑 수는 Cn = (2n)! / ((n+1)! × n!) 이라는 공식으로 구해요. n=0부터 1, 1, 2, 5, 14, 42, 132...로 이어져요. 아래에서 n을 바꿔가며 값을 확인하고, 왜 괄호 짝 맞추기와 다각형 삼각분할이 똑같은 개수가 되는지 직접 나열해서 확인해봐요.
n을 골라서 카탈랑 수를 계산하는 과정을 직접 확인해보세요.
여는 괄호와 닫는 괄호를 n쌍씩 써서, 짝이 정확히 맞는(어느 지점에서도 닫는 괄호가 여는 괄호보다 많아지지 않는) 모든 배열을 나열해봐요.
(n+2)각형을 대각선으로 나눠서 전부 삼각형이 되게 하는 방법이 몇 가지인지, 하나씩 넘겨보며 확인해보세요.
노드가 n개인 이진트리(각 노드가 왼쪽·오른쪽 자식을 최대 하나씩 가지는 나무 구조)의 서로 다른 모양의 개수도 정확히 카탈랑 수 Cn이에요. 괄호 하나를 노드 하나로, 괄호가 감싸는 구조를 트리의 가지로 바꿔서 생각하면, 사실 세 문제(괄호·다각형·이진트리)가 전부 같은 구조를 다른 옷을 입혀서 보고 있는 것이라는 게 밝혀져요.
이렇게 겉모습은 완전히 다른데 개수가 똑같은 문제들을 수학자들은 "전단사(bijection)가 있다"고 표현해요. 카탈랑 수는 지금까지 알려진 것만 200가지가 넘는 서로 다른 조합론 문제에서 등장해요.