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

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

---

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

---

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

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

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

카탈란 수열은 외젠 샤를 카탈랑(Eugène Charles Catalan)이 1838년에 제안하였습니다.

 

1-1. 카탈란 수열의 정의

카탈란 수열의 정의는 다음과 같습니다.

각 n개씩 가지고 있는 두 종류의 기호(A, B)를 길이 2n으로 나열할 때, 나열하는 매 순간 A의 개수가 B의 개수보다 적지 않도록 배열하는 방법의 수(나열하는 매 순간 $ \sum A \ge \sum B $)

또는

'1(A)' n개와 '-1(B)' n개를 2n개까지 차례대로 나열할 때, 나열하는 매 순간까지의 부분합이 음수가 되지 않게 나열하는 경우의 수
그 값이 바로 카탈란 수 $C_n$입니다.

그리고 여기서 각 n에 해당하는 경우의 수를 카탈란 수(Catalan Number), 이 수들이 이루는 수열을 카탈란 수열(Catalan Series)라고 합니다.

 

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각형의 내각의 합은 180°(n-2)입니다.
• 그 이유는 n각형은 항상 n-2개의 삼각형으로 분할할 수 있으며, 삼각형의 내각은 항상 180°이기 때문이죠.
• 여기서 볼록 다각형(n+2각형)을 삼각분할 하는 경우의 수(대각선 개수)는 꼭지점 고정시 재귀적으로 하위 다각형을 만들어가는 구조이며, 카탈란 수로 귀결됩니다!
• 단순 나열의 문제가 아닌 도형과 결부되며, 재귀적인 조합이 들어가는 문제이므로 자세한 유도는 이후 따로 진행하도록 하겠습니다.

즉, “교차하지 않는 대각선으로 삼각 분할” 이라는 조건이 A ≥ B 조건과 같은 재귀 구조를 만들어 낸다는 사실! 도형에서도 카탈란 수가 튀어나오는 이유가 여기 있습니다.

좀 더 확장해서 원 위에서 2n개의 점을 잡고 교차하지 않는 n개의 선분을 긋는 경우의 수도 포함됩니다!

2-5. n개의 노드를 가지는 이진트리 구성 방법의 수

• 이진트리는 노드 하나 + 왼쪽, 오른쪽 두개의 리프(leaf)노드를 가질 수 있는 구조입니다.
• 보통 첫 시작 노드는 루트 노드(root node), 말단 노드를 리프 노드(leaf node), 그 외 노드들을 내부 노드(internal node)라고 부릅니다.
• 여기서 n개의 노드를 가지는 이진트리를 구성하는 방법의 수가 카탈란 수!

2-6. 스택정렬 가능한 방법의 수

스택(stack)이란 바구니죠 바구니.

이 바구니에 어떤 숫자를 차례대로 넣을 때 만들 수 있는 경우의 수가 또한 카탈란 수 입니다.

가령 1, 2, 3이라고 하는 수를 차례대로 바구니에 넣을 때

1 넣고 바로 빼고 2 넣고 바로 빼고 3 넣고 바로 빼면 => 123

1 녛고 바로 빼고 2 넣고 3넣고나서 3빼고 2빼면(바구니라 넣었던 순서의 반대로밖에 못꺼냅니다) => 132

1 넣고 2넣고 바로 빼고 3 넣고 바로 빼고 마지막 1 빼면 => 231

1 넣고 2넣고 바로 빼고 1빼고 3넣고 바로 빼면 => 213

1 넣고 2 넣고 3 넣은 다음, 3빼고 2빼고 1빼면 => 321

이 다섯가지 경우밖에 만들 수 없고, 이것이 바로 $ C_3 $에 해당하는 5죠!

결국 정리해보면,

• 스택(stack)이란 바구니이며, 이 바구니에 특정 n가지의 수를 넣었다 빼었을 때 나올 수 있는 숫자(스택 정렬 가능한 숫자)
• ‘넣는 행위(push)’와 ‘빼는 행위(pop)’을 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	가능한 A/B 배열	$C_n$
0	(빈문자열)	$1$
1	AB	$1$
2	ABAB, AABB	$2$
3	ABABAB, AABABB, ABAABB, AAABBB, AAABAB	$5$

$n$이 커질수록 폭발적으로 늘어나죠? 실제로 카탈란 수열은 다음과 같습니다. $$ 1,\;1,\;2,\;5,\;14,\;42,\;132,\dots $$

 

5. 왜 재미있을까?

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

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

 

6. 마무리

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