카탈란 수

위키백과 ― 우리 모두의 백과사전.

조합론에서 자주 만날 수 있는 수열의 하나. 오일러가 "(n+2)-각형을 n개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났다. 수열의 이름은 벨기에의 수학자 카탈란의 이름을 따서 정해졌다.

0 이상의 n에 대해서 n 번째 카탈란 수

C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{n!(n+1)!}

이다. (이항계수차례곱 항목 참고)

카탈란 수는 언제나 자연수가 되며, 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 이상이 되도록 하는 방법의 수이다.
  • Cnai가 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들을 나열한 것이다.
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.
  • Dyck word에서 X를 여는 괄호로 보고 Y를 닫는 괄호로 보면, Cnn쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다.
((()))     ()(())     ()()()     (())()     (()())
  • Cnn + 1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 n + 1개의 항에 이항연산자를 적용하는 순서의 모든 가지수로도 볼 수 있다. 예를 들어 n = 3일 때, 4개의 항에 대해 다섯개의 괄호 표현식이 존재한다.
((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))
  • 이항연산자의 적용 순서는 이진 트리로도 나타낼 수 있다. 따라서 Cnn + 1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다.
  • Cn은 동형이 아닌 모든 포화 이진 트리(full binary tree) 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 n개인 트리의 개수이다. (포화 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)

[편집] 카탈란 수의 성질

  • 카탈란 수는 다음 점화식을 만족한다.
C_0 = 1 \qquad \mbox{and} \qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\quad\mbox{for }n\ge 1.
C(z)=\sum_{n=0}^\infty C_n z^n

로 정의할 때,

C(z)=1+zC(z)^2\,

이 성립하고, 따라서

C(z) = \frac{1-\sqrt{1-4z}}{2z} = \sum_{n=0}^\infty{2n \choose n}\frac{z^n}{n+1}

이 된다.

점근적으로 카탈란 수는

C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}

로 근사할 수 있다.

[편집] 외부 고리