Catalan Number: C_n

Catalan Number, 카탈란 수, 카탈란

정의

Catalan number:

$$C_n=\frac{1}{\{}n+1\}(\genfrac{}{}{0ex}{}{\{}{2})n\}\{n\}=\frac{\{}{(}2n)!\}\{(n+1)!n!\}$$

C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42.

응용 (모두 C_n 개)

• balanced parenthesis n 쌍
• binary tree with n internal nodes
• Dyck path length 2n (only up-right moves)
• triangulation of convex (n+2)-gon
• stack-permutations of 1..n

점화식

$$C_{\{}n+1\}=\sum _{\{}i=0{\}}^{\{}n\}{C}_i{C}_{\{}n-i\}$$

또는 $C_n=\frac{\{}{2}(2n-1)\}\{n+1\}{C}_{\{}n-1\}$.

참고

• 조합론
• Pascal Triangle