カタルーニャ語の数字はどこに出現しますか?
-指定された数の括弧のペアを持つ psp の数
- 指定された数の葉を持つ二分木の数
-n * n 正方形の左下隅から右上隅までの、対角線に触れないパスの数
-n 角形を三角形に分割する数
数え方は?1) n 番目のカタロニア数の式:
2)
•長さ 2n の PSS を考えてみましょう
•明らかに左中括弧で始まります
•つまり、P = (A)B とします。ここで、A と B – psp も (A と B は空でも構いません)
•A の長さが 2k の場合、シーケンス A は Ck 通りに構成できます
•B の長さ = 2(n – k - 1) となり、B は Cn-k-1 通りに構成できます
•dp の式が表示されます。Cn = sum(Ck * Cn-k-1) for all k <;
使用した材料: