카탈란 수
위키백과 ― 우리 모두의 백과사전.
조합론에서 자주 만날 수 있는 수열의 하나. 오일러가 "(n+2)-각형을 n개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났다. 수열의 이름은 벨기에의 수학자 카탈란의 이름을 따서 정해졌다.
0 이상의 n에 대해서 n 번째 카탈란 수
카탈란 수는 언제나 자연수가 되며, n = 0, 1, 2, 3, ... 번째 수는 아래와 같다. (OEIS의 수열 A000108)
- 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452...
[편집] 카탈란 수의 응용 예
조합론에서의 개수 세기 문제 가운데 많은 것이 카탈란 수를 그 해로 갖는다. 이 예제들은 조합수학자 리처드 P 스탠리의 저서 계수 조합론 2권에 나오는 카탈란 수의 서로 다른 66가지 표현 가운데 몇 개를 뽑은 것이다. 예제와 함께 있는 그림들은 C3 = 5의 경우의 예이다.
- Cn은 -1과 1 값으로 만들어진 수열 (a1, a2, ..., a2n)에서a1+a2+...+a2n=0 일 때, 각각의 부분합 a1, a1+a2, ..., a1+a2+...+a2n이 모두 0 이상이 되도록 하는 방법의 수이다.
- Cn은 ai가 1 또는 -1일 때, a1+a2+...+a2n+2=0이고 각각의 부분합 a1, a1+a2, ..., a1+a2+...+a2n+1이 모두 0 보다 크게 되도록 하는 방법의 수이다.
- Cn은 길이가 2n인 모든 Dyck word의 개수이다. Dyck word는 n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 Dyck word들을 나열한 것이다.
- Dyck word에서 X를 여는 괄호로 보고 Y를 닫는 괄호로 보면, Cn은 n쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다.
- Cn은 n + 1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 n + 1개의 항에 이항연산자를 적용하는 순서의 모든 가지수로도 볼 수 있다. 예를 들어 n = 3일 때, 4개의 항에 대해 다섯개의 괄호 표현식이 존재한다.

- 이항연산자의 적용 순서는 이진 트리로도 나타낼 수 있다. 따라서 Cn은 n + 1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다.
- Cn은 동형이 아닌 모든 포화 이진 트리(full binary tree) 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 n개인 트리의 개수이다. (포화 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)
[편집] 카탈란 수의 성질
- 카탈란 수는 다음 점화식을 만족한다.
- 카탈란 수의 생성함수를
로 정의할 때,
이 성립하고, 따라서
이 된다.
점근적으로 카탈란 수는
로 근사할 수 있다.