Codeforces #404 D. Anton and School - 2
http://codeforces.com/contest/785/problem/D
解法
一番右にある'('の位置を固定したとき、条件を満たす括弧列がいくつあるかを数える。
固定した左側に'('が4個、右側に')'が5個ある。
条件を満たす括弧列を作るには、左側の領域から'('を k 個取ったら、右側の領域から')'を k+1 個とればいい。
つまり、パターン数は以下の通り。
\[ \binom{4}{0}\binom{5}{1}+\binom{4}{1}\binom{5}{2}+\binom{4}{2}\binom{5}{3}+\binom{4}{3}\binom{5}{4}+\binom{4}{4}\binom{5}{5} \]
一般に、左側の領域に'('が L 個、右側の領域に')'が R 個ある場合、パターン数は以下の式となる。
\[ \sum_{k=0}^{\infty} \binom{L}{k}\binom{R}{k+1} \]
細かいことは気にせず無限大まで飛ばした。\(\binom{n}{r}=\binom{n}{n-r}\) であることを使うと以下の式に変形できることが分かる。
\[ \sum_{k=0}^{\infty} \binom{L}{k}\binom{R}{R - k - 1} \]
二項係数の下側の値、ここでは \(k\) と \(R - k - 1\) であるが、その和は 一定になっていて \(R - 1\) である。つまり、これは畳み込みになっている。
多項式 \( (1+x)^L (1+x)^R \) の \(x^{R-1}\) の係数がちょうどの畳み込みの値と一致するはずなので、
\[ \sum_{k=0}^{\infty} \binom{L}{k}\binom{R}{R - k - 1}=\binom{L+R}{R - 1} \]
である。よってこの問題を解くことができた。