algorithm - 有効な括弧の数

Question

有効な括弧の数を調べなければなりません。括弧は 2 つのタイプ[] ,()です。の X と Y の数を使用して有効なシーケンスを構築する方法はいくつありますか[] ,()? この問題について([])は、無効な方法、つまり() can't hold []. 再帰よりも優れた解決策があると考えています。

For Example X=1 and Y=1
[]()
()[]
[()]

Answer 1

グループ化された自己閉じ丸括弧の任意の組み合わせと角括弧の特定の配置について、マルチセットの組み合わせを使用して配置の数を決定できます。

n + k - 1 choose k, where k is the smaller of the number of self-enclosed parenthetical groups and the total number of square brackets, and n is the larger of the two + 1.

角括弧の配置数は、n 番目のカタロニア数です。

括弧のグループを生成する 1 つの方法は、増加する数のグループを割り当て、(X - 割り当てられたグループの数) の各パーティションの個別の順列の数を計算し、parts-as-nth-Catalan の合計を掛けることです。例えば：

X = 4
Counts for each grouping:

1 group: Cat 3
2 groups: Cat 2 * 2 + 1 // partitions [2,0] * 2 and [1,1]
3 groups: 3 // partition [1,0,0] * 3
4 groups: 1 // partition [0,0,0,0]

パーティションを回避する方法をまだ考えていないので、学びたいと思っています。