카탈란 수(Catalan Number)란?

카탈란 수는 조합론에서 매우 중요한 수열 중 하나로, 여러 가지 조합적 문제에서 등장하는 계수입니다.

카탈란 수의 일반적인 정의는 다음과 같습니다.
$n$ 번째 카탈란 수 $C_{n}$ 은 다음과 같이 주어집니다.

C_{n} = \frac{1}{n + 1} (n 2 n) = \frac{( 2 n )!}{( n + 1 )! n !}, n \geq 0

카탈란 수의 조합적 해석

카탈란 수는 다양한 조합 문제에서 등장합니다. 대표적인 몇 가지 예를 살펴보겠습니다.

1. 올바른 괄호 문자열의 개수

길이가 $2 n$ 인 문자열에서 $^{'} (^{'}$ 와 $^{'})^{'}$ 를 사용하여 올바른 괄호 문자열을 만들 수 있는 개수는 $C_{n}$ 입니다.
예를 들어, $n = 3$ 일 때, 가능한 올바른 괄호 문자열은:
- ”((()))”
- ”(()())”
- ”(())()”
- ”()(())”
- ”()()()”
  → 총 5개이며, 이는 $C_{3} = 5$ 와 같습니다.

2. 이진 트리(Binary Tree)의 개수

노드가 $n$ 개인 이진 트리를 구성하는 방법의 수는 $C_{n}$ 입니다.
예를 들어, $n = 3$ 인 경우 가능한 이진 트리의 개수는 5개이며, 이는 $C_{3} = 5$ 와 동일합니다.

3. 격자 경로(Lattice Path) 문제

$n \times n$ 격자에서 대각선을 넘지 않는 경로의 개수는 $C_{n}$ 입니다.
즉, (0,0)에서 (n,n)으로 가는 경로 중에서 항상 대각선 아래에만 위치하는 경로를 찾는 문제에서 등장합니다.

4. 다각형의 삼각 분할(Triangulation of Polygon)

$(n + 2)$ 개의 변을 가진 볼록 다각형을 삼각형으로 나누는 방법의 수는 $C_{n}$ 입니다.
예를 들어, 오각형(5변)에서 삼각형으로 나누는 방법은 5가지이며, 이는 $C_{3} = 5$ 와 같습니다.

5. 스택을 이용한 정렬 가능한 순열(Stack-Sortable Permutations)

스택을 이용하여 정렬할 수 있는 길이 $n$ 의 순열의 개수는 $C_{n}$ 입니다.

카탈란 수의 첫 몇 개 값

$n$	$C_{n}$
0	1
1	1
2	2
3	5
4	14
5	42
6	132

이 수들은 올바른 괄호 문자열의 개수, 이진 트리의 개수, 다각형의 삼각 분할 방법 등의 문제에서 같은 값을 가집니다.

카탈란 수의 유도 과정

카탈란 수의 공식:

C_{n} = \frac{1}{n + 1} (n 2 n)

이 공식은 이항 계수(Binomial Coefficient)를 이용하여 유도할 수 있습니다.

이항 계수 $(n 2 n)$ 는 $2 n$ 개의 요소 중 $n$ 개를 선택하는 경우의 수입니다.
그러나 이 경우 모든 가능한 경로를 고려하는 것이므로, 불가능한 경로(대각선을 넘는 경로)를 제외해야 합니다.
이를 반영하기 위해 $\frac{1}{n + 1}$ 을 곱하여 조정합니다.

카탈란 수의 점화식(Recurrence Relation)

카탈란 수는 다음과 같은 점화식을 만족합니다.

C_{n} = k = 0 \sum n - 1 C_{k} C_{n - 1 - k}, C_{0} = 1

이 점화식은 괄호 문자열을 구성하는 방법이나 이진 트리를 구성하는 방법을 분석하면 자연스럽게 도출됩니다.

결론

카탈란 수는 다양한 조합 문제에서 등장하는 중요한 수열이다.
이항 계수와 밀접한 관계가 있으며, 점화식으로도 정의될 수 있다.
올바른 괄호 문자열, 이진 트리, 격자 경로, 다각형 분할 등 다양한 문제에서 동일한 수가 등장한다.

카탈란 수는 조합론에서 매우 중요한 역할을 하므로, 많은 경우에 유용하게 사용됩니다!