카탈란 수

다음 점화식

구문 분석 실패 (구문 오류): {\displaystyle C_0=1, C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}\text{ for $n\ge 1$}}

으로 정의되는 수열의 성분을 카탈란 수(Catalan number)라고 한다. $n$번째 카탈란 수는 이항계수를 이용해 다음과 같이 나타낼 수 있다.

$C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}$

카탈란 수의 일부를 작은 순서대로 나타낸 결과는 다음과 같다.

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304 (oeis:A000108)

성질

$C_{n}$이 홀수일 필요충분조건은 $n$이 메르센 수인 것이다. 또한, 소수인 카탈란 수는 2와 5뿐이다.

한켈 행렬과 카탈란 수

$(i,j)$-성분이 $C_{t+i+j-2}$인 한켈 행렬

$M_{k}^{t}={\begin{bmatrix}C_{t}&C_{t+1}&\cdots &C_{t+k-1}\\C_{t+1}&C_{t+2}&\cdots &C_{t+k}\\\vdots &\vdots &\ddots &\vdots \\C_{t+k-1}&C_{t+k}&\cdots &C_{t+2k-2}\end{bmatrix}}$

에 대해 다음 식이 성립한다.

• $\det M_{k}^{0}={\begin{vmatrix}C_{0}&C_{1}&\cdots &C_{k-1}\\C_{1}&C_{2}&\cdots &C_{k}\\\vdots &\vdots &\ddots &\vdots \\C_{k-1}&C_{k}&\cdots &C_{2k-2}\end{vmatrix}}=1$
• $\det M_{k}^{1}={\begin{vmatrix}C_{1}&C_{2}&\cdots &C_{k}\\C_{2}&C_{3}&\cdots &C_{k+1}\\\vdots &\vdots &\ddots &\vdots \\C_{k}&C_{k+1}&\cdots &C_{2k-1}\end{vmatrix}}=1$
• $\det M_{k}^{2}={\begin{vmatrix}C_{2}&C_{3}&\cdots &C_{k+1}\\C_{3}&C_{4}&\cdots &C_{k+2}\\\vdots &\vdots &\ddots &\vdots \\C_{k+1}&C_{k+2}&\cdots &C_{2k}\end{vmatrix}}=k+1$
• $\det M_{k}^{3}={\begin{vmatrix}C_{3}&C_{4}&\cdots &C_{k+2}\\C_{4}&C_{5}&\cdots &C_{k+3}\\\vdots &\vdots &\ddots &\vdots \\C_{k+2}&C_{k+3}&\cdots &C_{2k+1}\end{vmatrix}}={\frac {(k+1)(k+2)(2k+3)}{6}}$