카탈란 넘버의 역사적 배경에 중요한 문제가 있는데요. 볼록 다각형 트라이앵귤레이션convex polygon triangulation이라고 불리는 이 문제는 다각형을 삼각형으로 나누는 방법을 세는 것입니다. 예를 들어 오각형은 다음과 같이 다섯 가지 방법이 있습니다.

Pentagon triangulation — 그림 1. 오각형 트라이앵귤레이션. 삼각형으로 나누는 방법이 다섯 가지 존재합니다.

나아가 $n$ 각형에 대해 풀면 카탈란 넘버를 발견하게 되는데요. 나중에 보겠지만 여기서 다음 카탈란 점화식을 이끌어낼 수 있습니다.

C_n = \frac{4n-2\mathstrut}{n+1} C_{n-1}

또한 클로즈드 폼closed-form을 얻을 수 있습니다.

C_n = \frac{1}{n+1} {2n \choose n}

여기서 ${2n \choose n}$ 은 이항 계수binomial coefficient입니다.

이 글에서는 트라이앵귤레이션 문제를 통해 위 관계식을 어떻게 유도해낼 수 있는지 보겠습니다. 즉 주로 수학적인 내용이 관심사가 될 것입니다. 이항 계수와 간단한 미적분을 배경 지식으로 전제하고 진행하겠습니다.

다각형을 삼각형으로 나누기

트라이앵귤레이션 문제의 답이 왜 카탈란 넘버가 되는지 보겠습니다.

간단한 예로 오각형을 나눠봅시다. 여기서 첫 번째 꼭지점과 다섯 번째 꼭지점을 잇는 모서리를 주목해봅시다. 그러면 다른 꼭지점을 골라서 삼각형을 만들 수 있는데요. 이 경우에는 세 가지 방법이 있습니다.

Three cases for a given vertex — 그림 2. 한 모서리에 대한 세 가지 케이스. 1번과 5번 꼭지점이 어디와 삼각형을 이루는 지에 따라 케이스가 나눠집니다.

이 삼각형은 양 옆에 두 다각형을 만드는데요. 따라서 삼각형으로 나누는 방법의 수는 그 두 나뉜 다각형을 삼각형으로 나누는 방법의 수를 곱한 것이 됩니다.

$n$ 각형을 삼각형으로 나눌 수 있는 방법의 개수를 $T_n$ 이라고 해봅시다. 그러면 오각형을 나누는 방법의 수 $T_5$ 는 다음과 같이 구할 수 있게 됩니다.

T_5 = T_2 T_4 + (T_3)^2 + T_4 T_2

그런데 오각형에서 멈출 필요는 없습니다. $n$ 각형으로 쉽게 일반화할 수 있는데요. 첫 번째 꼭지점과 $n$ 번째 꼭지점을 잇는 모서리를 봅시다. $k$ 번째 꼭지점과 삼각형을 만들면, 양 옆에 $k$ 각형과 $(n-k+1)$ 각형이 만들어집니다.

General cases for a given vertex — 그림 3. 오각형의 경우에서 일반적인 경우로 확장할 수 있습니다.

이제 꼭지점의 범위 $2 \le k \le (n-1)$ 에 따라서 전부 더하게 되면, 트라이앵귤레이션의 답을 구할 수 있는데요.

T_n = T_2 T_{n-1} + T_3 T_{n-2} + \cdots + T_{n-1} T_2

여기서 $C_n = T_{n+2}$ 라고 둔다면, 카탈란 점화식을 얻게 됩니다.

\tag{Eq.1} C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdots + C_{n-1} C_0

따라서 $n$ 각형을 삼각형으로 나누는 방법은 $C_n$ 가지, 즉 카탈란 넘버가 됩니다.

삼각형 대신 선으로 나누기

다른 방법으로 케이스를 나눈다면 또다른 카탈란 점화식인 $C_n = \frac{4n-2}{n+1} C_{n-1}$ 을 얻을 수 있는데요. 첫 번째 꼭지점에서 $k$ 번째 꼭지점까지 대각선을 긋는다고 생각해봅시다.

Polygon divided — 그림 4. 대각선으로 나눠진 다각형. 1번 꼭지점에서 어디로 대각선을 긋는지에 따라 나눕니다. 이 대각선은 삼각형의 한 변으로 쓸 것입니다.

그러면 두 개의 다각형으로 나뉘게 되는데요. 이때 $k$ 는 범위를 $3 \le k \le (n-1)$ 으로 가지고요. 모든 $k$ 의 범위에 대해 더하게 되면 $\sum_{k=3}^{n-1} T_k T_{n-k+2}$ 를 얻게 됩니다.

하지만 첫번째 꼭지점 말고 다른 꼭지점들도 생각할 필요가 있는데요. 일단 모든 꼭지점에 대해서 더하면, $n$ 을 곱해서 $n \sum_{k=3}^{n-1} T_k T_{n-k+2}$ 개가 됩니다.

이 카운팅에는 중복이 있는데요. 하나의 트라이앵귤레이션에 대해서 $2(n-3)$ 번 센 셈이 됩니다. 왜일까요?

Duplicate cases — 그림 5. 하나의 트라이앵귤레이션에 대한 중복 케이스들. 오각형의 경우 하나의 트라이앵귤레이션마다 네 가지의 중복된 경우가 존재합니다.

먼저, 삼각형을 이루는 두 대각선 중 하나를 고른 경우에 대해 중복이 생기기 때문에, 대각선의 개수인 $(n-3)$ 으로 나눠야 하고요. 한 대각선은 반대쪽 꼭지점에서 시작해 그을 수 있기 때문에, 여기에 둘로 나눠야하기 때문입니다. 따라서 $2(n-3)$ 번 중복이 있게 됩니다.

이 중복을 없애면 결국 원하는 답은 이렇게 됩니다.

T_n = \frac{n}{2(n-3)} \sum_{k=3}^{n-1} T_k T_{n-k+2}

여기서 $C_n = T_{n+2}$ 로 둔다면, 다음과 같은 식을 얻는데요.

C_n = \frac{n+2\mathstrut}{2(n-1)} (C_1 C_{n-1} + C_2 C_{n-2} + \cdots + C_{n-1} C_1)

기존에 얻었던 카탈란 점화식 $\textrm{Eq.1}$ 을 이용하면 $C_{n+1} = 2 C_n + \frac{4n+2}{n+2} C_n$ 을 얻습니다. (직접 해보세요.) 여기서 $n$ 에 $n-1$ 을 대입하면 원하는 결과가 나오게 됩니다.

\tag{Eq.2} C_n = \frac{4n-2\mathstrut}{n+1} C_{n-1}

클로즈드 폼 구하기

위의 결과 $\textrm{Eq.2}$ 를 이용해봅시다. 그러면 점화식 대신 클로즈드 폼 공식을 얻습니다.

\begin{align*} C_n &= \frac{4n-2\mathstrut}{n+1} \frac{4n-6}{n} \cdots \frac{6}{3} \frac{2}{2} C_0 \\ &= \frac{2^n}{(n+1)!} (2n-1)(2n-3) \cdots 3 \cdot 1 \\ &= \frac{2^n}{(n+1)!} \frac{(2n)!}{2^n n!} \\ &= \frac{1}{n+1} {2n \choose n} \end{align*}

이제 카탈란 넘버를 $O(n)$ 의 시간 복잡도로 계산할 수 있을 것입니다. 위의 점화식 $\textrm{Eq.2}$ 를 이용하거나, 클로즈드 폼에서 이항 계수를 $O(n)$ 의 시간 복잡도로 계산한다면요.

같은 결과를 미적분으로 해내기

위의 증명은 트라이앵귤레이션, 즉 기하학적인 해석으로부터 카탈란 넘버를 유도하고 있는데요. 미적분을 이용해 같은 결론을 이끌어 낼 수 있습니다.

먼저, 계수가 카탈란 넘버 $C_n$ 인, 제너레이팅 함수generating function라고도 불리는 함수 $C(x) = \sum_{n=0}^{\infty} C_n x^n$ 를 생각해봅시다. 그러면 다음과 같이 이차방정식으로부터 이 함수의 다른 표현을 얻게 됩니다.

\begin{align*} & \begin{aligned} (C(x))^{2\mathstrut} &= (C_0)^2 + (C_0 C_1 + C_1 C_0) x + (C_0 C_2 + (C_1)^2 + C_2 C_0) x^2 + \cdots \\ &= C_1 + C_2 x + C_3 x^2 + \cdots \\ &= (C(x) - C_0) / x \end{aligned} \\ & \Rightarrow x(C(x))^2 - C(x) + 1 = 0 \\ \tag{Eq.3} & \Rightarrow C(x) = \frac{1 - \sqrt{1 - 4x}}{2x} \end{align*}

여기서 근의 공식에서 양의 부호는 버립니다. 테일러 전개Taylor expansion를 이용할 때, $\sqrt{1-4x} = 1 - 2x + \cdots$ 로부터, $\frac{1 + \sqrt{1 - 4x}}{2x} = \frac{1}{x} - 1 + \cdots$ 이므로 $\frac{1}{x}$ 이 나와 맞지 않기 때문입니다.

먼저, 다음 식은 나중에 증명하기로 합니다.

\tag{Eq.4} \frac{1 - \sqrt{1 - 4x}}{2x} = \sum_{n=0}^{\infty} \frac{1}{n+1} {2n \choose n} x^n

이 식을 이용하면 $\textrm{Eq.3}$ 으로부터 다음을 얻습니다.

C(x) = \sum_{n=0}^{\infty} C_n x^n = \sum_{n=0}^{\infty} \frac{1}{n+1} {2n \choose n} x^n

여기서 각 항의 계수가 같아야 하므로, 카탈란 넘버의 클로즈드 폼 $C_n = \frac{1}{n+1} {2n \choose n}$ 을 얻습니다.

미뤘던 증명 끝내기

방금 사용했던 $\textrm{Eq.4}$ 를 증명할 차례인데요. 먼저 $A_n = {2n \choose n}$ 이라고 하고, 이를 계수로 갖는 함수 $A(x) = \sum_{n=0}^{\infty} A_n x^n$ 을 생각해봅시다. 이를 미분하면 다음을 얻습니다.

x A'(x) = x \left( \sum_{n=1}^{\infty} n A_n x^{n-1} \right) = \sum_{n=0}^{\infty} n A_n x^n

그런데 이항 계수의 정의를 이용하면 $(n+1) A_{n+1} = (4n+2) A_n$ 을 얻을 수 있습니다. (직접 해보세요.) 이것과 미분을 이용해 다음을 얻습니다.

\begin{align*} & \begin{aligned} A'(x) &= \sum_{n=0}^{\infty} (n+1) A_{n+1} x^n = \sum_{n=0}^{\infty} (4n+2) A_n x^n \\ &= 4 \sum_{n=0}^{\infty} n A_n x^n + 2 \sum_{n=0}^{\infty} A_n x^n \\ &= 4xA'(x) + 2A(x) \end{aligned} \\ & \Rightarrow \frac{A'(x)}{A(x)} = \frac{2}{1-4x} \end{align*}

양변을 적분하면 $A(x) = \frac{1}{\sqrt{1-4x}}$ 을 얻는데요. 이제 $A(x)$ 의 정의로부터 다음을 얻습니다.

\sum_{n=0}^{\infty} {2n \choose n} x^n = \frac{1}{\sqrt{1-4x}}

그 다음 양변을 적분하고 정리하면 $\textrm{Eq.4}$ 를 얻습니다. (이것도 직접 해보세요.)

카탈란 넘버의 모습

여기까지 긴 글이었습니다. 결국 카탈란 넘버는 $C_n = \frac{1}{n+1} {2n \choose n}$ 이 된다는 결론까지의 여정이었는데요. 여기서 카탈란 넘버의 근사값을 구할 수 있습니다. 스털링 근사Stirling’s approximation를 이용하면 이렇게 됩니다.

C_n = \frac{1}{n+1} \frac{(2n)!}{(n!)^2} \approx \frac{4^n}{n \sqrt{\pi n}} = O(4^n n^{-3/2})

이렇게 빅오 표기법big-O notation으로 카탈란 넘버의 어퍼 바운드upper bound를 알아냈습니다.

여기서 카탈란 넘버는 수가 커질 때 대략 네 배에 가까운 비율로 커지는 걸 볼 수 있는데요. (처음 글에서 대략 $4^n$ 만큼 빠르게 커진다고 언급했던 걸 기억하시나요?)

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, \dots

위와 같이 실제로 나열해보면 알 수 있습니다.

마치며

카탈란 넘버의 또 다른 점화식과 클로즈드 폼 공식을 유도해봤는데요. 이를 통해 카탈란 넘버가 증가하는 속도 또한 알 수 있었습니다.

첫 글에서 살펴봤던 것처럼, 바이너리 트리는 카탈란 넘버만큼 존재하는데요. 이로부터 바이너리 트리 또한 지수 함수만큼 매우 가파르게 개수가 늘어남을 알 수 있습니다. 따라서 노드가 조금만 많아져도 일일이 세기에는 사실상 풀기가 불가능한 문제였습니다.

레퍼런스

Catalan Numbers (Richard Stanley, 2015): 카탈란 넘버가 나타나는 다양한 문제를 담고 있습니다.
Catalan Numbers with Application (Thomas Koshy, 2008): 카탈란 넘버의 점화식과 클로즈드 폼의 증명을 찾아볼 수 있습니다.
oeis.org/A000108/list: 미리 계산된 카탈란 넘버입니다.