카탈랑 수는 놀라울 정도로 많은 조합론 문제에서 등장하는 수열입니다.
이 수열은 19세기에 살았던 벨기에의 수학자 카탈랑(Catalan)의 이름을 따서 명명되었지만, 실제로는 카탈랑보다 한 세기 앞서 살았던 오일러(Euler)도 이미 알고 있었습니다.
수열 처음 몇 개의 카탈랑 수 C_n(0번째부터 시작)은 다음과 같습니다:
1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ 1430,\ \ldo[…]
카탈랑 수는 수많은 조합론 문제에서 등장합니다. n번째 카탈랑 수는 다음과 같습니다:
n개의 여는 괄호와 n개의 닫는 괄호로 이루어진 올바른 괄호 문자열의 개수. n+1개의 리프를 가진 루트 있는 이진 트리의 개수(정점에는 번호가 매겨져 있지 않음). n+1개의 인수를 괄호로 완전히 묶는 방법의 수. 볼록 n+2각형의 삼각분할의 개수(즉, 서로 교차하지 않는 대각선으로 다각형을 삼각형들로 분할하는 방법의 수). 원 위의 2n개의 점을 서로 교차하지 않는 n개의 현으로 연결하는 방법의 수. n개의 내부 정점(즉, 자식이 적어도 하나 있는 정점)을 가진, 서로 동형이 아닌 완전 이진 트리의 개수. n \times n 크기의 정사각형 격자에서 점 (0,0)에서 점 (n,n)까지 가는 단조 경로 중 주대각선 위로 올라가지 않는 경로의 개수. 스택으로 정렬할 수 있는 길이 n인 순열의 개수(순열이 스택으로 정렬 가능할 필요충분조건은 a_k<a_i<a_j를 만족하는 인덱스 i<j<k가 존재하지 않는 것임을 보일 수 있음). n개의 원소로 이루어진 집합의 연속 분할(즉, 연속된 블록으로의 분할)의 개수. n개의 직사각형으로 계단 1 \ldots n을 덮는 방법의 수(여기서 계단이란 n개의 열로 이루어지고 i번째 열의 높이가 i인 도형을 뜻함). 계산 카탈랑 수에는 점화식과 일반항 공식, 두 가지 공식이 있습니다. 위에서 제시한 모든 문제가 동치라고 보므로, 공식을 증명할 때에는 증명하기 가장 쉬운 문제를 골라 사용하겠습니다.
점화식 C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}
점화식은 올바른 괄호 수열 문제로부터 쉽게 유도할 수 있습니다.
가장 왼쪽의 여는 괄호 l에는 특정한 닫는 괄호 r이 대응하며, 이 괄호는 식을 두 부분으로 나누고, 각 부분은 다시 올바른 괄호 문자열이 됩니다. 따라서 k = r-l-1이라고 두면, 임의의 고정된 r에 대해 정확히 C_k C_{n-1-k} 가지 방법이 있습니다. 이를 가능한 모든 k에 대해 합하면 C_n에 대한 점화식을 얻습니다.
해석적 공식 C_n = \frac{1}{n+1} C_{2n}^{n}
(여기서 C_n^k는 늘 그렇듯 이항 계수를 나타냅니다).
이 공식은 단조 경로 문제로부터 유도하는 것이 가장 간단합니다. 크기가 n \times n인 격자에서 단조 경로의 총 개수는 C_{2n}^{n}입니다. 이제 대각선을 넘어가는 단조 경로의 개수를 세어 봅시다. 그러한 경로 중 아무것이나 하나를 생각하고, 대각선보다 위에 있는 첫 번째 간선을 찾습니다. 이 간선 이후에 이어지는 경로 전체를 대각선에 대해 대칭 이동합니다. 그 결과 (n-1) \times (n+1) 격자에서의 단조 경로를 얻습니다. 그런데 다른 한편으로, (n-1) \times (n+1) 격자의 모든 단조 경로는 반드시 대각선을 넘어가므로, 이 경로는 n \times n 격자에서 대각선을 넘어가는 어떤 (그리고 유일한) 단조 경로로부터 바로 이러한 방식으로 얻어진 것입니다. (n-1) \times (n+1) 격자에서 단조 경로는 C_{2n}^{n-1}개 있습니다. 그 결과 다음 공식을 얻습니다:
C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C[…]