興味深い組み合わせの問題があり、ちょっと立ち往生しています
方程式 x の '()' の数を返す関数 p(xn) を定義しましょう x は x1 + x2 + x3 ... xn の形式でのみ定義できます この関数は n >=2 に対して定義されます
例:
P(x2) = (x1 + x2) = 1
p(x3) = ((x1 + x2) + x3) および (x1 + (x2 + x3))
p(x4) =
((x1 + x2) + (x3 + x4))
(((x1 + x2) + x3) + x4)
((x1 + (x2 + x3)) + x4)
(x1 + ((x2 + x3) + x4))
(x1 + (x2 + (x3 + x4)))
(x1 + (x2 + x3) + x4) は有効な例ではありません。各 + に対して 1 つの () が必要です。
今、組み合わせの数を決定する P の式を考え出そうとしていますが、前の項に依存する固定式または再帰的定義があるかどうかはわかりません。式を解くのを手伝ってくれませんか？
基本的に、ノードが合計であり、葉が x 1から x nである一意のバイナリ表現ツリーの数を数えようとしています。この数を P(n) としましょう。
n-1 個の合計のいずれかをルート ノードとして選択できます。k番目の合計を選択しましょう。ルートの左側に k 個の変数があるため、左側のサブツリーを P(k) 通りに編成できます。右側に nk 個の変数があるため、右側のサブツリーは P(nk) 通りに編成できます。したがって、全体として、ツリーを P(k)P(nk) のさまざまな方法で編成できます。
k は 1 から n-1 まで自由に選択できるため、n 葉の式ツリーを構成できる総数は次のとおりです。
P(n) = P(1)P(n-1) + P(2)P(n-2) + ··· + P(n-2)P(2) + P(n-1)P(1)
コメントで @DSM が指摘したように、この再帰関係はカタロニア語の数字を生成します。閉じた形式の解がありますが、再帰式から導き出すのは少し難しいです。ウィキペディアのカタロニア語の記事で、数式のいくつかの証明を見つけることができます。解決策は次のとおりです。
P(n) = C(2n,n)/(n+1) where C(n,k) = n! / (k!(n-k)!)