수학/ 카탈란 수 Catalan number

카탈란 수 Catalan number

---

정의

조합론에서, 이진 트리의 수 따위를 셀 때 등장하는 수열입니다. 

음이 아닌 정수 n에 대해서, n 번째 카탈란 수 Cn은 다음과 같습니다.

역사

18세기에 몽골의 수학자 명안도(c. 1692-c. 1763)가 최초로 발견하였습니다. 유럽 수학에서는 레온하르트 오일러가 "(n+2)-각형을 n개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났고, 벨기에의 수학자 외젠 샤를 카탈랑이 하노이의 탑 문제를 고려하면서 1838년에 재발견하였습니다.

응용

카탈란 수는 자연수열이며, 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, …

Cn은 -1과 1 값으로 만들어진 수열 (a1, a2, ..., a2n)에서a1+a2+...+a2n=0 일 때, 각각의 부분합 a1, a1+a2, ..., a1+a2+...+a2n이 모두 0 이상이 되도록 하는 방법의 수이다.

Cn은 ai가 1 또는 -1일 때, a1+a2+...+a2n+2=0이고 각각의 부분합 a1, a1+a2, ..., a1+a2+...+a2n+1이 모두 0 보다 크게 되도록 하는 방법의 수이다.

Cn은 길이가 2n인 모든 뒤크 단어(영어: Dyck word)의 개수이다. 

발터 폰 뒤크(독일어: Walther von Dyck)의 이름을 딴 뒤크 단어는 n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다.

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

뒤크 단어에서 X를 여는 괄호로 보고 Y를 닫는 괄호로 보면, Cn은 n쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다.

((()))     ()(())     ()()()     (())()     (()())

Cn은 n + 1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 n + 1개의 항에 이항연산자를 적용하는 순서의 모든 가지수로도 볼 수 있다. 

이항연산자의 적용 순서는 이진 트리로도 나타낼 수 있다. 따라서 Cn은 n + 1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다.

Cn은 동형이 아닌 모든 정 이진 트리 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 n개인 트리의 개수이다. (정 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)

Cn은 n+2각형을 n개의 삼각형으로 나누는 방법의 수이다. 

아래 그림은 4각형, 5각형, 6각형을 각각 2개, 3개, 4개의 삼각형으로 나누는 모든 방법을 나타냈다.

위 그림은 C4 = 14를 나타내는데, 순서대로 

Cn = 정 이진 트리에서 자식을 가진 노드 개수 

Cn = n+1개의 노드로 구성할 수 있는 트리 개수

Cn = n+1개의 묶음(..?)

Cn = 육각형을 4개의 삼각형으로 나눈다

Cn = 뒤크 단어 느낌(가장 마지막 -를 제외하고 생각한다). Mountain ranges라고 하여 산이 수평선 밑으로 내려가지 않게 한다.

-

https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

http://www.telsono.com/pelastration/numbers_catalan.html

http://aofa.cs.princeton.edu/60trees/

http://math.stackexchange.com/questions/1944275/rooted-binary-trees-and-catalan-numbers

https://en.wikipedia.org/wiki/Catalan_number