이전 글에서 다음과 같은 점화식을 소개했습니다.

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

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

예를 들어, 어떤 문제에서 세야 할 경우의 수가 이미 해결한 문제의 것과 일대일 대응됨을 보일 것입니다. 그러면 더 세볼 것도 없이 답은 둘 다 똑같다는 것을 보인 것입니다. 이것을 어렵게 말하면 두 문제 간의 바이젝션bijection을 찾는다고 말합니다.

앞으로 소개할 문제는 이런 식으로 해결할 것입니다. 그러면 관련 없어 보이는 문제들이 신기하게도 본질적으로는 똑같은 문제임을 이해할 수 있게 됩니다.

격자에서 최소 경로 세기

우선 카탈란 넘버가 나타나는 대표적인 문제인 딕 패스Dyck path 문제를 보겠습니다. 딕 패스란 격자 위에서 대각선 위를 넘지 않고 반대편에 도달하는 최소 경로를 말합니다.

그러면 가로 세로가 네 칸인 격자에서 딕 패스는 몇 개가 있을까요? 물론 네 번째 카탈란 넘버인 $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$ )

다른 문제로 바꾸기

여기 투표 문제ballot problem가 있습니다.

후보는 A, B가 있고 방금 투표를 마쳤다. 투표함에는 짝수 개의 표, 즉 $2n$ 개의 표가 들어있다. 개표를 진행할 때, B가 A를 추월하지 않고 동점으로 끝나는 경우의 수는 몇 가지인가?

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

이 문제는 처음 보면 일일이 세야할 것 같지만, 그럴 필요 없이 딕 패스로 바꿔서 바로 해결할 수 있습니다.

딕 패스 문제에 대응시키기

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

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

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

이런 식으로 그려보면, 투표 문제에서 실패하는 경우는 딕 패스에서 실패하는 경우와 대응됩니다. 성공하는 경우도 마찬가지고요. 따라서 투표 문제는 딕 패스 문제로 바꿔서 해결할 수 있고, 결국 투표 문제의 답은 카탈란 넘버가 됩니다. (앞서 약속한대로 직접 풀지 않았습니다.)

괄호 짝 맞추기

여는 괄호와 닫는 괄호가 $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$ 으로 정렬할 수 있기 때문입니다. 이런식으로 정렬할 수 있으면 스택 소터블 퍼뮤테이션 이라고 합니다.

Stack sortable permutation — 그림 5. 스택으로 정렬하는 퍼뮤테이션 ‘132’. ‘1’은 스택에 푸시하자마자 팝합니다. 그리고 ‘32’를 스택에 차례로 푸시넣은 뒤 팝함니다. 따라서 ‘123’으로 정렬이 가능합니다.

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

마치며

카탈란 넘버는 앞서 여러 문제로 보였듯이 다양한 곳에서 등장합니다. 하지만 푸는 방법을 이해하고 나면, 카탈란 넘버 문제들은 똑같은 패턴을 가진다는 것을 볼 수 있습니다. 여기서는 경우의 수를 직접 세는 대신, 이미 해결한 문제와 일대일 대응 시키는 방법을 사용했습니다. 이렇게 하면 카탈란 넘버의 패턴이 다른 방식으로 볼 수 있게 됩니다.

레퍼런스

Catalan Numbers (Richard Stanley, 2015)