카탈란 수(Catalan number)
수학이야기/확률통계 2011. 4. 25. 14:34카탈란 수(catalan number)로 불리는 수열이 있다. 핀란드 수학자 카탈란의 이름이 붙인 이 수열을 기호로는 $C_n$으로 나타낸다. 이 수열은 여러 가지 다른 문제를 풀이하는 과정에 나타난다.
카탈란 수열 문제들
잘 짜인 괄호
괄호 ()는 열고 닫았을 때, 잘 짜였다고 한다. 예를 들어 (())은 잘 짜인 것이지만 ())(은 잘못 짜인 것이다.
$n$쌍의 ()를 잘 짜인 모양으로 늘어 놓는 방법은 모두 몇 가지가 있을까?
산 만들기
괄호와 마찬가지로 오르막과 내리막을 $n$ 쌍으로 산을 만들 수 있는 방법의 수는 어떻게 구할까?
대각선 피해가기
정사각형들로 이루어진 $n\times n$ 개의 커다란 정사각형들의 변을 따라 이동할 때 대각선과 만나지 않고 이동하는 방법은 몇 가지일까? 그림과 같이 이 문제는 산 만들기와 일대일 대응된다.
다각형을 삼각형으로 나누기
$n+2$개 변으로 이루어진 볼록다각형을 서로 만나지 않는 대각선을 써서 $n$개의 삼각형으로 나누는 방법의 수
카탈란 수 구하기
괄호 만들기
$n$ 쌍의 괄호가 잘 짜인 방법의 수를 $C_n$이라고 하자.
이제 $C_0 ,C_1 ,C_2 , \cdots, C_{n-1}$으로 $C_n$을 나타내는 길을 찾아보자.
$n-1$쌍의 괄호가 잘 짜인 것에 ()를 알맞은 곳에 넣어주는 방법을 세면 된다.
$(A) B$와 같이 넣는다고 하면 $A$와 $B$도 잘 짜여 있어야 하고 만일 $A$에 괄호가 $k$쌍이 있다면 $B$에는 $n-1-k$쌍이 있어야 한다.
이제 문제는 $A$와 $B$로 나누는 방법을 세면 된다.
따라서 아래와 같은 점화식을 얻을 수 있다.
$C_1 =C_0 C_0$
$C_2 =C_0 C_1 +C_1 C_0$
$C_3 =C_0 C_2 +C_1 C_1+C_2 C_0$
$C_4 =C_0 C_3 +C_1 C_2+C_2 C_1 +C_3 C_0$
$\vdots$ $\vdots$
대각선 피하기
$n=5$일 때 그림은 아래와 같다. 모든 경우의 수에서 대각선과 만나는 수를 빼면 된다.
이들은 조합으로 셀 수 있다. 그림과 같이 점 $P$에서 대각선을 넘는다면 나머지 부분은 대각선을 축으로 대칭이동한다. 두 번째 그림과 같이 옮겨지므로 ${}_{10 }C_5 -{}_{10} C_6 $가 대각선과 만나지 않는 경로의 수가 된다.
일반적으로 $n\times n$이라면 $ {}_{2n} C_n - {}_{2n} C_{n+1}$ 이다.
따라서 카탈란 수열의 일반항은
$$C_n = {}_{2n}C_n -{}_{2n} C_{n+1} = {}_{2n} C_n - \frac{n}{n+1} {}_{2n} C_{n} =\frac{1}{n+1} {}_{2n} C_n$$
다각형 나누기
그림과 같이 $C_2 =2$, $C_3 =5$, $C_4 =14$이다.
$C_1=1$이라고 하고 이를 수열로 나타내면 $1,2,5,14,42,132,429,\cdots$이다.
점화식을 찾아보자. 먼저 8 각형을 살펴보자.
변 하나와 다른 꼭짓점을 택하는 방법은 그림과 같이 6가지다.
이제 각각의 그림에서 나누어진 다각형들을 삼각형으로 나누는 카탈란 수를 생각하면
$$C_6 =C_0\cdot C_5 +C_1\cdot C_4 +C_2\cdot C_3 +C_3\cdot C_2 +C_4\cdot C_1 +C_5\cdot C_0 $$이다.
이를 일반화하면
$$C_n =C_0\cdot C_{n-1} +C_1\cdot C_{n-2}+C_2\cdot C_{n-3} +\cdots+C_{n-2}\cdot C_1 +C_{n-1}\cdot C_0 $$이다.
이것은 카탈란 수열과 같다.
일반항을 조합으로 나타내면 $$C_n={}_{2n} C_n - {}_{2n} C_{n+1}= \frac{1}{n+1}{}_{2n} C_{n}$$이다.
생성함수
카탈란 수 $C_n$의 생성함수를 $$f(x)=\sum_{n=0}^{\infty}{C_n x^n}=C_0 +C_1 x +C_2 x^2 +\cdots+C_n x^n +\cdots$$라 하면,
$$\begin{split}f(x)^2 &=(C_0 +C_1x +C_2 x^2 +C_3 x^3+\cdots)(C_0 +C_1x +C_2 x^2 +C_3 x^3+\cdots)\\ &=C_0 C_0 +(C_0 C_1 +C_1 C_0 )x +(C_0 C_2 +C_1 C_1 +C_2 C_0 )x^2 +\cdots \\&=C_1 +C_2 x +C_3 x^2 +C_4 x^3 + \cdots\end{split}$$
이므로
$$\begin{split}xf(x)^2 &=C_1 x +C_2 x^2 +C_3 x^3 +C_4 x^4 + \cdots \\&=C_0 +(C_1 x +C_2 x^2 +C_3 x^3 +C_4 x^4 + \cdots )-C_0 \\&=f(x)-1\end{split}$$이다. 즉, $C_n$의 생성함수 $f(x)$는 방정식
$$xf(x)^2 -f(x)+1=0$$을 만족한다. 따라서 근의 공식에 의해
$$f(x)=\frac{1 \pm \sqrt{1-4x}}{2x}$$이다. 충분히 작은 $x$에 대하여 $f(0)=1$이 성립, 다시 말하면
$$\lim_{x\rightarrow 0}f(x)=1$$이어야 하므로 카탈란 수 $C_n$의 생성함수는
$$f(x)=\frac{1 - \sqrt{1-4x}}{2x}$$이다.
연분수로 나타내기
연분수(Continued_fraction) 표현을 위해 위 방정식 $xf(x)^2 -f(x)+1=0$을 변형해 보자.
$$xf(x)-1+\frac{1}{f(x)}=0$$
$$\frac{1}{f(x)}=1-xf(x)$$
$$f(x)=\frac{1}{1-xf(x)}$$이다.
$$\displaystyle{f(x)=\frac{1}{1-\frac{x}{1-xf(x)}}}$$
그러므로 아래와 같은 연분수로 나타낼 수 있다.
$$f(x)=\cfrac{1}{1-\cfrac{x}{1-\cfrac{x}{1-\cfrac{x}{1-\cfrac{x}{1-\cdots}}}}}$$
참고
http://en.wikipedia.org/wiki/Eug%C3%A8ne_Charles_Catalan
http://en.wikipedia.org/wiki/Catalan_number
http://mathworld.wolfram.com/CatalanNumber.html
http://www.geometer.org/mathcircles/catalan.pdf
