[include(틀:이산수학)]
[목차]
{{{+1 Catalan numbers}}}

== 카탈랑 수 ==
=== 개요 ===
[[외젠 샤를 카탈랑]](Eugène Charles Catalan)이 1838년에 제안한 [[수열]]로, 보통 [math(C_n)]으로 표기한다. [[OEIS]]에 [[https://oeis.org/A000108|A000108]]수열로 등록되어 있다.

제9항까지의 값은 다음과 같다.
|| [math(n)] || [math(0)] || [math(1)] || [math(2)] || [math(3)] || [math(4)] || [math(5)] || [math(6)] || [math(7)] || [math(8)] || [math(9)] ||
|| [math(C_n)] || [math(1)] || [math(1)] || [math(2)] || [math(5)] || [math(14)] || [math(42)] || [math(132)] || [math(429)] || [math(1430)] || [math(4862)] ||

=== 정의 ===
[math(n)]번째 카탈랑 수 [math(C_n)]는 다음 [[점화식]]의 형태로 나타낼 수 있다.
||<tablealign=center><tablebordercolor=#fff,#1f2023><bgcolor=#fff,#1f2023> [math(\displaystyle C_{n+1}=\sum_{i=0}^n C_i C_{n-i}~(n \ge 0))], [math(C_0=1)] ||
위 점화식은 생각보다 독특한 방법으로 풀리는데, 먼저 카탈랑 수의 [[생성함수]]를 다음과 같이 정의하고 [math(\{c(x)\}^2)]을 계산해보면
||<tablealign=center><tablebordercolor=#fff,#1f2023><bgcolor=#fff,#1f2023> [math(\begin{aligned} c(x) &= \sum_{n=0}^\infty C_n x^n = C_0 + C_1 x + C_2 x^2 + \cdots\cdots \\ \{c(x)\}^2 &= {C_0}^2 + {\left( C_0 C_1 + C_1 C_0 \right)}x + {\left( C_0 C_2 + {C_1}^2 + C_2 C_0 \right)}x^2 + \cdots\cdots + {\left( \sum_{i=0}^n C_i C_{n-i} \right)} x^n + \cdots\cdots\end{aligned})] ||
점화식에 따라 합의 기호로 나타내어지는 [math(x^n)]의 계수가 최초 생성함수 식에서 [math(x^{n+1})]의 계수이므로 생성함수에 대해 다음과 같은 관계식이 성립한다.
||<tablealign=center><tablebordercolor=#fff,#1f2023><bgcolor=#fff,#1f2023> [math(c(x) = 1 + x\{c(x)\}^2)] ||
위 이차 방정식을 풀면
||<tablealign=center><tablebordercolor=#fff,#1f2023><bgcolor=#fff,#1f2023> [math(c(x) = \dfrac{1 \pm \sqrt{1 - 4x}}{2x} = \dfrac 2{1 \mp \sqrt{1 - 4x}})] (복부호 동순) ||
이 되는데 위 식에서 [math(x \to 0)]일 때의 값 [math(C_0 = 1)]이 존재하는 경우는 [math(\dfrac{1 - \sqrt{1 - 4x}}{2x})]뿐이며, 이 식에 [[테일러 전개]]를 적용한다.
||<tablealign=center><tablebordercolor=#fff,#1f2023><bgcolor=#fff,#1f2023> [math(\displaystyle \begin{aligned} \sqrt{1-4x} &= {\left( 1-4x \right)}^{\frac 12} = \sum_{n=0}^\infty \binom{\frac 12}n (-4x)^n = 1 -2x + \sum_{n=2}^\infty \frac 1{n!} \prod_{r=0}^{n-2} \frac 12 {\left( - \frac 12 - r \right)} (-4)^n x^n \\ &= 1 - 2x + \sum_{n=2}^\infty \frac1{n!} \frac{(-1)^{n-1}(2n-3)!!}{2^n} (-1)^n 4^n x^n = 1 - 2x - \sum_{n=2}^\infty \frac{(2n-3)!!}{n!} 2^n x^n \\ &= 1 - 2x - \sum_{n=2}^\infty \frac{(2n-3)!}{n!(n-2)!2^{n-2}}2^n x^n = 1 - 2x - \sum_{n=2}^\infty \frac{4(2n-3)!}{n!(n-2)!}x^n \\ &= 1 - 2x - \sum_{n=2}^\infty \frac{4{\cdot}2n(2n-1)(2n-2)(2n-3)!}{2^2 n(n-1)(2n-1)n!(n-2)!}x^n = 1 - 2x - \sum_{n=2}^\infty \frac{(2n)!}{(2n-1)(n!)^2}x^n \\ &= -\sum_{n=0}^\infty \frac1{2n-1} \binom{2n}n x^n \end{aligned})] ||
[math(!!)]는 이중 계승 기호로 [math(2)]씩 빼서 곱하라는 뜻이다. 위 식을 대입해서 정리하면
||<tablealign=center><tablebordercolor=#fff,#1f2023><bgcolor=#fff,#1f2023> [math(\displaystyle \begin{aligned} c(x) &= \sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1-4x}}{2x} = \frac 1{2x}{\left( 1 + \sum_{n=0}^\infty \frac1{2n-1} \binom{2n}n x^n \right)} = \frac1{2x} \sum_{n=1}^\infty \frac1{2n-1} \binom{2n}n x^n \\ &= \sum_{n=1}^\infty \frac1{2(2n-1)} \binom{2n}n x^{n-1} = \sum_{n=0}^\infty \frac1{2(2n+1)} \binom{2n+2}{n+1}x^n = \sum_{n=0}^\infty \frac{(2n+2)!}{2(2n+1)\{(n+1)!\}^2}x^n \\ &= \sum_{n=0}^\infty \frac{(2n)!}{(n+1)!n!}x^n = \sum_{n=0}^\infty \frac{(2n)!}{(n+1)(n!)^2}x^n \\ &= \sum_{n=0}^\infty \frac1{n+1} \binom{2n}n x^n \end{aligned} \\ \therefore C_n = \frac1{n+1} \binom{2n}n )] ||

=== [[조합론]]에서의 등장 ===
카탈랑 수는 다음을 포함한 수많은 조합문제들의 답으로 등장한다. Richard Stanley의 조합론 교과서 'Enumerative Combinatorics'[* Stanley, Richard P. (1999), Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, ISBN 978-0-521-56069-6, 219p~]에선 이런 예시들 66가지(...)가 연습문제로 나온다고 한다.
 * 정[math(n)]다각형에 대각선을 그어 삼각형으로 분할하는 방법의 수
 * 딕 경로(Dyck paths): [math((0,\,0))]에서 [math((n,\,n))]까지 [[격자점]]을 따라 오른쪽(즉 [math((1,\,0))]만큼) 혹은 위로(즉 [math((0,\,1))]만큼) 한 칸씩 이동하는 경로 중, 대각선 [math(x=y)] 좌상단으로 넘어가지 않는 경로의 개수
 * 각각 [math(n)]개의 왼쪽 괄호와 오른쪽 괄호를 나열하는 데 괄호가 서로 맞아떨어지는 문자열의 개수. 예로 [math(n=2)]이면 (()), ()()의 두 가지 경우가 있다
 * 크기 [math(2 \times n)]짜리 표의 각 칸에 [math(1)]부터 [math(2n)]까지의 숫자를 집어넣는데, 아래로 가거나 오른쪽으로 갈수록 수가 커지는 방법의 수
위의 문제들에서 왜 하필이면 카탈랑 수가 쓰일까? 이들의 대부분 경우에선 서로간의 조합론적 일대일대응을 찾을 수 있고, 일대일대응을 관찰하기 힘들더라도 상단의 점화식 [math(\displaystyle C_{n+1}=\sum_{i=0}^n C_i C_{n-i})]을 유도할 수 있는 경우가 많다. 한편 위의 딕 경로 문제에 대해선 점화식과 독립적으로
||<tablealign=center><tablebordercolor=#fff,#1f2023><bgcolor=#fff,#1f2023> [math(C_n = \dbinom{2n}n - \dbinom{2n}{n-1} = \dfrac1{n+1}\dbinom{2n}n)] ||
로 바로 일반항을 도출하는 것도 가능하다. 풀이는 다음과 같다.
만약 대각선을 넘어가는 경로가 있다면, 직선 [math(l:y=x+1)]과 만나야 한다. [math(A=(0,\,0))]에서 [math(B=(n,\,n))]으로 가는 경로가 [math(l)]과 만나는 최초의 점을 [math(P)]라 하면, [math(P \to B)]의 경로 부분만 [math(l)]에 대칭시켜 변경해 [math(A \to P \to (n-1,\,n+1))]의 경로를 얻을 수 있다. 따라서 대각선을 넘어가는 경로는 [math((0,\,0))]에서 [math((n-1,\,n+1))]까지 이동하는 경로와 일대일대응되므로 그 개수는 [math(\dbinom{2n}{n-1})]개가 된다.

== [[카탈랑 상수]] ==
[[카탈랑 상수]] 참고

[[분류:수학]][[분류:이산수학]]