카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?

오랜만의 포스팅으로 돌아왔습니다.
 
요 근래 새롭게 관심이 생긴 수열이 있습니다.
바로 카탈란 수열(Catalan Number)입니다. 뭐 카탈랑 수열이라고도 한다는군요.
어찌됐든, 그럼 이 수열은 어떻게 정의가 되는가... 하면, 일단 한가지 이야기를 해보도록하겠습니다.

카탈란 수열을 처음부터 파헤쳐 보자!

1. 카탈란 수열이 뭐길래?

카탈란 수열은 $1,\,1,\,2,\,5,\,14,\,42,\dots$ 처럼 시작하는 수열입니다. 정의는 간단합니다. “두 종류의 기호(A, B)를 길이 $2n$으로 나열할 때, 어느 접두사에서도 A의 개수가 B의 개수보다 적지 않도록 배열하는 방법의 수” 그 값이 바로 카탈란 수 $C_n$입니다.

2. 예시 살펴보기

2‑1. 영화관 잔돈 문제

어느 영화관 주인은 잔돈 0원으로 영업을 시작하고 마감까지 잔돈이 생기면 안 됩니다. 영화표는 5,000원, 손님은 5,000원권(A)과 10,000원권(B)만 가지고 오죠. 줄 세우는 순간순간 A ≥ B를 만족해야 잔돈이 안 생깁니다. 총 $2n$명의 손님(A $n$명, B $n$명)이 들어올 때 가능한 줄 세우기 가짓수가 $C_n$!

2‑2. 올바른 괄호 문자열

프로그래머라면 익숙한 “괄호 짝 맞추기” 역시 카탈란 수의 고전 예시입니다. 길이가 $2n$인 문자열에서 (를 A, )를 B라 두고 어느 접두사에서도 ( 개수 ≥ ) 개수, 최종적으로 동일한 개수를 만족해야 “올바른 괄호”가 됩니다. 그 가짓수가 또 $C_n$!

2‑3. 뒤크(Dyck) 문자열

문자열 이론에서는 이런 문자열을 Dyck 문자열이라 부릅니다. 조건은 동일해요.

• 길이 $2n$
• A와 B가 $n$개씩
• 모든 접두사에서 A ≥ B

영화관, 괄호치기, Dyck 문자열… 전부 같은 문제를 다른 언어로 설명했을 뿐이라는 사실!

2‑4. 볼록 다각형 삼각 분할(대각선 갯수 예시)

이번엔 도형으로 가봅시다. “볼록 $(n+2)$‑각형을 서로 교차하지 않는 대각선으로 쪼개 삼각형만 남도록 분할하는 방법의 수” — 이 역시 카탈란 수 $C_n$입니다.

왜 그럴까요? 간단한 귀납 논리를 보여드릴게요.

1. 기준 꼭짓점 고정 임의의 꼭짓점(편하게 1번 꼭짓점)을 고정합니다.
2. 첫 대각선 선택 1번 꼭짓점에서 다른 꼭짓점 $k+2$ ($0≤k≤n-1$)로 대각선을 긋습니다. 그러면 다각형이
     • 왼쪽 부분: $(k+2)$‑각형 → 삼각 분할 가짓수 $C_k$
     • 오른쪽 부분: $(n-k+1)$‑각형 → 삼각 분할 가짓수 $C_{n-1-k}$
   두 조각으로 나뉩니다.
3. 재귀적 조합 첫 대각선 선택 마다 양쪽을 독립적으로 삼각 분할하면 총 가짓수는 $$C_k \times C_{\,n-1-k}$$ 이를 $k=0$부터 $n-1$까지 합치면 $$C_n = \sum_{k=0}^{n-1} C_k\,C_{\,n-1-k}.$$ 이 재귀식이 바로 카탈란 수의 정의적 특징입니다!

즉, “교차하지 않는 대각선으로 삼각 분할” 이라는 조건이 A ≥ B 조건과 같은 재귀 구조를 만들어 낸다는 사실! 도형에서도 카탈란 수가 튀어나오는 이유가 여기 있습니다.(맛보기이므로 '와 그냥 신기하다~' 정도로만 봐주시면 됩니다. 카탈란 수의 재귀함수적 특징은 이후에 더 살펴보겠습니다.)

3. n × n 격자 맛보기

3‑1. R은 오른쪽, U는 위쪽

A를 R(오른쪽), B를 U(위쪽)으로 바꿔 생각해 봅시다. 그럼 (0,0)에서 (n,n)까지 오른쪽·위쪽으로만 2n번 이동하는 경로가 생깁니다. 조건 A ≥ B는 언제나 $y≤x$ 선 아래에 있다는 뜻. 이 경로를 Dyck 경로라고 부르는데, 본격적인 분석은 다음 포스팅에서 진행할 예정이니 여기서는 “카탈란 수가 격자 경로와도 연결된다!”만 기억해 두면 OK.

4. 작은 n 직접 세어 보기

$n$이 커질수록 폭발적으로 늘어나죠? 실제로 카탈란 수는 다음처럼 시작합니다. $$1,\;1,\;2,\;5,\;14,\;42,\;132,\dots$$

5. 왜 재미있을까?

• 영화관 잔돈 같은 스토리텔링 예제
• 괄호치기·컴퓨터 스택 문제
• 다각형 삼각 분할·트리 구조 등 수학·CS 곳곳에서 등장

이렇게 많은 분야에 얼굴을 내미니 안 재밌을 수가 없죠!

6. 마무리

오늘은 “카탈란 수는 무엇인가?”를 중점적으로 살펴봤습니다. 다음 포스팅에서는 다음 포스팅에서는 일반항 $C_n$을 손에 넣는 과정을 차근차근 풀어 보겠습니다. 기대해 주세요!