Catalan 數
Catalan number$ C_n
漸化式
$ C_0:=1,$ C_{n+1}:=\frac{2(2n+1)}{n+2}C_n=\sum_{i=0}^n C_i C_{n-i}
一般項
$ C_n=\frac 1{n+1}\begin{pmatrix}2n \\ n\end{pmatrix}=\frac{(2n)!}{(n+1)!n!}=\begin{pmatrix}2n \\ n\end{pmatrix}-\begin{pmatrix}2n \\ n-1\end{pmatrix}
$ C_n=\frac 1{2\pi}\int_0^4 x^n\sqrt{\frac{4-x}x}dx=\frac 2\pi 4^n\int_{-1}^1 x^{2n}\sqrt{1-x^2}dx
$ C(x):=\sum_{n=0}^\infty C_n x^n
$ C(x)=1+x C(x)^2
$ C(x)=\frac{1-\sqrt{1-4x}}{2x}=-\frac 1{2x}\sum_{n=1}^\infty\begin{pmatrix}\frac 1 2 \\ n\end{pmatrix}(-4x)^n=\sum_{n=0}^\infty\frac 1{n+1}\begin{pmatrix}2n \\ n\end{pmatrix}x^n
近似
$ C_n\sim\frac{4^n}{n^{\frac 3 2}\sqrt\pi}