카탈란 수(Catalan Number)란?
카탈란 수는 조합론에서 매우 중요하게 다뤄지는 수열로, 재귀적으로 정의되는 객체를 세는 다양한 계산 문제에 등장하는 자연수 수열입니다.
카탈란 수가 나타나는 대표적인 경우
Cn은 길이가 2n인 딕 단어(Dyck word)의 개수입니다. 딕 단어란 n개의 X와 n개의 Y로 구성된 문자열로, 문자열의 어느 접두사에서도 Y의 개수가 X의 개수를 초과하지 않아야 합니다. 예를 들어 길이가 6인 딕 단어는 다음과 같습니다.
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
기호 X를 여는 괄호 '('로, Y를 닫는 괄호 ')'로 다시 해석하면, Cn은 n쌍의 괄호가 올바르게 짝을 이룬 표현식의 개수가 됩니다.
((())) ()(()) ()()() (())() (()())
Cn은 n+1개의 인자를 완전히 괄호로 묶는 서로 다른 방법의 수, 즉 이항 연산자를 n번 적용할 때 가능한 결합 순서의 수이기도 합니다. 예를 들어 n = 3일 때 네 개의 인자에 대해 다음과 같은 다섯 가지 괄호 묶음이 존재합니다.
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
이항 연산자의 연속적인 적용은 완전 이진 트리(full binary tree)로 표현할 수 있습니다. (루트가 있는 이진 트리에서 모든 정점이 자식을 두 개 가지거나 하나도 가지지 않을 때 이를 완전 이진 트리라 합니다.) 따라서 Cn은 리프 노드가 n+1개인 완전 이진 트리의 개수와 같습니다.
카탈란 수의 점화식
카탈란 수는 다음 점화식으로 정의됩니다.
C0 = 1, Cn+1 = Σ (i = 0 ~ n) Ci · Cn-i
닫힌 형태의 공식으로는 Cn = (2n)! / ((n+1)! × n!) 이며, 이를 이용하면 재귀 호출 없이도 효율적으로 계산할 수 있습니다.
예제
입력 - 6
출력 - 1 1 2 5 14 42
설명: n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... 에 해당하는 카탈란 수는
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ... 입니다.
C++ 구현 코드
#include<iostream>
using namespace std;
long int catalan(int n) {
if (n <= 1){
return 1;
}
long int result = 0;
for (int i=0; i<n; i++){
result += catalan(i)*catalan(n-i-1);
}
return result;
}
int main(){
for (int i=0; i<6; i++)
cout << catalan(i) << " ";
return 0;
}실행 결과
1 1 2 5 14 42