카탈란 수

수학 상수 [math]\displaystyle{ G }[/math]에 관한 내용은 카탈란 상수 문서를 읽어 주세요.

카탈란 수(Catalan Numbers)는 이산수학에서 자주 등장하는 수열이다.

수열의 처음 부분(0번째부터 10번째까지)은 아래와 같다.

• 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, … (OEIS의 수열 A000108)

등장 예시

• 질문 ①: 문자 A와 B가 각각 [math]\displaystyle{ n }[/math]개씩 있다. 이들 문자를 배열할 때, 첫 글자부터 임의의 지점까지 부분 문자열에 대해 항상 A의 개수가 B보다 많거나 같게 만들려고 한다. 이 조건을 만족하는 문자열은 총 몇 가지인가?
• 질문 ②: 도화지에서 경사와 길이가 일정한 ↗ 대각선과 ↘ 대각선을 각각 [math]\displaystyle{ n }[/math]개씩 이어붙여서 산 모양을 그리려고 한다. 이때 양 끝 지점은 지평선에 있고, 산 모양의 각 지점들은 항상 지표면 혹은 그보다 높이 있어야 한다. 이때 그릴 수 있는 지그재그 모양은 총 몇 개인가?
• 질문 ③: 각 라운드마다 둘이 붙어서 한 명이 다음 판으로 진출하는 게임이 있다. [math]\displaystyle{ n+1 }[/math]명이서 [math]\displaystyle{ n }[/math]라운드를 진행할 때, 토너먼트 대진을 짜는 방법은 총 몇 가지인가?
• 질문 ④: 볼록한 [math]\displaystyle{ n+2 }[/math]각형을 삼각형 [math]\displaystyle{ n }[/math]개로 분할하는 방법은 총 몇 가지인가?

위 질문의 답은 모두 카탈란 수 [math]\displaystyle{ C_n }[/math]이다.

정의와 점화식

카탈란 수는 아래 식으로 정의한다.

[math]\displaystyle{ C_n=\frac{1}{n+1} \binom{2n}{n}=\frac{(2n)!}{(n+1)!n!}\text{ for } n \geq 0 }[/math]

[math]\displaystyle{ C_n=\prod_{k=2}^n \frac{n+k}{k}\text{ for } n \geq 2 }[/math]

또, 이 정의는 점화식으로도 표현할 수 있다.

[math]\displaystyle{ C_0=1, C_{n+1}=\sum_{k=0}^n C_k C_{n-k}, n \geq 0 }[/math]

[math]\displaystyle{ C_0=1, C_{n+1}= \frac{2(2n+1)}{n+2} C_k, n \geq 0 }[/math]

생성 함수

생성 함수 [math]\displaystyle{ C(x)=C_0+C_1x+C_2x^2+ \cdots =\sum_{n=0}^\infty C_nx^n }[/math]은 점화식으로부터 이끌어낼 수 있다. 이 식의 양변을 제곱하면 [math]\displaystyle{ C(x)^2=\sum_{n=0}^\infty \sum_{k=0}^n C_kC_{n-k}x^n }[/math]이고, 앞의 점화식으로부터 [math]\displaystyle{ C(x)^2=\sum_{n=0}^\infty C_{n+1}x^n=\frac{C(x)-1}{x} }[/math]임을 알 수 있다.

따라서 [math]\displaystyle{ C(x)=\frac{1 \pm \sqrt{1-4x}}{2x} }[/math]로 정리되고, 여기서 [math]\displaystyle{ \lim_{x \to 0}C(x)=1 }[/math] 조건을 만족하는 것은 마이너스 부호다. [math]\displaystyle{ x=0 }[/math]에서도 정의가 되도록 한다면, 분자를 유리화해서 [math]\displaystyle{ C(x)=\frac{2}{1+\sqrt{1-4x}} }[/math]와 같이 쓰면 된다.