【📄笔记📄】排列组合 - 校内/校外

lancas - 排列与组合 一看就通精讲版 - 校内/校外

课上视频： bilibili - 【漫士】这是你学明白组合数学最好的机会

上半区问题路线计算推导过程（卡特兰数列）：

$C_{2n}^{n} - C_{2n}^{n~-~1}$

$=\frac{(2n)!}{n! ~*~ n!} - \frac{(2n)!}{((2n)~-~n~+~1)! * (n~-~1)!}$

$=\frac{(2n)!}{n! ~*~ n!} - \frac{(2n)!}{(n~+~1)! * (n~-~1)!}$

$=\frac{(2n)!}{n! ~*~ n!} - \frac{(2n)!}{n! ~*~ n!} * \frac{n}{n ~+~ 1}$

$=\frac{(2n)!}{n! ~*~ n!} * \frac{n+1}{n ~+~ 1} - \frac{(2n)!}{n! ~*~ n!} * \frac{n}{n ~+~ 1}$

$=\frac{(2n)!}{n! ~*~ n!} * (\frac{n+1}{n ~+~ 1}~-~\frac{n}{n~+~1})$

$=\frac{(2n)!}{n! ~*~ n!} * \frac{1}{n~+~1}$

$∵C_{2n}^{n} = \frac{(2n)!}{n! ~*~ n!}$

$∴C_{2n}^{n} - C_{2n}^{n~-~1} = C_{2n}^{n} * \frac{1}{n + 1}=\frac{C_{2n}^{n}}{n~+~1}$

$∵$ 我没写的上文

$∴$ 卡特兰数列的第 $n$ 项（ $f(n)$ ） = $\frac{C_{2n}^{n}}{n~+~1}$

---

$∵f(n) = \frac{C_{2n}^{n}}{n~+~1}$

$∴f(n)=\frac{(2n)!}{n!~*~n!}~ *~ \frac{1}{n ~+~ 1}$

$= \frac{(2n-2)! * (2n-1) * 2n}{n*(n-1)!*n*(n-1)!} * \frac{1}{n ~+~ 1}$

$= \frac{(2n-2)! * (2n-1) * 2n}{n*(n-1)!*n*(n-1)! * (n+1)}$

-——拆分分数——-

$= \frac{(2n-2)!}{(n-1)!*n*(n-1)!} ~*~ \frac{(2n-1) * 2n}{n * (n+1)}$

$= \frac{(2n-2)!}{(n-1)!*(n-1)!} ~*~ \frac{1}{n} ~*~ \frac{(2n-1) * 2}{n+1}$

---

$∵f(n) = \frac{C_{2n}^{n}}{n~+~1}$

$∴f(n)=\frac{(2n)!}{n!~*~n!}~ *~ \frac{1}{n ~+~ 1}$

$∴f(n~-~1)=\frac{2(n~-~1)!}{(n~-~1)!(n~-~1)!} * \frac{1}{n}$ _（换元）

---

将

$f(n~-~1)=\frac{2(n~-~1)!}{(n~-~1)!(n~-~1)!} * \frac{1}{n}$

代入

$f(n) = \frac{(2n-2)!}{(n-1)!*(n-1)!} ~*~ \frac{1}{n} ~*~ \frac{(2n-1) * 2}{n+1}$

得

$f(n) = f(n-1) * \frac{(2n-1) * 2}{n+1}$

$= f(n-1) * \frac{4n-2}{n+1}$

综上，得出

$f(n) = f(n-1) * \frac{4n-2}{n+1}$

---

四个卡特兰递推式：

1. $f[n]=f[0]~∗~f[n~−~1]~+~f[1]~∗~f[n~−~2]~+~...~+~f[n~−~1]~∗~f[0]$ $(n≥2)$

2. $h[n]=h[n~−~1]~∗~(4~∗~n~−~2)~/~(n~+~1)$ ^{<—— 既上文推导出的}

3. $h[n]=C[2n,n]~/~(n~+~1)(n=0,1,2,...)$

4. $h[n]=C[2n,n]−C[2n,n−1](n=0,1,2,...)$