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