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