#정의

올바른 괄호 문자열(올바른 괄호 문자열)의 개수를 세어 봅시다. 직관적으로 무엇인지 이해할 수 있지만, 형식적으로는 다음과 같이 정의됩니다: - 빈 문자열은 올바른 괄호 문자열입니다 - $A$가 올바른 괄호 문자열이면, $(A)$도 올바른 괄호 문자열입니다 - $A$와 $B$가 올바른 괄호 문자열이면, $AB$도 올바른 괄호 문자열입니다.

이제 괄호가 $2n$개인 올바른 괄호 문자열의 개수를 세어 봅시다. 이를 카탈랑 수라고 하며 $C_n$으로 표기합니다.

#공식

여는 괄호와 닫는 괄호의 개수 차이가 처음으로 0이 되는 첫 위치를 생각하고, 그 위치까지의 올바른 괄호 문자열 부분을 $(A)$, 그 이후의 부분을 $B$라고 표기합시다. $A$와 $B$가 더 작은 크기의 올바른 괄호 문자열(비어 있을 수도 있음)이라는 것은 자명합니다.

이제 $A$의 크기를 전부 살펴보면 $C_n$을 쉽게 계산할 수 있습니다.

$C_0=1$

$C_n=C_0C_{n-1}+C_1C_{n-2}+\ldots+C_{n-1}C_0$

#대안 공식

$C_n = \frac{1}{n+1}{2 n \choose n} = \frac{1}{2 n+1}{2 n+1 \choose n} = \binom{2 n}{n} - \binom{2 n}{n-1}$

다시 말해, 카탈랑 수 $C_n$은 파스칼 삼각형의 같은 행에 있는 중앙 이항 계수와 그 옆에 이웃한 이항 계수의 차와 같습니다.