카탈랑 수

조합론에서, **카탈랑 수**(Catalan數, ) 또는 **카탈란 수**는 이진 트리의 수 따위를 셀 때 등장하는 수열이다.

## 정의
**카탈랑 수**
:C \colon \mathbb N \to \mathbb N
:C \colon n \mapsto C_n
는 자연수열이며, 여러 방법으로 정의될 수 있다. 이 정의들은 모두 서로 동치이다.

### 직접적 정의
음이 아닌 정수 n에 대해서, n번째 **카탈랑 수** C_n는 다음과 같다.
:C_n = \frac1{n+1}\binom{2n}n = \frac{(2n)!}{n!(n+1)!} = \prod_{i=2}^n\frac{n+i}i
여기서 (-)!는 계승이며, \textstyle\binom{-}{-}은 이항 계수이다.

### 점화식
카탈랑 수는 다음과 같은 점화식으로 재귀적으로 정의될 수 있다.
:C_0 = 1
:C_{n+1}=\sum_{i+j = n}C_i C_j = C_0C_n+C_1C_{n-1}+\dotsb+C_nC_0\qquad(n\ge0)
또한, 다음과 같은 점화식을 사용할 수도 있다.
:C_0 = 1
:C_{n+1} = \frac{2(2n+1)}{(n+2)}C_n

### 생성 함수
카탈랑 수는 그 생성 함수
: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 = \left.\frac1{n!}\frac{\mathrm d^n}{\mathrm dz^n}C(z)\right|_{z=0}
이다.


**생성 함수를 통한 정의와 구체적 정의가 동치임의 증명**

카탈랑 수의 생성 함수를
:C(z) = \sum_{n=0}^\infty C_nz^n
라고 정의하자. 점화식에 의하여 C(z) = 1 + zC(z)^2이므로,
:C(z) = \frac{1-\sqrt{1-4z}}{2z}
이다. 그 테일러 급수는 (뉴턴의 이항정리를 이용하면)
:\sqrt{1-4z}=1-\sum_{n=1}^\infty\binom{2n}n\frac{z^n}{2n-1}
이므로,
:C(z)=\frac1{2z}\sum_{n=1}^\infty\binom{2n}n\frac{z^n}{2n-1}=\sum_{n=0}^\infty \binom{2n+2}{n+1}\frac{z^n}{2(2n+1)}=\sum_{n=0}^\infty\binom{2n}n\frac{z^n}{n+1}
이다. 즉,
:C_n = \binom{2n}n\frac 1{n+1}
이다.



## 성질
### 점근적 성질
점근적으로 카탈랑 수는
:C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}
로 근사할 수 있다. 이는 스털링 근사를 사용한 것이다.

### 홀짝성
카탈랑 수 C_n가 홀수일 필요충분조건은 n이 메르센 수 n=2^k-1인 것이다.
:\forall n\in\mathbb N\colon \left(2\nmid C_n \iff \exists k\in\mathbb N\colon n = 2^k-1\right)
즉, 홀수인 카탈랑 수는
:C_{2^0-1} = 1
:C_{2^1-1} = 1
:C_{2^2-1} = 5
:C_{2^3-1} = 429
따위의 수이다.

카탈랑 수 가운데 소수인 것은 C_2=2 및 C_3 = 5 밖에 없다.

### 완전 단조성
실수 수열 a\colon\mathbb N\to\mathbb R가 다음 조건을 만족시키면, 완전 단조 수열()이라고 한다.
* 임의의 k,n\in\mathbb N에 대하여, (-1)^k\Delta^ka_n\ge0. 여기서 \Delta는 유한 차분이다. 특히,
** k=0인 경우에 따라, a는 음이 아닌 실수들로 구성된다.
** k=1인 경우에 따라, a는 감소 수열이다.

완전 단조 수열들의 집합 위에 다음과 같은 이항 관계를 정의하자.
:a\preceq b\iff a_0\le b_0
이에 따라, 완전 단조 수열들의 집합은 원전순서 집합을 이룬다. 그 극소 원소를 극소 완전 단조 수열()이라고 한다.

두 수열
:n\mapsto\frac{C_n}{4^n}\qquad(n\in\mathbb N)
:n\mapsto\frac4{\pi(2n+1)}-\frac{C_n}{4^n}\qquad(n\in\mathbb N)
은 극소 완전 단조 수열이다.

## 예
처음 몇 카탈랑 수는 아래와 같다 (n=0,1,\dots,37,\dots). 
: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, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364, …

## 응용
조합론에서의 개수 세기 문제 가운데 많은 것이 카탈랑 수를 그 해로 갖는다. 이 예제들은 조합 수학자 리처드 P. 스탠리의 저서 《Enumerative Combinatorics》 2권에 나오는 카탈랑 수의 서로 다른 66가지 표현 가운데 몇 개를 뽑은 것이다. 예제와 함께 있는 그림들은 *C*3 = 5의 경우의 예이다.

* *C**n*은 -1과 1 값으로 만들어진 수열 (*a*1, *a*2, ..., *a*2*n*)에서*a*1+*a*2+...+*a*2*n*=0 일 때, 각각의 부분합 a1, a1+a2, ..., *a*1+*a*2+...+*a*2*n*이 모두 0 이상이 되도록 하는 방법의 수이다.
* *C**n*은 *a**i*가 1 또는 -1일 때, *a*1+*a*2+...+*a*2*n*+2=0이고 각각의 부분합 a1, a1+a2, ..., *a*1+*a*2+...+*a*2*n*+1이 모두 0 보다 크게 되도록 하는 방법의 수이다.
* *C**n*은 길이가 *2n*인 모든 **뒤크 단어**()의 개수이다. 발터 폰 뒤크()의 이름을 딴 뒤크 단어는 n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다.

* 뒤크 단어에서 X를 여는 괄호로 보고 Y를 닫는 괄호로 보면, *C**n*은 *n*쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다.

* *C**n*은 *n*&nbsp;+&nbsp;1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 *n*&nbsp;+&nbsp;1개의 항에 이항 연산을 적용하는 순서의 모든 가지수로도 볼 수 있다. 예를 들어 *n* = 3일 때, 4개의 항에 대해 다섯개의 괄호 표현식이 존재한다.

* 이항 연산의 적용 순서는 이진 트리로도 나타낼 수 있다. 따라서 *C**n*은 *n*&nbsp;+&nbsp;1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다.
가운데
* *C**n*은 동형이 아닌 모든 정 이진 트리 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 *n*개인 트리의 개수이다. (**정** 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)
* *C**n*은 *n*+2각형을 *n*개의 삼각형으로 나누는 방법의 수이다. 아래 그림은 6각형을 4개의 삼각형으로 나누는 모든 방법을 나타낸 것으로 총 C_4가지이다.
350px|가운데

## 역사
18세기에 몽골의 수학자 명안도(c. 1692-c. 1763)가 최초로 발견하였다.

유럽 수학에서는 레온하르트 오일러가 "(*n*+2)-각형을 *n*개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났다. 벨기에의 수학자 외젠 샤를 카탈랑이 하노이의 탑 문제를 고려하면서 1838년에 재발견하였다.

## 같이 보기
* 오일러 변환
* 모츠킨 수

## 참고 문헌

## 외부 링크
* 
* 

분류:정수열
분류:열거조합론