Catalan Number(카탈랑 수)

What is Catalan Number?

A n개, B n개를 나열한 순열의 A의 개수와 B의 개수를 한 곳으로부터 세어갈때 항상 A의 개수가 B의 개수보다 크거나 같은 배열의 개수를 뜻한다.

일반적으로는 $C_n$ 으로 표현한다.

Main Idea

항상 A의 개수가 B의 개수보다 크거나 같은 배열(구해야 하는 값)을 Good array라 한다.
전체 경우의 수에서 Bad array가 나오는 경우의 수를 빼주면 Good Array의 개수를 구할 수 있다.

Proof

1. Bad Array를 임의로 하나 써준다. ex)AABBBA
2. A보다 B가 많아지는 지점을 기준으로 왼쪽의 배열을 반전시킨다. 
AABBB|A -> BBAAA|A
3. 반전 후 만들어진 순열은 항상 A가 n+1개, B가 n-1개로 이루어진다.
4. 3의 순열은 Bad Array를 반전시킨 값이므로 반전 후 만들어진 순열의 개수=Bad Array 개수다.
\begin{align*}
C_n = &\frac{2n!}{n! \cdot n!} - \frac{2n!}{(n+1)! \cdot (n-1)!}\\
=&\frac{2n!}{n! \cdot n!} - \frac{n}{n+1} \cdot \frac{2n!}{n!\cdot n}\\
=&\frac{1}{n+1} \cdot \frac{2n!}{n! \cdot n!}\\
=&\frac{1}{n+1} \cdot _{2n}\mathrm{C}_{n}\\
\end{align*}

 

Use

1. 정n다각형에 대각선을 그어 삼각형을 분할하는 경우의 수
2. 왼쪽 괄호 n개와 오른쪽 괄호n개를 나열할 때 괄호가 서로 맞아떨어지는 배열의 경우의 수
3. n+1개의 항에 괄호를 씌우는 모든 경우의 수
4. 대각선 위를 침범하지 않고 A에서 B로 가는 최단 경로의 개수