本文使用 Zhihu On VSCode 創作並釋出
卡特蘭數經常會在演算法題中出現，是組合數學中的一個特別重要的數.
\begin{aligned}h(n)&=\sum\limits_{i=0}^{n-1}h(i)\cdot h(n-i-1)\\&=h(0)\cdot h(n-1)+h(1)\cdot h(n-2)+\cdots+h(n-1)\cdot h(0).\end{aligned}\\
則Catalan 數的解為h(n)=\frac{1}{n+1}C_{2n}^n .
令H(x)=h(0)+h(1)x+h(2)x^2+\cdots+h(n)x^n+\cdots ，則遞迴公式左邊就是H(x) 的n 次項系數，右邊是H^2(x) 的n-1 次項系數，所以我們有
H(x)=xH^2(x)+h(0)=xH^2(x)+1.
解得H(x)=\frac{1\pm\sqrt{1-4x}}{2x} .
在上一篇文章中，由廣義牛頓二項式定理得\sqrt{1-4x}=\sum\limits_{n=0}^{\infty}-\frac{1}{2n-1}C_{2n}^nx^n.
取H(x)=\frac{1-\sqrt{1-4x}}{2x} ，則x^n 系數為\frac{1}{2}\frac{1}{2n+1}C_{2n+2}^{n+1}=\frac{1}{n+1}C_{2n}^n .
這樣就得到Catalan 數h(n)=\frac{1}{n+1}C_{2n}^n .
在鄧俊輝【C++數據結構】「二叉搜尋樹」一節中，由一組共n 個互異節點組成的二叉搜尋樹，總共有\frac{1}{n+1}C_{2n}^n=\frac{(2n)!}{n!(n+1)!} 棵.
