4. 카탈란 수의 일반항
조합론에 관련된 문제를 풀다 보면 <카탈란 수>라는 수열을 생각보다 많이 접할 수 있다.
정확하게 카탈란 수라는 이름을 주지는 않는 경우가 많지만 0번째 항부터 시작하는 첫 몇 개의 항이 1, 1, 2, 5, 14... 인 수열이라거나, 아니면 다음 점화식으로 이루어진 수열을 이용해야 하는 문제는 제법 보았을 것이다.
$$ C_{n+1} = \sum_{i+j=n}C_iC_j = \sum_{i=0}^{n} C_iC_{n-i} $$
그런데 이걸 매번 다이나믹 프로그래밍이나 재귀 함수로 풀다 보면, n이 충분히 커졌을 때 시간 초과를 받는 경우가 종종 생긴다.
그런 불상사를 시작 전에 회피하고자 한다. 그래서 이 포스트에서는 카탈란 수의 일반항을 구하는 방법을 다룰 것이다.
분명히 쓸모가 많을 것이다. 장담하건대.
우선 어떤 수열 \(\{a_n\}\)의 생성함수는 다음과 같이 멱급수의 꼴로 정의된다.
$$ f(x) := \sum_{i=0}^\infty a_ix^i $$
예를 들어서 피보나치 수열의 생성함수는 \(F(x)=x+x^2+2x^3+3x^4+\cdots\)로, 모든 항이 1인 수열의 생성함수는 \(U(x)=1+x+x^2+x^3+x^4+\cdots\)로 표현이 된다.
이를 적당한 수렴구간 내에서 조금 더 예쁜 함수로 변경할 수도 있다.
예를 들면 \(U(x)=\frac{1}{1-x}\)로 표현할 수 있으며, \(x+(x^2+x)F(x)=x+\sum_{i=2}^\infty{(F_{i-2}+F_{i-1})x^i}=\sum_{i=0}^\infty F_ix^i=F(x)\)으로부터 피보나치 수열의 생성함수가 \(F(x)=\frac{x}{1-x-x^2}\)임을 알 수 있다.
그러면 카탈란 수의 생성함수를 \(f(x)=\sum_0^\infty C_ix^i\)라고 두자. \(\{f(x)\}^2\)의 n차항은 어떤 모습일까?
멱급수의 곱셈은 다항함수의 곱셈과 당연히 아주 유사하게 정의된다. 따라서 다음과 같이 전개를 할 수 있는 것이다.
$$ \{f(x)\}^2=\left(\sum_{0}^{\infty}C_{i}x^{i}\right)\cdot\left(\sum_{0}^{\infty}C_{i}x^{i}\right) = \sum_{i,j}{C_i}{C_j}{x^{i+j}} $$
그러면 n차항의 계수는 \(\sum_{i+j=n}{C_i}{C_j}\)가 될 것이다! 이게 무엇인가? 바로 \(C_{n+1}\)이다!
따라서 \(x\{f(x)\}^2 = \sum_{i=1}^{\infty}C_ix^i=f(x)-1\)이 된다. \(f(x)=\frac{1-\sqrt{1-4x}}{2x}\)라는 것이다.
이제 일반항을 구하기 위해서 테일러 급수를 이용하자.
이항정리를 일반화한 공식을 이용한다면, 우선 \(\sqrt{1-4x}=\sum_{n=0}^{\infty}{{x^n}(-4)^n\binom{\frac{1}{2}}{n}}\)가 된다.
또한 \(\binom{\frac{1}{2}}{n}=\frac{\left(\frac{1}{2}\right)\cdot\left(\frac{1}{2}-1\right)\cdots\left(\frac{1}{2}-n+1\right)}{n!}=\frac{1\cdot(-1)\cdot(-3)\cdots(2n-3)}{n!\cdot2^n}\)\(=(-1)^{n-1}\frac{1\cdot2\cdots(2n-1)\cdot(2n)}{4^n(n!)^2}\cdot\frac{1}{2n-1}=-\frac{1}{(-4)^n}\cdot\frac{1}{2n-1}\cdot\binom{2n}{n}\)이 된다.
따라서 \(\sqrt{1-4x}=1-\sum_{n=1}^{\infty}\frac{x^n}{2n-1}\binom{2n}{n}\)이 되는 것이다.
이제 한 발자국만 남았다. 방금 얻은 결과를 \(f(x)\)에 집어넣어 보고 식을 정리해 보자.
$$f(x)=\frac{1}{2x}\sum_{n=1}^{\infty}\frac{x^n}{2n-1}\binom{2n}{n}=\sum_{n=0}^{\infty}\binom{2n+2}{n+1}\frac{x^n}{2(2n+1)}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{x^n}{n+1}$$
이제 모든 것이 끝났다. 카탈란 수의 생성함수 \(f(x)\)의 n차항으로부터 n번째 카탈란 수를 얻을 수 있는 것이다.
$$ C_n= \frac{1}{n+1}\binom{2n}{n} $$
이제 카탈란 수를 팩토리얼만 가지고 나타낼 수 있게 되었다!!
카탈란 수를 요구하는 문제에 아주 요긴하게 써먹어 보자. 예를 들면... 내가 다음 포스트에 올릴 1670번 문제라거나?
