카탈란 수(Catalan number)에 대하여
1. 카탈란 수의 정의 및 응용$n$번째 카탈란 수(Catalan number) $C_n$이란 아래의 점화식을 만족하는 수열의 $n$번째 항을 말한다. \[ C_0 = 1, \quad C_n = \sum_{i=0}^{n} C_i C_{n-i}, \ n \geq 0. \tag{1.1} \]이 수열의 첫 10개의 항을 나열하면 다음과 같다. ($C_0$부터 $C_9$까지) \[ 1,\ 1,\ 2,\ 5,\ 14,\ 43,\ 132,\ 429,\ 1430,\ 4862,\ \ldots \] 카탈란 수는 조합론(combinatorics)에서 빈번하게 등장하는 수 중의 하나로, 아래와 같은 문제들의 해답이 모두 $n$번째 카탈란 수 $C_n$으로 주어진다. 먼저 $C_4 = 14$라는 사실을 기억하자. (더 많은 ..