一筆書きできる括弧の組
一昨年，昨年に続き，とある研究室合宿でのプログラミングコンテストで出題するために作成した問題を（一部編集して）公開します． 解答は後日ここで発表します．
n (≧1) を自然数とする． s，tはそれぞれ 2n+1 文字，2n 文字からなる文字列で以下の全ての条件を満たしている．
ここで，x[i] は文字列 x の i 番めの文字を表すものとする．たとえば，n=2 のとき， <s, t> = <"
- s の中の文字は，ハイフン '
-'，左括弧 '(' ，右括弧 ')' のいずれかであり，ハイフンはちょうど1回だけ現れる．- t の中の文字は，左括弧 '
('，右括弧 ')' のいずれかである．- s，t の中のどの括弧も正しく対応づけられている．ハイフンの位置は問題にしない．
- 文字 s[i] (1≦i≦2n) がハイフンであるとき，文字 t[i] から始めて，以下の手順で移動を繰り返すことにより，s と t の中の全ての括弧を 1 回ずつ辿ることができる．
- その文字が s の中の括弧のとき，対応する括弧 s[j] を辿り，t[j] に移動する．
- その文字が t の中の括弧のとき，対応する括弧 t[j] を辿り，s[j] に移動する．
(()-)", "()()"> や <s, t> = <"()(-)", "(())"> は条件を満たすが， <s, t> = <"(-())", "()()"> や <s, t> = <"(()-)", "(())"> は条件を満たさない． 与えられた自然数 n (≦10) に対し， 条件を満たす <s, t> の組の数を出力するプログラムを書け．
