카탈랑 수

위키백과, 우리 모두의 백과사전.
(카탈란 수에서 넘어옴)
이동: 둘러보기, 검색

참고 : '카탈랑'이 아니라 '카탈란'이 옳은 표현이다.

정의[편집]

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

카탈란 수는 자연수열이며, 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. 스탠리의 저서 계수 조합론 2권에 나오는 카탈란 수의 서로 다른 66가지 표현 가운데 몇 개를 뽑은 것이다. 예제와 함께 있는 그림들은 C3 = 5의 경우의 예이다.

  • Cn은 -1과 1 값으로 만들어진 수열 (a1, a2, ..., a2n)에서a1+a2+...+a2n=0 일 때, 각각의 부분합 a1, a1+a2, ..., a1+a2+...+a2n이 모두 0 이상이 되도록 하는 방법의 수이다.
  • Cnai가 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를 닫는 괄호로 보면, Cnn쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수이다.
((()))     ()(())     ()()()     (())()     (()())
  • Cnn + 1개의 항에 괄호를 씌우는 모든 경우의 수이다. 혹은 n + 1개의 항에 이항연산자를 적용하는 순서의 모든 가지수로도 볼 수 있다. 예를 들어 n = 3일 때, 4개의 항에 대해 다섯개의 괄호 표현식이 존재한다.
  • 이항연산자의 적용 순서는 이진 트리로도 나타낼 수 있다. 따라서 Cnn + 1개의 단말 노드를 갖는 이진 순서 트리의 개수임을 알 수 있다.
Catalan number binary tree example.png
  • Cn동형이 아닌 모든 정 이진 트리 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 n개인 트리의 개수이다. ( 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)
  • Cnn+2각형을 n개의 삼각형으로 나누는 방법의 수이다. 아래 그림은 6각형을 4개의 삼각형으로 나누는 모든 방법을 나타낸 것으로 총 가지 이다.
Catalan-Hexagons-example.svg

성질[편집]

점화식과 생성함수[편집]

카탈란 수는 다음 점화식을 만족한다.

카탈란 수의 생성함수

로 정의할 때,

이 성립하고, 따라서

이 된다.

점근적 성질[편집]

점근적으로 카탈란 수는

로 근사할 수 있다.

증명[편집]

생성함수, 뉴턴 이항정리를 이용한 증명[편집]

카탈란 수의 생성함수 라고 정의할 때,

점화식에 의하여 이 성립하므로

가 성립한다.

이 때, 이므로 뉴턴의 이항정리를 이용하면

이다.

위 식을 다시 정리하면,

이고 여기에 로 치환을 해주면

이 되므로 이를 다시 에 대입하면

이 된다.

고로 이 되는데 이를 원래 생성함수였던 와 비교하면

이므로 이를 정리하면

이 됨을 알 수 있다.

역사[편집]

18세기에 몽골의 수학자 명안도(c. 1692-c. 1763)가 최초로 발견하였다.[1][2][3]

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

외부 링크[편집]

  1. Larcombe, P.J. (1999년 9월). “The 18th century Chinese discovery of the Catalan numbers” (PDF). 《Mathematical Spectrum》 (영어) 32 (1): 5–7. 
  2. 羅見今 (1988). “明安圖公式辨正”. 《內蒙古師大學報(自然科學版)》 (중국어) 1: 42-48. 
  3. 羅見今 (2010). “明安圖和他的冪級數展開式” (PDF). 《數學傳播》 (중국어) 34 (1): 65–73. 
  4. Catalan, Eugène Charles (1838). Note sur un Problème de combinaisons[[분류:프랑스어 표기를 포함한 문서|카탈랑 수]]” (PDF). 《Journal de Mathématiques Pures et Appliquées (1re série)》 (프랑스어) 3: 111-112.  URL과 위키 링크가 충돌함 (도움말)
  5. O’Connor, John J.; Edmund F. Robertson (2012년 9월). “Eugène Charles Catalan”. 《MacTutor History of Mathematics Archive》 (영어). 세인트앤드루스 대학교.