2022/12/10_Catalan
szhqwq
·
·
算法·理论
Catalan
1. 递归定义
$$f_n = f_0 \cdot f_{n - 1} + f_1 \cdot f_{n - 2} + ... + f_{n - 1} \cdot f_0 = \sum\limits_{k=1}^nf_{k - 1} \cdot f_{n - k}$$
2. 递推关系
$$f_n = \frac{4n - 2}{n + 1} \cdot f_{n - 1}$$
3. 通项公式
$$f_n = \frac{C_{2n}^n}{n + 1}$$
4. $$f_n = C_{2n}^n - C_{2n}^{n - 1}$$
### 推导：
$$
\begin{aligned}
f_n &= C_{2n}^n - C_{2n}^{n - 1} \\
&= \frac{(2n)!}{n! \cdot n!} - \frac{(2n)!}{(n + 1) \cdot (n - 1)} \\
&= \frac{1}{n + 1} \cdot (\frac{(2n)! \cdot (n + 1)}{n! \cdot n!} - \frac{(2n)!}{n! \cdot (n - 1)!}) \\
&= \frac{1}{n + 1} \cdot (\frac{(2n)! \cdot (n + 1)}{n! \cdot n!} - \frac{(2n)! \cdot n}{n! \cdot n!}) \\
&= \frac{1}{n + 1} \cdot \frac{(2n)!}{n! \cdot n!} \\
&= \frac{\frac{(2n)!}{n! \cdot n!}}{n + 1} \\
&= \frac{C_{n}^{2n}}{n + 1} \\
\end{aligned}
$$
由此，得证3.
$$
\begin{aligned}
f_n &= \frac{4n-2}{n + 1} \cdot f_{n - 1} \\
\frac{1}{n + 1} \cdot C_{2n}^n &= \frac{4n - 2}{n + 1} \cdot \frac{1}{n} \cdot C_{2n - 2}^{n - 1} \\
C_{2n}^n &= (4n - 2) \cdot \frac{1}{n} \cdot C_{2n - 2}^{n - 1} \\
\frac{(2n)!}{n! \cdot n!} &= \frac{2n(2n - 1)}{n} \cdot \frac{(2n - 2)! \cdot n}{(n - 1)! \cdot (n - 1)! \cdot n} = \frac{(2n)!}{n! \cdot n!} \\
\end{aligned}
$$
由此，得证4.