바이너리 트리의 개수를 세는 문제를 통해 카탈란 넘버를 알아본 이전 글에서 다음과 같은 점화식을 소개했는데요.

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

이 카탈란 넘버가 나타나는 다른 다양한 문제를 알아볼 것입니다. 하지만 문제를 직접 해결하는 대신, 이미 해결한 문제로 환원reduce하는 방법으로 풀어볼 것입니다.

다시 말해, 경우의 수를 세기 위해 카탈란 넘버를 직접 찾기 않고, 세야할 경우들이 기존에 해결한 문제와 일대일 대응됨을 보일 것입니다. 어렵게 말하면 두 문제 간의 바이젝션bijection을 찾는 것입니다.

우선 카탈란 넘버가 나타나는 또 다른 대표적인 문제인 딕 패스Dyck path 문제를 보겠습니다. 그리고 이 문제로 쉽게 바꿔칠 수 있는 다른 문제들도 보겠습니다.

격자에서 최소 경로 세기

딕 패스란 격자 위에서 대각선 위를 넘지 않고 반대편에 도달하는 최소 경로를 말하는데요.

Dyck path — 그림 1. 딕 패스 규칙. 경로가 대각선을 넘어가면 안 됩니다.

그러면 가로 세로가 네 칸인 격자에서 딕 패스는 몇 개가 있을까요? 물론 네 번째 카탈란 넘버인 $C_4 = 14$ 가 답이 될텐데요. 하지만 직접 계산해봅시다.

출발 이후에 대각선과 처음으로 닿는 점 $B$ 를 주목해봅시다. 그러면 이 점을 기준으로 두 개의 구역이 생깁니다. 그리고 총 경로의 개수는 그 두 구역에서 만들 수 있는 경로의 개수를 곱한 것이 됩니다.

Dyck path with cases — 그림 2. 딕 패스의 네 가지 패턴. 첫 번째로 대각선에 닿는 순간이 언제인지에 따라 나눕니다. 회색 삼각형은 더 작은 문제에 해당합니다.

가로와 세로의 길이가 $n$ 인 격자에 존재하는 딕 패스의 개수를 $C_n$ 이라고 해봅시다. 그러면 원하는 답인 $C_4$ 는 다음과 같이 계산할 수 있는데요.

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

길이가 없거나 하나인 경우 각각 딕 패스의 개수가 하나씩 있다고 합시다. ( $C_0 = 1$ , $C_1 = 1$ ) 그러면 $C_4$ 는 카탈란 넘버가 되고, 답은 정말로 14가지가 됩니다.

다른 문제로 바꿔치기

여기 투표 문제ballot problem가 있습니다. 두 후보 A, B를 둔 투표가 있고, 투표함에는 짝수 개, 즉 $2n$ 개의 표가 들어있는데요.

개표를 진행할 때, B가 A를 추월하지 않고 동점으로 끝나는 경우의 수는 몇 가지일까요?

Ballot problem rule — 그림 3. 추월이 없는 개표 진행. 오른쪽처럼 B는 A보다 더 많은 표를 가질 수 없습니다.

딕 패스 문제에 대응시키기

격자를 하나 그려봅시다. A의 표가 나올 때마다 오른쪽으로, B의 표는 위로 한 칸 움직인다고 해봅시다.

예를 들어 개표가 AAB까지 진행됐다고 해봅시다. 그러면 딕 패스 그리기는 실패하는데요.

Ballot as Dyck path — 그림 4. 개표가 AAB까지 진행됐을 때 그린 경로.

이런 식으로 투표 문제에서 실패하는 경우는 딕 패스에서 실패하는 경우와 각각 대응됩니다. 성공하는 경우도 마찬가지고요. 그러므로 투표 문제는 딕 패스 문제로 바꿔서 해결할 수 있고, 결국 투표 문제의 답은 카탈란 넘버가 됩니다.

괄호 짝 맞추기

여는 괄호와 닫는 괄호가 $n$ 개씩 있다고 해봅시다. 이것들을 짝이 맞도록 나열하는 방법은 몇 가지가 있을까요? 예를 들어 $()()$ 는 옳은 방법이지만, $())($ 는 틀린 방법입니다. (즉 열기 전에 닫으면 안됩니다.)

괄호를 나열하는 매 순간마다 닫는 괄호가 더 많으면 안되는데요. 그런데 비슷한 상황이 아까도 있었습니다. 투표 문제에서도 한쪽이 표를 더 많이 받는 상황이 없어야 했습니다.

그러면 가상의 투표를 떠올려 봅시다. 그리고 여는 괄호와 닫는 괄호가 나올 때마다 각각 후보 A, B의 표가 개표되었다고 해봅시다.

\begin{align*} (()()) \: & \rightarrow \: AABABB \quad\text{(O)}\\ (()))( \: & \rightarrow \: AABBBA \quad\text{(X)} \end{align*}

괄호 문제의 각 케이스는 투표 문제의 케이스와 일대일 대응되는데요. 따라서 사실상 투표 문제의 답과 같게 됩니다. 즉 카탈란 넘버가 됩니다.

보너스 두 문제

하나는 숫자 나열 문제인데요. $i$ 번째 숫자는 $i$ 보다 크면 안됩니다. 즉 $123$ 과 $112$ 은 옳은 케이스지만, $223$ 과 $133$ 은 그렇지 않습니다. 그리고 다음 숫자는 이전의 숫자보다 작으면 안됩니다. 즉 $132$ 는 옳은 케이스가 아닙니다.

그러면 이런 식으로 나열할 수 있는 숫자는 몇 가지가 있을까요? 풀이는 생략하고 직접 해보는 문제로 남겨두겠습니다. 하지만 여태 했던 방법 그대로 해결할 수 있습니다. (힌트: $i$ 번째 숫자 $n$ 을 격자 위 점 $x=i$ , $y=n$ 에 대응시켜서 딕 패스 문제로 바꿔보세요.)

다른 문제로, 스택 소터블 퍼뮤테이션stack-sortable permutation이 있습니다. 즉 스택 하나를 이용해 정렬할 수 있는 퍼뮤테이션, 즉 순열의 개수를 구하는 문제인데요.

예를 들어 $n=3$ 인 경우, 퍼뮤테이션은 $123$ 을 섞은 $3!=6$ 개의 숫자들이 있습니다.

123, 132, 213, 231, 312, 321

여기서 $132$ 는 스택 소터블 퍼뮤테이션입니다. 왜냐면 다음과 같이 $123$ 으로 정렬할 수 있기 때문입니다. 첫 번째 숫자는 스택에 넣자마자 뺍니다. 그리고 나머지 두 숫자를 차례로 스택에 넣은뒤 모두 빼면 $123$ 이 완성됩니다.

Stack sortable permutation — 그림 5. 스택으로 정렬하는 퍼뮤테이션 ‘132’. ‘32’를 스택으로 정렬할 수 있으므로, ‘132’는 ‘123’으로 정렬이 가능합니다.

이런식으로 정렬할 수 있는 퍼뮤테이션을 스택 소터블 퍼뮤테이션 이라고 합니다.

그러면 $1$ 부터 $n$ 까지의 숫자로 만든 퍼뮤테이션 중에 몇 개가 스택 소터블 퍼뮤테이션일까요? (힌트: 스택에 푸시할 때와 팝할 때를 각각 여는 괄호와 닫는 괄호에 대응시켜보세요.)

마치며

이상하리만큼 다양한 곳에서 등장하는 카탈란 넘버를 살펴보았습니다. 여기서 답을 직접 구하는 대신, 기존에 풀었던 문제와 일대일 대응시키는 방법을 사용했습니다.

또 다른 문제: 트라이앵귤레이션

사실 역사를 거슬러 올라가보면 오일러Leonhard Euler와 함께 트라이앵귤레이션triangulation이라는 문제가 등장하는데요. 다각형을 삼각형으로 나누는 방법의 개수를 구하는 문제입니다. 사각형은 두 가지 방법으로 나눌 수 있고, 오각형은 다섯 가지 방법이 있습니다. 이런 예시로 볼 수 있듯이 여기에서도 카탈란 넘버가 나타납니다.

한편 이 문제로부터 카탈란 넘버의 클로즈드 폼closed-form 공식인 $C_n = \frac{1}{n+1}{2n \choose n}$ 을 얻을 수 있습니다. 이를 통해 $C_n$ 을 구하기 위해 점화식으로 다음 수를 계속 구하는 대신, 바로 계산할 수 있게 됩니다. 이는 다음에 기회가 되면 살펴보는 것으로 정리하겠습니다.

레퍼런스

Catalan Numbers (Richard Stanley, 2015)