Catalan Number

Catalan's Number
 
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...



구하는 법 

C(n) = (2nCn) / (n+1) = (2n)! / ((n+1)! * n!)
or
C[0]=1, C[n+1] = C[0]C[n] + C[1]C[n-1] + ... + C[n]C[0]


 
Catalan 수가 적용되는 예

n개의 노드로 만들 수 있는 tree 개수
n+2 측면으로 된 다각형을 n 삼각형들로 자를 수 있는 방법의 수
한 번에 두 개씩, 괄호 안에 곱해지며 늘여지는 수들을 놓는 방법의 수
n +1로 남겨지는 planar binary trees의 수
길이 2n을 통해서 n-by-n로 향하는데 주요한 대각선을 넘지 않는 경로의 수
stack-sort
행렬곱
등등..



관련된 논문

invalid-file

카탈란 수가 적용되는 예가 무지 많다..
Super Catalan도 있던데.. 그건 뭐지..