카탈랑 수 문서 원본 보기

{{위키데이터 속성 추적}}
{{구별|카탈랑 상수}}
[[조합론]]에서 '''카탈랑 수'''(Catalan數, {{llang|en|Catalan number}}) 또는 '''카탈란 수'''는 [[이진 트리]]의 수 따위를 셀 때 등장하는 [[수열]]이다.

== 정의 ==
'''카탈랑 수'''
:<math>C \colon \mathbb N \to \mathbb N</math>
:<math>C \colon n \mapsto C_n</math>
는 자연수열이며, 여러 방법으로 정의될 수 있다. 이 정의들은 모두 서로 [[동치]]이다.

=== 직접적 정의 ===
음이 아닌 정수 ''n''에 대해서, ''n'' 번째 '''카탈랑 수''' <math>C_n</math>는 다음과 같다.
:<math>C_n = \frac1{n+1}\binom{2n}n = \frac{(2n)!}{n!(n+1)!} = \prod_{i=2}^n\frac{n+i}i</math>
여기서 <math>(-)!</math>는 [[계승 (수학)]]이며, <math>\textstyle\binom{-}{-}</math>은 [[이항 계수]]이다.

=== 점화식 ===
카탈랑 수는 다음과 같은 [[점화식]]으로 재귀적으로 정의될 수 있다.
:<math>C_0 = 1</math>
:<math>C_{n+1}=\sum_{i+j = n}C_i C_j = C_0C_n+C_1C_{n-1}+\dotsb+C_nC_0\qquad(n\ge0)</math>
또한, 다음과 같은 점화식을 사용할 수도 있다.
:<math>C_0 = 1</math>
:<math>C_{n+1} = \frac{2(2n+1)}{(n+2)}C_n</math>

=== 생성 함수 ===
카탈랑 수는 그 [[생성함수 (수학)|생성 함수]]
:<math>C(z)=\sum_{n=0}^\infty C_n z^n</math>
를 통해 정의될 수도 있다. 이 경우,
:<math>C(z)=1+zC(z)^2</math>
이므로
:<math>C(z) = \frac{1-\sqrt{1-4z}}{2z} = \sum_{n=0}^\infty{2n \choose n}\frac{z^n}{n+1}</math>
이 된다. 그렇다면 카탈랑 수는
:<math>C_n = \left.\frac1{n!}\frac{\mathrm d^n}{\mathrm dz^n}C(z)\right|_{z=0}</math>
이다.

<div class="mw-collapsible mw-collapsed toccolours">
'''생성 함수를 통한 정의와 구체적 정의가 동치임의 증명'''
<div class="mw-collapsible-content">
카탈랑 수의 [[생성함수 (수학)|생성 함수]]를
:<math>C(z) = \sum_{n=0}^\infty C_nz^n</math>
라고 정의하자. [[점화식]]에 의하여 <math>C(z) = 1 + zC(z)^2</math>이므로,
:<math>C(z) = \frac{1-\sqrt{1-4z}}{2z}</math>
이다. 그 [[테일러 급수]]는 ([[뉴턴의 이항정리]]를 이용하면)
:<math>\sqrt{1-4z}=1-\sum_{n=1}^\infty\binom{2n}n\frac{z^n}{2n-1}</math>
이므로,
:<math>C(z)=\frac1{2z}\sum_{n=1}^\infty\binom{2n}n\frac{z^n}{2n-1}=\sum_{n=0}^\infty \binom{2n+2}{n+1}\frac{z^n}{2(2n+1)}=\sum_{n=0}^\infty\binom{2n}n\frac{z^n}{n+1}</math>
이다. 즉,
:<math>C_n = \binom{2n}n\frac 1{n+1}</math>
이다.
</div>
</div>

== 성질 ==
=== 점근적 성질 ===
점근적으로 카탈랑 수는
:<math>C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}</math>
로 근사할 수 있다. 이는 [[스털링 근사]]를 사용한 것이다.

=== 홀짝성 ===
카탈랑 수 <math>C_n</math>가 홀수일 [[필요 충분 조건]]은 <math>n</math>이 메르센 수 <math>n=2^k-1</math>인 것이다.<ref name="KS">{{저널 인용 | 이름1=Thomas | 성1=Koshy | 성2=Salmassi | 이름2=Mohammad | 날짜=2006 | url=https://www.maa.org/sites/default/files/Koshy-CMJ-2006.pdf | 제목=Parity and primality of Catalan numbers | 저널=The College Mathematics Journal | 권=37 | 호=1 | 쪽=52–53 | 언어=en | access-date=2020-01-26 | archive-date=2021-02-09 | archive-url=https://web.archive.org/web/20210209110106/https://www.maa.org/sites/default/files/Koshy-CMJ-2006.pdf | url-status= }}</ref>{{rp|52}}
:<math>\forall n\in\mathbb n\colon \left(C_n \mid 2 \iff \exists k\in\mathbb N\colon n = 2^k-1\right)</math>
즉, 홀수인 카탈랑 수는
:<math>C_{2^0-1} = 1</math>
:<math>C_{2^1-1} = 1</math>
:<math>C_{2^2-1} = 5</math>
:<math>C_{2^3-1} = 429</math>
따위의 수이다.

카탈랑 수 가운데 [[소수 (수론)|소수]]인 것은 <math>C_2=2</math> 및 <math>C_3 = 5</math> 밖에 없다.<ref name="KS"/>{{rp|53}}

== 예 ==
카탈랑 수의 ''n''=0…37까지의 값들은 아래와 같다. {{OEIS|A000108}}
:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364, …

== 응용 ==
[[조합론]]에서의 개수 세기 문제 가운데 많은 것이 카탈랑 수를 그 해로 갖는다. 이 예제들은 조합 [[수학자]] 리처드 P. 스탠리의 저서 《Enumerative Combinatorics》 2권<ref>
{{서적 인용
 |성=Stanley
 |이름=Richard P.
 |날짜=2001년 6월 4일
 |제목=Enumerative Combinatorics
 |판=1
 |권=2
 |url=http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/enumerative-combinatorics-volume-2
 |출판사=Cambridge University Press
 |isbn=9780521789875
}}</ref>에 나오는 카탈랑 수의 서로 다른 66가지 표현 가운데 몇 개를 뽑은 것이다. 예제와 함께 있는 그림들은 ''C''<sub>3</sub> = 5의 경우의 예이다.

* ''C''<sub>''n''</sub>은 -1과 1 값으로 만들어진 수열 (''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>2''n''</sub>)에서''a''<sub>1</sub>+''a''<sub>2</sub>+...+''a''<sub>2''n''</sub>=0 일 때, 각각의 부분합 a<sub>1</sub>, a<sub>1</sub>+a<sub>2</sub>, ..., ''a''<sub>1</sub>+''a''<sub>2</sub>+...+''a''<sub>2''n''</sub>이 모두 0 이상이 되도록 하는 방법의 수이다.
* ''C''<sub>''n''</sub>은 ''a''<sub>''i''</sub>가 1 또는 -1일 때, ''a''<sub>1</sub>+''a''<sub>2</sub>+...+''a''<sub>2''n''+2</sub>=0이고 각각의 부분합 a<sub>1</sub>, a<sub>1</sub>+a<sub>2</sub>, ..., ''a''<sub>1</sub>+''a''<sub>2</sub>+...+''a''<sub>2''n''+1</sub>이 모두 0 보다 크게 되도록 하는 방법의 수이다.
* ''C''<sub>''n''</sub>은 길이가 ''2n''인 모든 '''뒤크 단어'''({{llang|en|Dyck word}})의 개수이다. 발터 폰 뒤크({{llang|de|Walther von Dyck}})의 이름을 딴 뒤크 단어는 n개의 X와 n개의 Y로 이루어진 [[문자열]] 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다.
{{center|<big> XXXYYY &nbsp;&nbsp;&nbsp; XYXXYY &nbsp;&nbsp;&nbsp; XYXYXY &nbsp;&nbsp;&nbsp; XXYYXY &nbsp;&nbsp;&nbsp; XXYXYY.</big>}}
* 뒤크 단어에서 X를 여는 괄호로 보고 Y를 닫는 괄호로 보면, ''C''<sub>''n''</sub>은 ''n''쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다.
{{center|<big> ((())) &nbsp;&nbsp;&nbsp; ()(()) &nbsp;&nbsp;&nbsp; ()()() &nbsp;&nbsp;&nbsp; (())() &nbsp;&nbsp;&nbsp; (()()) </big>}}
* ''C''<sub>''n''</sub>은 ''n''&nbsp;+&nbsp;1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 ''n''&nbsp;+&nbsp;1개의 항에 [[이항 연산]]을 적용하는 순서의 모든 가지수로도 볼 수 있다. 예를 들어 ''n'' = 3일 때, 4개의 항에 대해 다섯개의 괄호 표현식이 존재한다.
{{center|<math>((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))</math>}}
* 이항 연산의 적용 순서는 [[이진 트리]]로도 나타낼 수 있다. 따라서 ''C''<sub>''n''</sub>은 ''n''&nbsp;+&nbsp;1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다.
[[파일:Catalan number binary tree example.png|가운데]]
* ''C''<sub>''n''</sub>은 [[동형]]이 아닌 모든 [[이진 트리#종류|정 이진 트리]] 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 ''n''개인 트리의 개수이다. ('''정''' 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)
* ''C''<sub>''n''</sub>은 ''n''+2각형을 ''n''개의 삼각형으로 나누는 방법의 수이다. 아래 그림은 6각형을 4개의 삼각형으로 나누는 모든 방법을 나타낸 것으로 총 <math>C_4</math>가지이다.
[[파일:Catalan-Hexagons-example.svg|350px|가운데]]

== 역사 ==
18세기에 [[몽골]]의 수학자 [[명안도]](c. 1692-c. 1763)가 최초로 발견하였다.<ref>{{저널 인용|성=Larcombe|이름=P.J.|날짜=1999-09|제목=The 18th century Chinese discovery of the Catalan numbers|저널=Mathematical Spectrum|권=32|호=1|쪽=5–7|url=http://ms.appliedprobability.org/data/files/Abstracts%2032/32-1-2.pdf|언어=en|확인날짜=2013년 3월 4일|보존url=https://web.archive.org/web/20160314041555/http://ms.appliedprobability.org/data/files/abstracts%2032/32-1-2.pdf|보존날짜=2016년 3월 14일|url-status=dead}}</ref><ref>{{저널 인용|저자=羅見今|제목=明安圖公式辨正|저널=內蒙古師大學報(自然科學版)|날짜=1988|권=1|쪽=42-48|언어=zh}}</ref><ref>{{저널 인용|제목=明安圖和他的冪級數展開式|저자=羅見今|저널=數學傳播|권=34|호=1|쪽=65–73|url=http://w3.math.sinica.edu.tw/math_media/d341/34106.pdf|날짜=2010|언어=zh|access-date=2013-03-04|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304185645/http://w3.math.sinica.edu.tw/math_media/d341/34106.pdf|url-status=}}</ref>

유럽 수학에서는 [[레온하르트 오일러]]가 "(''n''+2)-각형을 ''n''개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났다. [[벨기에]]의 수학자 [[외젠 샤를 카탈랑|외젠 샤를 카탈랑]]이 [[하노이의 탑]] 문제를 고려하면서 1838년에 재발견하였다.<ref>{{저널 인용
 |제목 = Note sur un Problème de combinaisons
 |날짜 = 1838
 |이름 = Eugène Charles
 |성    = Catalan
 |저널 = Journal de Mathématiques Pures et Appliquées (1<sup>re</sup> série)
 |권    = 3
 |쪽    = 111-112
 |언어 = fr
 |url    = http://portail.mathdoc.fr/JMPA/PDF/JMPA_1838_1_3_A13_0.pdf
}}{{깨진 링크|url=http://portail.mathdoc.fr/JMPA/PDF/JMPA_1838_1_3_A13_0.pdf }}</ref><ref>{{MacTutor|id=Catalan|title=Eugène Charles Catalan|date=2012-09}}</ref>

== 같이 보기 ==
* [[오일러 변환]]
* [[모츠킨 수]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=CatalanNumber|title=Catalan number}}
* {{eom|title=Binary tree|first=M.|last=Hazewinkel}}

{{전거 통제}}

[[분류:정수열]]
[[분류:열거조합론]]