무언가를 세는 문제에서 광범위하게 나타나는 숫자가 있습니다. 카탈란 넘버Catalan number라고 불리는 이 숫자들은 다음과 같은 수열, 즉 시퀀스sequence입니다.

1, 1, 2, 5, 14, 42, 132, 429, 1430, \dots

이 숫자들이 무엇이 특별할까요?

바이너리 트리binary tree의 개수를 세다보면 카탈란 넘버를 마주치게 됩니다. 노드가 하나인 바이너리 트리는 한 가지, 두 개는 두 가지, 세 개는 다섯 가지가 있습니다.

Five kinds of binary trees with three nodes — 그림 1. 세 노드를 가진 트리들. 총 다섯 가지가 존재합니다.

나아가서 노드가 네 개라면 열 네 가지, 다섯 개라면 마흔 두 가지가 있습니다. 여기서 카탈란 넘버가 나타납니다.

카탈란 넘버 $C_n$ 는 다음과 같은 점화식recurrence relation으로 정의할 수 있습니다.

\begin{align*} C_n &= \sum_{k=0}^{n-1} C_k C_{n-1-k} \quad (C_0 = 0) \\ &= C_0 C_{n-1} + C_1 C_{n-2} + C_2 C_{n-3} + \cdots + C_{n-1} C_0 \end{align*}

즉 노드가 $n$ 개인 바이너리 트리는 $C_n$ 개가 됩니다. 그리고 점화식을 얻었으므로, 간단한 코드를 통해 그 개수를 계산할 수 있습니다.

왜 바이너리 트리의 개수가 이런 식을 가질까요? 이는 문제를 더 작은 문제의 답을 통해 푸는 패턴과 관련이 있습니다. 이는 $C_n$ 을 구하기 위해 $C_0$ 을 비롯한 이전의 카탈란 넘버를 이용하는 부분에서 볼 수 있습니다.

그러면 바이너리 트리에서 카탈란 넘버가 등장하는 이유를 알아보겠습니다.

일일이 세는 대신 패턴을 세기

노드가 네 개일 땐 바이너리 트리가 14개 임을 앞서 언급했는데요. 어떻게 구할 수 있을까요?

카탈란 넘버는 대략 $4^n$ 을 따라 가파르게 커지기 때문에, 노드가 조금만 많아져도 일일이 세기가 금방 어려워집니다.

하지만 이미 풀었던 문제의 답으로 해결할 수 있는데요. 왼쪽 서브트리subtree를 주목해보세요. 여기에 오는 노드 개수를 기준으로 케이스를 나눠봅시다.

Four cases of binary tress with four nodes — 그림 2. 노드가 네 개일 때의 패턴. 왼쪽 서브 트리에 몇 개의 노드가 있는 지에 따라 나눕니다.

노드가 $n$ 개일 때 트리의 개수를 $C_n$ 이라고 해봅시다. 첫 번째 경우, 왼쪽에 $C_0$ 가지, 오른쪽에 $C_3$ 가지가 올 수 있기 때문에, 총 $C_0 \times C_3$ 가지의 트리를 만들 수 있습니다.

이런 식으로 두 번째 경우는 $C_1 \times C_2$ 가지가 됩니다. 나머지도 마찬가지이고, 대칭적으로 구할 수 있습니다. 결국 네 개의 노드로 만들 수 있는 트리의 개수 $C_4$ 는 다음과 같이 계산할 수 있게 됩니다.

C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 14

이는 노드가 $n$ 개인 경우로 쉽게 일반화할 수 있습니다.

C_n = C_0 C_{n-1} + C_1 C_{n-2} + C_2 C_{n-3} + \cdots + C_{n-1} C_0

이 결과는 앞서 소개했던 카탈란 넘버의 점화식이 됩니다.

악수 문제에서 찾아내는 똑같은 패턴

바이너리 트리의 개수를 세기위해 사용했던 방법이 고스란히 반복되는 다른 문제에서도 카탈란 넘버가 나타납니다. 아래 악수 문제가 그런 예시인데요.

여기 여덟 명의 사람이 둥근 테이블에 있다고 해봅시다. 그리고 각자 악수를 하려고 합니다. 하지만 팔이 교차되는 일은 없기를 바라고 있습니다. 그러면 이렇게 악수를 하는 방법은 몇 가지일까요?

Successful and failed case of handshaking — 그림 3. 악수 문제. 왼쪽은 올바른 경우입니다. 하지만 오른쪽처럼 4번과 6번이 악수하면, 5번과 7번이 악수할 때 팔이 교차됩니다. 이런 경우는 답에서 제외됩니다.

여기서도 더 작은 문제의 답을 이용해 풀 수 있는데요. 이번에는 1번 사람이 누구와 악수하는지 기준으로 케이스를 나눠봅시다.

Handshaking diagram — 그림 4. 악수의 네 가지 패턴. 1번 사람이 누구와 악수를 하는 지에 따라 나눕니다. 3번 사람과 악수한다면, 2번 사람은 악수할 사람이 없게 됩니다. 이런 이유로 홀수 번의 사람과 악수하는 경우는 제외합니다.

그러면 악수한 팔이 사람들을 두 그룹으로 나누는데요. 따라서 악수하는 방법의 수는 각 그룹에서 악수하는 방법의 수를 곱한 것이 됩니다.

$n$ 명이 악수하는 방법의 수를 $H_n$ 이라고 해봅시다. 그러면 문제의 답 $H_8$ 은 이렇게 됩니다.

H_8 = H_0 H_6 + H_2 H_4 + H_4 H_2 + H_6 H_0

여기서 $C_n = H_{2n}$ 으로 정의해봅시다.

C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0

따라서 이 문제의 답은 또 카탈란 넘버가 됩니다.

카탈란 넘버 계산 프로그램

점화식을 구했으니, 실제로 카탈란 넘버를 계산할 수 있습니다. 파이썬Python으로 구현하면 다음과 같습니다.

def catalan(n)
  if n == 0:
    return 1

  ans = 0
  for k in range(n):
    ans += catalan_bf(k) * catalan_bf(n-1-k)
  return ans

시간 복잡도가 $O(3^n)$ 인 점은 언급만 하고, 증명은 직접 해보는 문제로 남기겠습니다.

그런데 위 코드는 똑같은 카탈란 넘버를 자꾸 계산하는데요. 다이나믹 프로그래밍dynamic programming으로 중복 계산을 피할 수 있습니다.

def catalan(n)
    dp = [0] * (n+1)
    dp[0] = 1

    for m in range(1, n+1):
        for k in range(m):
            dp[m] += dp[k] * dp[m-1-k]

    return dp[n]

이렇게 시간 복잡도를 $O(n^2)$ 으로 줄일 수 있습니다.

위 코드는 지스트Gist에서 볼 수 있습니다.

마치며

여기까지 바이너리 트리를 세는 문제에서 카탈란 넘버가 나타나는 이유를 알아보았습니다. 그리고 바이너리 트리 뿐만 아니라 악수 문제에서도 카탈란 넘버를 이끌어냈습니다. 이렇게 유도한 카탈란 넘버의 점화식을 이용해, 실제로 계산하는 프로그램도 간단히 만들 수 있었습니다.

더 많은 문제들

카탈란 넘버는 언뜻 보기에 관련이 없어보이는 다른 문제에서도 나타나는데요. 다각형을 삼각형으로 쪼개는 방법, 괄호를 짝을 맞춰 나열하는 방법, 두 후보가 있을 때 추월 없이 개표가 동점으로 끝나는 경우의 수 같은 것들이 있습니다. 즉 이런 문제들은 본질적으로 같은 문제입니다.

그 중에 딕 패스Dyck path 문제를 주목해볼만 한데요. 다른 문제들을 딕 패스 문제로 바꿔침으로써 답을 쉽게 얻을 수 있습니다. 이것은 다음에 기회가 될 때 살펴보겠습니다.

다른 점화식

카탈란 넘버를 구하는 프로그램이 더 나은 시간 복잡도 $O(n)$ 을 갖도록 개선할 수 있습니다. 사실 카탈란 넘버는 $C_n = \frac{4n-2}{n+1} C_{n-1}$ 라는 점화식도 가지는데요. 이를 이용해 $n$ 번의 계산으로 카탈란 넘버를 구할 수 있기 때문입니다.

왜 이런 점화식이 나타나는지는 다음에 기회가 된다면 살펴보겠습니다. 카탈란 넘버의 클로즈드 폼closed-form 공식 $C_n = \frac{1}{n+1} {2n \choose n}$ 도 함께요.

레퍼런스

Catalan Numbers (Richard Stanley, 2015)