algorithm - バランス括弧

Question

次の問題のバックトラッキングソリューションで生成された結果の数である誰かが私に答えることができるかどうか疑問に思っていました:

n 対の括弧が与えられた場合、整形式の括弧のすべての組み合わせを生成する関数を作成します。

たとえば、n = 3 の場合、解セットは次のようになります。

"((()))"、"(()())"、"(())()"、"()(())"、"()()()"

stackoverflow に関連する投稿があります: Java でバランスの取れた括弧を生成する

有効な括弧の数を計算する前に生成できる数式があるかどうかは疑問です。例:
- f(n):
- f(1) = 1
- f(2) = 2
- f(3) = 5
など。

ありがとうございました。

Answer 1

正しく一致する n ペアの括弧を含む数式は、カタロニア語の数を介して計算できます。ウィキペディアからの関連リンクを引用します。

組み合わせ論には多くの数え上げ問題があり、その解はカタロニア語数で与えられます... Cn は長さ 2n の Dyck 語の数です。Dyck ワードは、n 個の X と n 個の Y から構成される文字列であり、文字列の最初のセグメントに X よりも多くの Y が含まれないようにします…記号 X を開き括弧として再解釈し、Y を閉じ括弧として再解釈し、Cn は式の数をカウントします。正しく一致する n ペアの括弧を含みます。

n 番目のカタロニア数は、次のように二項係数で直接与えられます。