　以降は，一つ目の条件を満たすもの，つまり，`〇` と `〇` の間に `()` という連続文字列がないものだけを文字列と呼ぶことにする．

　一般に，`(` と `)` と `〇` がそれぞれ $n$ 個ずつある場合を考える．$xy$ 平面上に $A(0,0)$, $B(0,1)$, $X(n,n)$, $Y(n,n+1)$ をとる．
$x$ 軸正方向への長さ $1$ の移動を 「$\to$」 ，$y$ 軸正方向への長さ $1$ の移動を 「 $\uparrow$ 」で表すこととする．任意の文字列に関して，
- `〇` と `)` だけを抜き出して左から順に `〇` を $\to$，`)` を $\uparrow$ に対応させて点 $A$ から繋げていったものを A-path
- `〇` と `(` だけを抜き出して左から順に `〇` を $\to$，`(` を $\uparrow$ に対応させて点 $B$ から繋げていったものを B-path

と呼ぶことにする．例えば $n=6$ のとき `〇(〇(〇〇)((〇)))((〇))` を表す A-path,B-path は下図のようになる．

![figure 1](\/images\/aP0oSxGwD00sXbK63lqLnNxme7YNuRgup8lFsS9Q)

　このように任意の文字列を矢印に変換して A-path を作ると，`〇` と `)` は $n$ 個ずつあるので始点を点 $A$ とすると終点は必ず点 $X$ になる．同様に B-path は始点を点 $B$ とすると，終点は点 $Y$ になる．逆に任意の A-path,B-path の組から一意に $3n$ 個の文字列を復元できる．（これは部分文字列 `()` が禁止されていることから従う．すなわち，同じ $x$ 座標で A-path と B-path それぞれに $\uparrow$ があるときは `)` を先に A-path の $\uparrow$ の数だけ並べ，その後に `(`を並べる．）

---

**補題．** 文字列が問の $2$ つの条件を満たすための必要十分条件は，A-path と B-path が共有点をもたないことである．

**証明．**  
【必要性】文字列は一つ目の条件を満たしており，括弧だけ見ると正しい括弧列なので任意の $x=i　(i=1,\cdots,n)$ についてその時点までに出てきた `)` の総数は $x=i-1$ までに出てきた `(` の総数以下である．また $x=0$ のとき A-path は $\uparrow$ から始まることはない．よって交差することも接することもない．

【十分性】もし交差することも接することもなければ，上と同様の議論で正しい括弧列になるので一つ目の条件を満たす．また，`〇` と `〇` の間に `()` という連続部分列がないので二つ目の条件も満たす．

---

　よって，点 $A$ から 点 $X$ まで $\to,\uparrow$ だけで行き，点 $B$ から 点 $Y$ まで $\to,\uparrow$ だけで行く組の総数 $({}\_{2n}\mathrm{C}\_{n})^2$ から，A-path と B-path が交差または接する組の総数を引けばよい．

---

**補題．**A-path と B-path の組で，交差または接するものの総数は次に等しい．
$$\dbinom{2n+1}{n}\dbinom{2n-1}{n}$$

**証明．**  
　$\to$ と $\uparrow$ を繋げて出来る矢印列のことを単に path と呼ぶことにする．
A-path と B-path が初めて接した点以降の path を A-path と B-path で交換した path を考える．
すると始点が点 $A$ で終点が点 $Y$ となる pathと，始点が点 $B$ で終点が点 $X$ となる path が新しく出来る．図 $2$ 参照．
逆に任意の点 $A$ と点 $Y$ を結ぶ path と，点 $B$ と点$X$ を結ぶ path は必ず交差するか接し，最初に接した点で以降の path を交換すると，途中で交差したり接する A-path と B-path になる．ここで  
- 点 $A$ と点 $Y$ を結ぶ path の総数は ${}\_{2n+1}\mathrm{C}\_{n}$ 個．  
- 点 $B$ と点 $X$ を結ぶ path の総数は ${}\_{2n-1}\mathrm{C}\_{n}$ 個．
  
なので求める総数は補題の通りになる．

![figure 1](\/images\/uyUVHVNPOKe391M3JHQIL8lVPJuPgfn87ak3OiBH)

---

よって一般解は
$$\dbinom{2n}{n}^2-\dbinom{2n+1}{n}\dbinom{2n-1}{n}=\dfrac{1}{2n+2}\dbinom{2n}{n}^2$$
個である．ゆえに求める総数は $n=10$ を代入して
$$\dfrac{1}{22}\dbinom{20}{10}^2=\textbf{1551580888}$$
公式解説
https://onlinemathcontest.com/contests/omce005/editorial/3208
　 `(` `o` `)` が $n$ 個ずつある場合を考えます.   
`o` と `()` を変換することで, 数えるべき対象は `(`, `)` を $2n$ 個ずつ用いてできる正しい括弧列で, `()` を丁度 $n$ 個含むものです.  

　一般に, `(` `)` を $N$ 個ずつ用いた正しい括弧列で `()` を丁度 $K$ 個もつものの個数は [ナラヤナ数](https:\/\/en.wikipedia.org\/wiki\/Narayana_number ) として知られている数で, その値は $$\frac{1}{N}\binom{N}{K}\binom{N}{K-1}$$
です.  

　よって今回の設定のもと, 求める答えは $$\frac{1}{2n}\binom{2n}{n}\binom{2n}{n-1}$$
です.
ナラヤナ数を用いる解法
https://onlinemathcontest.com/contests/omce005/editorial/3208/547
　等しい個数の `(` と `)` からなる文字列であって，連続する部分文字列 `()` をひとつ選んで消すことを繰り返すことで空文字列にできる文字列を**正しい括弧列**とよび，このとき同時に消した `(` と `)` を**対応する括弧**と呼ぶことにします（これはどの正しい括弧列に対しても一意に定まります）．\
　`(` と `)` と `〇` を $10$ 個ずつ並べて $30$ 文字の文字列 $S$ を作る方法のうち，
- $S$ から `〇` をすべて消去すると正しい括弧列 $S^\prime$ が得られる．
- $S^\prime$ のすべての対応する括弧は，$S$ において間に少なくとも $1$ つの `〇` を含んでいる．

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

<details><summary>具体例<\/summary>

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

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

- `)))))(((((〇〇〇〇〇〇〇〇〇〇)))))(((((`　
- `(〇(〇))(〇)(〇)(〇)()(〇〇)(〇)(〇)(〇)`
<\/details>