다음 두 문제를 생각해보세요. 첫째, 여는 괄호 "("와 닫는 괄호 ")"를 각각 n개씩 써서, 어느 지점에서도 닫는 괄호가 여는 괄호보다 많아지지 않도록 짝을 맞추는 방법은 몇 가지일까요? 둘째, 볼록한 (n+2)각형을 대각선으로 나눠서 조각이 전부 삼각형이 되게 하는 방법은 몇 가지일까요? 겉으로는 완전히 다른 문제인데, 놀랍게도 두 문제의 답은 정확히 똑같은 수열이에요: 1, 1, 2, 5, 14, 42, 132... 이 수를 카탈랑 수라고 불러요.
카탈랑 수는 Cn = (2n)! / ((n+1)! × n!) 이라는 공식으로 계산해요. n=0부터 대입하면 C0=1, C1=1, C2=2, C3=5, C4=14, C5=42로 이어져요. 예를 들어 괄호 3쌍으로 만들 수 있는 올바른 배열은 ((())), (()()), (())(), ()(()), ()()() 이렇게 정확히 5가지예요.
그런데 오각형(5각형)을 대각선으로 나눠서 전부 삼각형이 되게 하는 방법도 세어보면 똑같이 5가지가 나와요. 우연이 아니에요. 오각형은 대각선 2개를 그으면 삼각형 3개로 나뉘는데, 이때 (n+2)각형에서 n=3이라 C3=5와 정확히 일치해요. 괄호 문제도, 다각형 문제도 사실은 "재귀적으로 두 조각으로 나누는 방법의 수"라는 같은 구조를 갖고 있기 때문이에요.
이 우연 같은 일치를 수학자들은 "전단사(bijection)가 있다"고 표현해요. 두 문제의 답을 하나하나 일대일로 짝지을 수 있다는 뜻이에요. 실제로 괄호 하나를 다각형의 대각선 하나로, 괄호가 감싸는 구조를 삼각형이 붙는 순서로 바꿔서 생각하면 두 문제가 정확히 같은 방식으로 대응돼요. 심지어 노드가 n개인 이진트리(각 노드가 왼쪽·오른쪽 자식을 최대 하나씩 갖는 나무 구조)의 서로 다른 모양의 개수도 똑같이 Cn이에요.
카탈랑 수는 벨기에 수학자 외젠 카탈랑의 이름을 땄지만, 사실 그보다 앞서 스위스의 레온하르트 오일러와 몽골의 밍안투가 각자 독립적으로 이 수를 연구했어요. 지금까지 알려진 것만 200가지가 넘는 서로 다른 조합론 문제에서 카탈랑 수가 등장할 만큼, 수학 곳곳에 숨어있는 수예요.
저희 체험 페이지에서는 n을 바꿔가며 카탈랑 수가 어떻게 계산되는지 직접 확인할 수 있고, 괄호 배열을 전부 나열해서 눈으로 세어볼 수 있어요. 또 다각형의 삼각분할 방법을 하나씩 넘겨보면서, 두 문제의 답이 정말로 똑같이 늘어나는지 직접 확인할 수 있어요.