카탈랑 수

C\에 대한 내용은 카탈랑 상수 문서 참고하십시오.

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제

기타	P-NP 문제^미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}

1. 카탈랑 수

1.1. 개요1.2. 정의1.3. 조합론에서의 등장

2. 카탈랑 상수

Catalan numbers

1. 카탈랑 수

1.1. 개요

외젠 샤를 카탈랑(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)]

1.2. 정의

[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 )]

1.3. 조합론에서의 등장

카탈랑 수는 다음을 포함한 수많은 조합문제들의 답으로 등장한다. Richard Stanley의 조합론 교과서 'Enumerative Combinatorics'[1]에선 이런 예시들 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})]개가 된다.

2. 카탈랑 상수

자세한 내용은 카탈랑 상수 문서 참고하십시오.

[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~

카탈랑 수

1. 카탈랑 수

1.1. 개요

1.2. 정의

1.3. 조합론에서의 등장

2. 카탈랑 상수

분류