나무모에 미러 (일반/어두운 화면)
최근 수정 시각 : 2024-12-20 16:39:05

카탈랑 수

카탈란 수에서 넘어옴


파일:나무위키+유도.png  
은(는) 여기로 연결됩니다.
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. 개요2. 정의3. 조합론에서의 등장

Catalan numbers

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

2. 정의

[math(n)]번째 카탈랑 수 [math(C_n)]은 다음 점화식의 형태로 나타낼 수 있다. (단, [math(n)]은 [math(n\ge0)]인 정수)
[math(\begin{aligned} \displaystyle
C_0 &= 1 \\
C_{n+1} &= \sum_{i=0}^n C_i C_{n-i}
\end{aligned} )]
위 점화식은 생각보다 독특한 방법으로 풀리는데, 먼저 카탈랑 수의 생성함수를 다음과 같이 정의하고 [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 \\
\{c(x)\}^2 &= {C_0}^2 + (C_0 C_1 + C_1 C_0)x + (C_0 C_2 + {C_1}^2 + C_2 C_0)x^2 + \cdots + \!\biggl( \sum_{i=0}^n C_i C_{n-i} \biggr) x^n + \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 )]

3. 조합론에서의 등장

카탈랑 수는 다음을 포함한 수많은 조합문제들의 답으로 등장한다. Richard Stanley의 조합론 교과서 'Enumerative Combinatorics'[1]에선 이런 예시들 66가지(...)가 연습문제로 나온다고 한다.위의 문제들에서 왜 하필이면 카탈랑 수가 쓰일까? 이들의 대부분 경우에선 서로간의 조합론적 일대일대응을 찾을 수 있고, 일대일대응을 관찰하기 힘들더라도 상단의 점화식 [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})]개가 된다.
[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~

분류