OMC181(C)

　一般に $2\times n$ の長方形で二人が左から右に行く道順の数を $a_n$ とします．すなわち求めたいのは $a_9$ です．
漸化式を使って解きましょう．

・二人が最初にどちらも右に移動するならば残りの道順は $a_{n-1}$ だけあります．
・小野寺さんが初手で下に行き， $1\leq k\leq n-1$ 回右に行った後で上に移動すると残りの道順は $a_{n-k-1}$ だけあります．( $a_0=1$ とします)
・芹沢さんが初手で上に行き， $1\leq k\leq n-1$ 回右に行った後で上に移動すると残りの道順は $a_{n-k-1}$ だけあります．
・小野寺さんが初手で下に行き， $n$ 回右に行った後で上に移動すると残りの道順は $1$ だけあります．
・芹沢さんが初手で上に行き， $n$ 回右に行った後で上に移動すると残りの道順は $1$ だけあります．

したがって次の漸化式が得られます． $$a_n=a_{n-1}+2(a_{n-2}+\cdots+a_0)+2$$ これと $n$ を $n+1$ とした式の差をとって次を得ます． $$a_{n+1}=2a_n+a_{n-1}　(n=2,3,...)$$ $a_1=3,a_2=7$ なのでこの漸化式を用いて $a_3=17,a_4=41,a_5=99,a_6=239,a_7=577,a_8=1393,a_9=\mathbf{3363}$ を得ます．