カタラン数は素晴らしいものです
求法#
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 エリート