카탈란 수(Catalan number)

카탈란 수(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