OMCE005(D)

点数: 700

Writer: umezo

　等しい個数の ( と ) からなる文字列であって，連続する部分文字列 () をひとつ選んで消すことを繰り返すことで空文字列にできる文字列を正しい括弧列とよび，このとき同時に消した ( と ) を対応する括弧と呼ぶことにします（これはどの正しい括弧列に対しても一意に定まります）．
　( と ) と 〇 を $10$ 個ずつ並べて $30$ 文字の文字列 $S$ を作る方法のうち，

$S$ から 〇 をすべて消去すると正しい括弧列 $S^\prime$ が得られる．
$S^\prime$ のすべての対応する括弧は， $S$ において間に少なくとも $1$ つの 〇 を含んでいる．

の両方の条件を満たす並べ方の総数は全部で何個ありますか？

具体例

　以下は条件をみたす文字列です．一つの対応する括弧が複数の 〇 を含んでいてもよく，また 〇 は必ずしも括弧の中に含まれている必要はありません．

((〇)(〇)〇〇)((〇)(〇))((〇))(〇)(〇〇)　
〇((〇))((〇))〇〇(〇(((〇))〇)((〇)))〇

　また，以下は条件をみたさない文字列です．一つ目は 〇 を消去した時に正しい括弧列とならず，二つ目には 〇 を間に含まない対応する括弧が存在します．

)))))(((((〇〇〇〇〇〇〇〇〇〇)))))(((((　
(〇(〇))(〇)(〇)(〇)()(〇〇)(〇)(〇)(〇)

解答を提出するにはログインしてください.