5.2.4  카탈란 수열의 다양한 의미
          (Catalan Numbers and Its Meanings)

 
카탈란(E.C.Catalan)은 일반항이 다음의 공식으로 주어지는 수열을 생각하였다.

이것을 카탈란 수라 하고, 처음 몇 개의 항을 나열하면 다음과 같다.  

  1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, . . .

카탈란 수는 조합론 분야에서 자주 다루어지고 있는 수열로 그 의미가 다양하게 해석되고 있다. 여기서는 그 중 몇가지를 소개하기로 한다.

각형을   개의 삼각형으로 분할하는 방법의 수. (예제)
일렬로 배열된 개의 숫자의 곱에서 괄호를 삽입하여 곱하는 방법의 수. (예제)
두 사람에 대한 투표에서 A 와 B가 최종적으로는 똑같이 표씩 얻었지만, A 가 B 에게 지지않고 투표결과가 진행되는 방법의 수. (예제)
정수들의 격자점을 갖는 평면에서 점 에서 점 에 이르는 경로 중 대각선의 위에 있는 점들은 지나지 않는 경로의 수. (예제)
개의 잎(leaves) 을 갖는 이진트리( binary tree) 의 개수. (예제)
개의 선분(edge) 을 갖는 근트리(rooted tree) 의 개수. (예제)

카탈란 수의 의미는 다양하게 해석되지만 각 경우는 같은 수의 원소를 나타내기 때문에 각 해석 간에는 1-1 대응이 존재한다. 다음의 애니메이션은 그러한 1-1 대응관계 중 하나를 정의하는 방법을 보여준다.

  카탈란 수열의 의미 사이의 1-1 대응 관계.