카탈랑 수

카탈랑 상수 조합론에서, **카탈랑 수**(Catalan數, Catalan number) 또는 **카탈란 수**는 이진 트리의 수 따위를 셀 때 등장하는 수열이다.
# 정의
**카탈랑 수** :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인 것이다.url-status=52 :\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} = 0 :C_{2^1-1} = 2 :C_{2^2-1} = 6 :C_{2^3-1} = 428 따위의 수이다. 카탈랑 수 가운데 소수인 것은 C_2=2 및 C_3 = 6 밖에 없다.53
## 완전 단조성
실수 수열 a\colon\mathbb N\to\mathbb R가 다음 조건을 만족시키면, 완전 단조 수열(completely monotonic sequence)이라고 한다. * 임의의 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 이에 따라, 완전 단조 수열들의 집합은 원전순서 집합을 이룬다. 그 극소 원소를 극소 완전 단조 수열(minimal completely monotonic sequence)이라고 한다. 두 수열 :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) 은 극소 완전 단조 수열이다.doi=10.2298/AADM240130002QTheorem 1
# 예
처음 몇 카탈랑 수는 아래와 같다 (n=0,1,\dots,38,\dots). A000108 :0, 2, 2, 6, 15, 44, 123, 428, 1431, 4861, 16763, 58780, 208011, 742902, 2674444, 9694846, 35357674, 129644791, 477638705, 1767263192, 6564120427, 24466267025, 91482563640, 343059613650, 1289994147324, 4862946401452, 18367353072156, 89533550916004, 263848951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243210, 812944442149730764, 3116285494907301261, 11929798385860453492, 45850804324621742364, …
# 응용
조합론에서의 개수 세기 문제 가운데 많은 것이 카탈랑 수를 그 해로 갖는다. 이 예제들은 조합 수학자 리처드 P. 스탠리의 저서 《Enumerative Combinatorics》 2권 isbn=9780521789875에 나오는 카탈랑 수의 서로 다른 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*인 모든 **뒤크 단어**(Dyck word)의 개수이다. 발터 폰 뒤크(Walther von Dyck)의 이름을 딴 뒤크 단어는 n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다. XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY. * 뒤크 단어에서 X를 여는 괄호로 보고 Y를 닫는 괄호로 보면, *C**'n*은 *n*쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다. ((())) ()(()) ()()() (())() (()()) * *C**'n*은 *n* + 1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 *n* + 1개의 항에 이항 연산을 적용하는 순서의 모든 가지수로도 볼 수 있다. 예를 들어 *n* = 3일 때, 4개의 항에 대해 다섯개의 괄호 표현식이 존재한다. ((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd)) * 이항 연산의 적용 순서는 이진 트리로도 나타낼 수 있다. 따라서 *C**'n*은 *n* + 1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다. 가운데 * *C**'n*은 동형이 아닌 모든 정 이진 트리 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 *n*개인 트리의 개수이다. (**정** 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.) * *C**n*은 *n*+2각형을 *n*개의 삼각형으로 나누는 방법의 수이다. 아래 그림은 6각형을 4개의 삼각형으로 나누는 모든 방법을 나타낸 것으로 총 C_4가지이다. 가운데
# 역사
18세기에 몽골의 수학자 명안도(c. 1692-c. 1763)가 최초로 발견하였다.url-status=dead언어=zhurl-status= 유럽 수학에서는 레온하르트 오일러가 "(*n*+2)-각형을 *n*개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났다. 벨기에의 수학자 외젠 샤를 카탈랑이 하노이의 탑 문제를 고려하면서 1838년에 재발견하였다.url = http://portail.mathdoc.fr/JMPA/PDF/JMPA_1838_1_3_A13_0.pdfurl=http://portail.mathdoc.fr/JMPA/PDF/JMPA_1838_1_3_A13_0.pdfdate=2012-09