프로그래밍 끄적끄적

카탈랑 수(Catalan number)는 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, ... 로 이루어진 수열로, 조합론에서 빈번하게 나타나는 수열이다. 점화식으로 나타내면 다음과 같다. $$ C_{0} = 1, \, C_{n+1} = \sum_{i=0}^{n}{C_{i}C_{n-i}} \; (n \geq 1) $$ 이 점화식을 따르는 대표적인 예제로, 'n개의 괄호 쌍으로 나타낼 수 있는 올바른 괄호 조합 구하기'가 있다. (이때 올바른 괄호란, '('의 개수가 항상 많거나 같다가 마지막엔 '('의 개수와 ')'의 개수가 같은 식을 말한다.) 점화식을 위해 C(0) = 1이라고 설정한다. 1개의 괄호 쌍 1개의 괄호 쌍은 '()'으로..