引言
這裡推導Catalan number。
模型
這裡可以用一個例子介紹Catalan number。譬如，對一個序列$x_n$，下一個$x_{n+1}$取值有兩種可能：如果$x_n > 0$，那麼$x_{n+1}$可以取$x_n \pm 1$，但如果$x_n = 0$，則$x_{n+1}$必須取$x_n + 1$。這個序列從$x_0 = 0$出發，並最終回到$x_n = 0$原點。如此一來，可能的路徑共有多少條。
不難發現這個$n$必須為偶數，為方便起見，用$2n$取代原先的下標$n$。這個數字是$C_n$，也就是Catalan number，下面將推出這個數的大小。
推導
不難看出，若不考慮限制條件，即允許$x_{2n}$在中間過程中穿過原點成為負數，那麼可能的路徑共有$\binom{2n}{n}$條。
現在考慮另一種情況，在第$2k$步回到原點$x_{2k} = 0$，並在此前的過程中從未穿越原點變成負數。這時候有兩種可能：
第一是繼續向上，在以後的變化中可能穿過原點，也就是說需要在以後的變化中扣除這些路徑。
第二是向下，這意味著穿過了原點，自此以後所有的變化需要從總路徑中扣除，扣除的路徑數為$2C_k\binom{2n-2k}{n-k}/2 = C_k\binom{2n-2k}{n-k}$。前面乘以二是因為考慮與之對稱的過程，即$x_{2n}$恆不為正的情況；後面除以二表示是未來路徑的一半，即選擇向下的情況。
綜上，可以寫出Catalan number的表達式為
$$
2C_n = B_n - \sum_{k=1}^{n-1}C_kB_{n-k}
$$
左邊係數$2$表示考慮與之對稱的過程，其中
$$
B_n = \binom{2n}{n} = \frac{(2n)!}{[(n)!]^2} = \frac{(2n)!!(2n-1)!!}{[(n)!]^2} = \frac{2^n(2n-1)!!}{n!}
$$
或者將等式改寫成
$$
C_n = 2B_n - \sum_{k=0}^{n}C_kB_{n-k}
$$
這裡考慮generating function
$$
c(x) = \sum_{n = 0}^\infty C_nx^n
$$
以及
$$
b(x) = \sum_{n = 0}^\infty B_nx^n = \frac{1}{\sqrt{1-4x}}
$$
對比$x^n$的每一項係數，可以得到
$$
c(x) = 2b(x) - c(x)b(x)
$$
解出
$$
c(x) = \frac{2b(x)}{1 + b(x)} = \frac{1 - \sqrt{1 - 4x}}{2x}
$$
將$c(x)$展開
$$
\begin{equation}
\begin{aligned}
c(x) =& \frac{1}{2x}\left[ 1 - \sum_{n = 0}^\infty \binom{1/2}{n}(-4x)^n \right] \\
=& \frac{1}{2x}\left[ 1 + \sum_{n = 0}^\infty \binom{2n}{n}\frac{1}{2n - 1}x^n \right] \\
=& \frac{1}{2}\sum_{n = 1}^\infty \binom{2n}{n}\frac{1}{2n - 1}x^{n-1} \\
=& \frac{1}{2}\sum_{n = 0}^\infty \binom{2(n+1)}{n + 1}\frac{1}{2n + 1}x^{n} \\
=& \sum_{n = 0}^\infty \frac{2(n+1)(2n+1)}{2(n+1)^2}\binom{2n}{n}\frac{1}{2n + 1}x^{n} \\
=& \sum_{n = 0}^\infty \frac{1}{n + 1}\binom{2n}{n}x^{n}
\end{aligned}
\end{equation}
$$
因此
$$
C_n = \frac{1}{n + 1}\binom{2n}{n}
$$
後記
Catalan number廣泛出現在統計物理當中，譬如自旋玻璃和隨機矩陣。