카탈랑 수¶
카탈랑 수는 여러 조합론 문제에서 유용하게 쓰이는 수열이며, 이러한 문제에는 재귀적으로 정의되는 대상이 자주 등장합니다.
이 수열은 19세기에 살았던 벨기에의 수학자 카탈랑의 이름을 따서 명명되었습니다. (사실 이 수열은 카탈랑보다 한 세기 앞서 살았던 오일러도 이미 알고 있었습니다.)
처음 몇 개의 카탈랑 수 $C_n$은 다음과 같습니다(0부터 시작합니다):
$1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$
몇 가지 조합론 문제에서의 응용¶
카탈랑 수 $C_n$은 다음 문제들의 답입니다.
- 여는 괄호 $n$개와 닫는 괄호 $n$개로 이루어진 올바른 괄호 문자열의 개수입니다.
- 리프가 $n + 1$개인 루트 있는 정 이진 트리의 개수입니다(정점에는 번호가 매겨져 있지 않습니다). 루트 있는 이진 트리에서 모든 정점이 자식을 두 개 가지거나 하나도 가지지 않으면 이를 정 이진 트리라고 합니다.
- $n + 1$개의 인수에 괄호를 완전히 치는 방법의 수입니다.
- 변이 $n + 2$개인 볼록 다각형을 삼각분할하는 방법의 수입니다(즉, 대각선을 이용해 다각형을 서로 겹치지 않는 삼각형들로 분할하는 방법의 수입니다).
- 원 위의 점 $2n$개를 연결하여 서로 만나지 않는 현 $n$개를 만드는 방법의 수입니다.
- 내부 노드(즉, 자식을 적어도 하나 가지는 노드)가 $n$개인 서로 동형이 아닌 정 이진 트리의 개수입니다.
- 크기가 $n \times n$인 정사각 격자에서 점 $(0, 0)$부터 점 $(n, n)$까지 가는 단조 격자 경로 중 주대각선(즉, $(0, 0)$과 $(n, n)$을 잇는 대각선) 위로 올라가지 않는 경로의 개수입니다.
- 스택 정렬이 가능한 길이 $n$인 순열의 개수입니다(즉, 어떤 순열이 스택 정렬 가능한 것은 $a_k < a_i < a_j$를 만족하는 인덱스 $i < j < k$가 존재하지 않는 것과 동치임을 보일 수 있습니다).
- 원소가 $n$개인 집합의 비교차 분할의 개수입니다.
- 직사각형 $n$개를 사용하여 계단 $1 \ldots n$을 덮는 방법의 수입니다(계단은 $n$개의 열로 이루어지며, $i^{th}$ 열의 높이는 $i$입니다).
계산¶
카탈랑 수를 구하는 공식에는 재귀 공식과 해석적 공식 두 가지가 있습니다. 앞서 언급한 문제들은 모두 동치(답이 같음)라고 보므로, 아래 공식들을 증명할 때에는 가장 다루기 쉬운 문제를 선택하겠습니다.
재귀 공식¶
점화식은 올바른 괄호 문자열 문제로부터 쉽게 유도할 수 있습니다.
가장 왼쪽의 여는 괄호 $l$은 어떤 닫는 괄호 $r$과 짝을 이룹니다. $l$과 $r$ 사이에 괄호 쌍이 $k$개 있다고 가정합시다. 그 사이의 부분 문자열은 $k$쌍으로 이루어진 임의의 올바른 괄호 문자열이 될 수 있고, $r$ 뒤의 접미사는 $n-1-k$쌍으로 이루어진 임의의 올바른 괄호 문자열이 될 수 있습니다. 따라서 고정된 $k$에 대해 이러한 괄호 수열은 정확히 $C_k C_{n-1-k}$개 있습니다. 모든 $k=0,1,\ldots,n-1$에 대해 이를 더하면 $C_n$에 대한 점화식을 얻습니다.
같은 내용을 달리 말하면, 비어 있지 않은 모든 올바른 괄호 문자열은 $(A)B$ 꼴로 유일하게 분해할 수 있으며, 여기서 $A$와 $B$는 올바른 괄호 문자열입니다. $A$가 $k$쌍을 포함하면 $B$는 $n-1-k$쌍을 포함하므로, 같은 점화식을 얻습니다.
C++ 구현¶
const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init(int n) {
catalan[0] = catalan[1] = 1;
for (int i=2; i<=n; i++) {
catalan[i] = 0;
for (int j=0; j < i; j++) {
catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
if (catalan[i] >= MOD) {
catalan[i] -= MOD;
}
}
}
}
해석적 공식¶
(여기서 $\binom{n}{k}$는 일반적인 이항 계수, 즉 $n$개의 대상으로 이루어진 집합에서 $k$개의 대상을 고르는 방법의 수를 나타냅니다.)
위 공식은 정사각형 격자에서의 단조 경로 문제로부터 쉽게 유도할 수 있습니다. $n \times n$ 크기의 격자에서 단조 경로의 총 개수는 $\binom{2n}{n}$입니다.
이제 주대각선을 넘어가는 단조 경로의 개수를 세어 보겠습니다. 주대각선을 넘어가는 이러한 경로를 생각하고, 그 경로에서 대각선 위에 있는 첫 번째 간선을 찾습니다. 이 간선 이후의 경로 전체를 대각선에 대해 대칭시킵니다. 그 결과는 항상 $(n - 1) \times (n + 1)$ 격자에서의 단조 경로가 됩니다. 반대로, $(n - 1) \times (n + 1)$ 격자의 모든 단조 경로는 반드시 대각선과 교차합니다. 따라서 $n \times n$ 격자에서 주대각선을 넘어가는 모든 단조 경로를 빠짐없이 세었습니다.
$(n - 1) \times (n + 1)$ 격자에서 단조 경로의 개수는 $\binom{2n}{n-1}$입니다. 이러한 경로를 "나쁜" 경로라고 부릅시다. 결과적으로, 주대각선을 넘어가지 않는 단조 경로의 개수를 구하려면 위의 "나쁜" 경로의 개수를 빼면 되며, 이로써 다음 공식을 얻습니다.