Catalan Numbers1. 카탈랑 수
외젠 샤를 카탈랑(Eugène Charles Catalan)이 1865년에 발견한
수열로, 보통 $$C_n$$으로 표기한다.
OEIS에
A000108수열로 등록되어 있다.
제9항까지의 값은 다음과 같다.
$$n$$
| [math(0)]
| $$1$$
| $$2$$
| $$3$$
| $$4$$
| $$5$$
| $$6$$
| $$7$$
| $$8$$
| $$9$$
|
$$C_n$$
| $$1$$
| $$1$$
| $$2$$
| $$5$$
| $$14$$
| $$42$$
| $$132$$
| $$429$$
| $$1430$$
| $$4862$$
|
$$n$$번째 카탈랑 수(Catalan Number) $$C_n$$는 다음
점화식의 형태로 나타낼 수 있다.
$$\displaystyle C_{n+1}=\sum_{i=0}^n C_i C_{n-i}~(n \ge 0)$$, $$C_0=1$$
|
위 점화식은 생각보다 독특한 방법으로 풀리는데, 먼저 카탈랑 수의
생성함수를 다음과 같이 정의하고 $$\left\{ c \left( x \right) \right\}^2$$을 계산해보면
$$\displaystyle c \left( x \right) = \sum_{n=0}^\infty C_n x^n = C_0 + C_1 x + C_2 x^2 + \cdots\cdots \\ \left\{ c \left( x \right) \right\}^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$$
|
점화식에 따라 합의 기호로 나타내어지는 $$x^n$$의 계수가 최초 생성함수 식에서 $$x^{n+1}$$의 계수이므로 생성함수에 대해 다음과 같은 관계식이 성립한다.
$$c \left( x \right) = 1 + x\left\{ c\left( x \right) \right\}^2$$
|
위 이차 방정식을 풀면
$$c \left( x \right) = \dfrac{1 \pm \sqrt{1 - 4x}}{2x} = \dfrac 2{1 \mp \sqrt{1 - 4x}}$$ (복부호 동순)
|
이 되는데 위 식에서 $$x \to 0$$일 때의 값 $$C_0 = 1$$이 존재하는 경우는 $$\dfrac{1 - \sqrt{1 - 4x}}{2x}$$뿐이며, 이 식에 대해 테일러 전개를 적용한다.
$$\displaystyle \begin{aligned} \sqrt{1-4x} &= \left( 1-4x \right)^{\frac 12} = \sum_{n=0}^\infty \binom{\frac 12}n \left( -4x \right)^n = 1 -2x + \sum_{n=2}^\infty \frac 1{n!} \prod_{r=0}^{n-2} \frac 12 \left( - \frac 12 - r \right) \left( -4 \right)^n x^n \\ &= 1 - 2x + \sum_{n=2}^\infty \frac 1{n!} \frac{ \left( -1 \right)^{n-1} (2n-3)!!}{2^n} \left( -1 \right)^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! \left( n-2 \right)! 2^{n-2}} 2^n x^n = 1 - 2x - \sum_{n=2}^\infty \frac{4 \left( 2n-3 \right)!}{n! \left( n-2 \right)!} x^n \\ &= 1 - 2x - \sum_{n=2}^\infty \frac{ 4 \cdot 2n \left( 2n-1 \right) \left( 2n-2 \right) \left( 2n-3 \right)!}{2^2 n\left( n-1 \right) \left( 2n-1 \right) n! \left( n-2 \right)!} x^n = 1 - 2x - \sum_{n=2}^\infty \frac{(2n)!}{\left( 2n-1 \right) \left( n! \right)^2}x^n \\ &= -\sum_{n=0}^\infty \frac 1{2n-1} \binom{2n}n x^n \end{aligned}$$
|
!!는 이중 계승 기호로 $$2$$씩 빼서 곱하라는 뜻이다. 위 식을 대입해서 정리하면
$$\displaystyle \begin{aligned} c \left( x \right) &= \sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1-4x}}{2x} = \frac 1{2x} \left( 1 + \sum_{n=0}^\infty \frac 1{2n-1} \binom{2n}n x^n \right) = \frac 1{2x} \sum_{n=1}^\infty \frac 1{2n-1} \binom{2n}n x^n \\ &= \sum_{n=1}^\infty \frac 1{2\left( 2n-1 \right)} \binom{2n}n x^{n-1} = \sum_{n=0}^\infty \frac 1{2\left( 2n+1 \right)} \binom{2n+2}{n+1} x^n = \sum_{n=0}^\infty \frac{(2n+2)!}{2\left( 2n+1 \right) \left\{(n+1)! \right\}^2}x^n \\ &= \sum_{n=0}^\infty \frac{(2n)!}{(n+1)!n!}x^n = \sum_{n=0}^\infty \frac{(2n)!}{\left( n+1 \right) \left( n! \right)^2} x^n \\ &= \sum_{n=0}^\infty \frac 1{n+1} \binom{2n}n x^n \end{aligned} \\ \therefore C_n = \frac 1{n+1} \binom{2n}n $$
|
카탈랑 수는 다음을 포함한 수많은 조합문제들의 답으로 등장한다. Richard Stanley의 조합론 교과서 'Enumerative Combinatorics'
[1] Stanley, Richard P. (1999), Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, ISBN 978-0-521-56069-6
에선 이런 예시들 66가지(...)가 연습문제로 나온다고 한다.
- 정$$n$$다각형에 대각선을 그어 삼각형으로 분할하는 방법의 수
- 딕 경로(Dyck paths): (0,0)에서 (n,n)까지 격자점을 따라 오른쪽(즉 (1,0)만큼) 혹은 위로(즉 (0,1)만큼) 한 칸씩 이동하는 경로 중, 대각선 $$x=y$$ 좌상단으로 넘어가지 않는 경로의 개수
- 각각 $$n$$개의 왼쪽 괄호와 오른쪽 괄호를 나열하는데 괄호가 서로 맞아떨어지는 문자열의 개수. 예로 $$n=2$$이면 (()), ()()의 두 가지 경우가 있다
- 크기 $$2 \times n$$짜리 표의 각 칸에 1부터 $$2n$$까지의 숫자를 집어넣는데, 아래로 가거나 오른쪽으로 갈수록 수가 커지는 방법의 수
이들의 대부분 경우에선 서로간의 조합론적 일대일대응을 찾을 수 있고, 일대일대응을 관찰하기 힘들더라도 상단의 점화식 $$C_{n+1}=\sum_{i=0}^n C_i C_{n-i}$$을 유도할 수 있는 경우가 많다. 한편 위의 딕 경로 문제에 대해선 점화식과 독립적으로
$$\displaystyle C_n = \binom{2n}{n} - \binom{2n}{n-1}$$
|
을 얻어내어 다음처럼 풀이하는 것도 가능하다. 만약 대각선을 넘어가는 경로가 있다면, 직선 $$l:y=x+1$$과 만나야 한다. $$A=(0,0)$$에서 $$B=(n,n)$$으로 가는 경로가 $$l$$과 만나는 최초의 점을 $$P$$라 하면, $$P \rightarrow B$$의 경로 부분만 $$l$$에 대칭시켜 변경해 $$A \rightarrow P \rightarrow (n-1,n+1)$$의 경로를 얻을 수 있다. 따라서 대각선을 넘어가는 경로는 $$(0,0)$$에서 $$(n-1,n+1)$$까지 이동하는 경로와 일대일대응되므로 그 개수는 $$\binom{2n}{n-1}$$개가 된다.
카탈랑 상수 참조.