卡特蘭數是個好東西
求法#
1.$f(n)=\sum_{i=0}^{n-1}f(i)\cdot f(n-1-i)$
2.$f(n)=\frac{(4n-2)\cdot f(n-1)}{n+1}$
3.$f(n)=\frac{C_{2n}^{n}}{n+1}$
應用#
-
n 個節點的二叉樹形態數
-
n 個元素的入棧、出棧的序列數
合法的出入棧序列：序列的任意前綴中，
入棧次數>=出棧次數 -
通過連接頂點把
(n+2)條邊的凸多邊形分割成三角形 -
幾乎所有卡特蘭數的問題都可以轉化為 “完成 n 步 k1 操作和 n 步 k2 操作，其中要求 k1 操作次數始終大於 k2 次數”
實際做題過程#
大佬們都是證明這道題是卡特蘭數。
而作為一個蒟蒻，我也就只能算出前三項（1,2,5），然後
“大膽而合理地外推”——hqx 大佬
"你應該在前面加一個像伽利略一樣"——hqx 大佬