카탈랑 수(Catalan number)

괄호 n쌍을 짝이 맞게 늘어놓는 방법은 몇 가지일까요? n = 3이면 ((())), (()()), (())(), ()(()), ()()()의 다섯 가지입니다. 이렇게 n = 0, 1, 2, …에 대해 1, 1, 2, 5, 14, 42, 132, …로 이어지는 수가 카탈랑 수 $C_n$입니다. 1838년 괄호 치는 방법을 세며 이 수를 다룬 벨기에 브뤼헤 태생의 수학자 외젠 카탈랑의 이름을 땄습니다. 다각형을 삼각형으로 나누는 방법으로는 오일러가 1751년에 이미 이 수를 셌습니다. 이 수가 유명한 까닭은 전혀 달라 보이는 세기 문제 수백 가지의 답이 모두 이 수이기 때문입니다.

괄호 쌍: () 이전 다음 무작위

왼쪽은 여는 괄호를 한 칸 오르기, 닫는 괄호를 한 칸 내리기로 바꾼 산 모양 길입니다. 짝이 맞는다는 것은 길이 바닥 아래로 내려가지 않고 바닥에서 끝난다는 뜻입니다. 이런 길을 독일의 수학자 발터 폰 디크의 이름을 따 디크 경로⁠(Dyck path)⁠라고 합니다. 오른쪽은 (n+2)각형을 서로 엇갈리지 않는 대각선으로 잘라 삼각형 n개로 나눈 그림입니다. 괄호 한 쌍이 삼각형 하나에 대응하고, 같은 색끼리 짝입니다. 맨 앞 괄호 쌍이 아래 밑변 위의 삼각형이 되고, 그 괄호의 안쪽과 뒤쪽이 각각 삼각형 왼쪽과 오른쪽의 작은 다각형이 됩니다. 이런 일대일대응이 있으니 두 세기의 답이 같습니다.

점화식⁠(recurrence relation)⁠. 비어 있지 않은 짝 맞는 괄호열은 모두 $(A)B$ 꼴로 단 한 가지 방법으로 쪼개집니다. 맨 앞 여는 괄호와 그 짝인 닫는 괄호가 A를 감싸고, 그 뒤에 남은 것이 B이기 때문입니다. A와 B도 짝이 맞는 괄호열(빈 것도 됩니다)이고, A가 i쌍이면 B는 $n-1-i$쌍입니다. 그래서 위의 점화식 $C_n = \sum_i C_i\,C_{n-1-i}$가 나옵니다. 꼭짓점⁠(vertex)⁠이 n개인 이진 트리의 모양도 같은 이유로 $C_n$가지입니다. 뿌리의 왼쪽 가지와 오른쪽 가지가 A와 B입니다(트리⁠(tree)⁠, 재귀⁠(recursion)⁠). 행렬⁠(matrix)⁠ n+1개를 곱하는 순서(괄호 치는 방법)도 $C_n$가지입니다. 이 수는 금세 너무 커지므로, 모두 따지지 않고 가장 싼 곱셈 순서를 찾는 문제는 동적 계획법⁠(dynamic programming)⁠의 교과서 예제입니다.

닫힌 식. 오르기 n번, 내리기 n번인 길은 모두 $\binom{2n}{n}$개입니다(이항계수⁠, binomial coefficient⁠). 그중 바닥 아래로 내려가는 '나쁜' 길은, 처음으로 높이 −1에 닿은 뒤의 부분을 위아래로 뒤집으면 오르기 n−1번, 내리기 n+1번인 길과 일대일로 대응하므로 $\binom{2n}{n+1}$개입니다(반사 원리⁠, reflection principle⁠). 빼면 $C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}$입니다. 지금 $C_n$ = . 스털링 공식⁠(Stirling's formula)⁠을 쓰면 $C_n \sim \frac{4^n}{n^{3/2}\sqrt\pi}$입니다. 여기서 ∼는 n이 커질수록 두 변의 비가 1로 다가간다는 뜻이고, 작은 n에서는 차이가 꽤 큽니다(n = 7이면 오른쪽이 약 499로, 실제 값 429보다 16%쯤 큽니다).

이어지는 곳. 오르내리는 길은 동전 던지기로 움직이는 무작위 행보⁠(random walk)⁠입니다. 그런 길이 바닥과 꼭대기 가운데 어디에 먼저 닿는지를 묻는 것이 도박꾼의 파산⁠(gambler's ruin)⁠이고, 바닥에 닿지 않는 길을 세는 반사 원리는 개표 문제⁠(ballot problem)⁠에서도 씁니다. 개표 문제는 후보 A가 a표, B가 b표(a > b)를 얻었을 때 표를 무작위 순서로 하나씩 열면 A가 처음부터 끝까지 줄곧 앞설 확률⁠(probability)⁠을 묻는 문제로, 답은 $(a-b)/(a+b)$입니다. 짝이 맞는 괄호열 전체는 문맥 자유 문법⁠(context-free grammar)⁠ $S \to (S)S \mid \varepsilon$가 만드는 언어입니다. 이 규칙은 '짝 맞는 괄호열(S)은 괄호 한 쌍 안에 짝 맞는 괄호열을 넣고 뒤에 또 하나를 붙인 것이거나, 빈 문자열(ε)이다'라고 읽습니다. 이 언어는 기억이 유한한 유한 오토마톤⁠(finite automaton)⁠으로는 알아볼 수 없는 언어의 대표적인 예입니다. 열린 괄호가 몇 개 쌓였는지를 얼마든지 큰 수까지 세어 두어야 하는데, 유한한 기억으로는 어느 수 이상을 구별할 수 없기 때문입니다.

생성함수⁠(generating function)⁠ $C(x) = 1 + xC(x)^2$을 풀면 $C(x) = \frac{1-\sqrt{1-4x}}{2x}$입니다. 같은 식을 '이진 나무는 빈 나무이거나, 마디 하나에 나무 두 개를 단 것'이라는 타입⁠(type)⁠의 정의로 읽을 수 있는데, 이렇게 타입을 합과 곱으로 짓고 값을 세는 것이 대수적 자료형⁠(algebraic data type)⁠입니다. 이 타입은 방정식 $T\cong 1 + T\times T$의 가장 작은 해, 곧 시작 대수이고, 나무 위의 구조적 재귀는 그 대수에서 다른 대수로 가는 하나뿐인 준동형(fold)입니다.