　一般に  $2\times n$ の区画の場合を考える. 各区画を頂点, 各境界線を辺とし，境界線で隣接した $2$ 区画の間に辺を張った $2n$ 頂点 $3n-2$ 辺のグラフを考える(図1). 求めるものは, このグラフから $n-1$ 辺を取り除いたときにグラフが木となるような方法の総数である.\
　ここで, 条件を満たす木のうち，右端の $2$ 頂点の間に辺が存在するものをパターン $A$, 存在しないものをパターン $B$ と呼ぶ(図2). また，パターン $A,B$ がそれぞれ $a_n,b_n$ 個あるとする. 左側からグラフを作っていくことを考える. \
　$2\times n$ のパターン $A$ の木の右側に $2$ つの頂点と $3$ つの辺を貼り，辺を除くことで条件を満たす $2\times (n+1)$ の木を作ることを考える(図3). 辺 $1,3,4$ を除けばパターン $A$ の木ができ，辺 $2$ を除けばパターン $B$ の木ができる.\
　同様に $2\times n$ のパターン $B$ の木の右側に $2$ つの頂点と $3$ つの辺を貼り，辺を除くことで条件を満たす $2\times (n+1)$ の木を作ることを考える(図4).  辺 $1,3$ を除けばパターン $A$ の木ができ，辺 $2$ を除けばパターン $B$ の木ができる.\
　逆に，これらで尽くされていることもわかる. 以上の議論から，$a_1=1,b_1=0$ および以下の漸化式が成り立つ：
$$ a_{n+1}=3a_n+2b_n, \quad b_{n+1}=a_n+b_n$$
したがって，求める答えは $a_5+b_5=\bf{209}$ である. 
![figure 1](\/images\/FGufTm5MESQP4xW3ejuzl1dWo2E0HZchcZFuI2ms)
公式解説
https://onlinemathcontest.com/contests/omc096/editorial/2998
　下図のように，長方形の空間が境界線（点線）で $2\times5$ の区画に区切られており，境界線によって隣り合う区画は自由に行き来することができます．ここで，$13$ 本の区画の境界線の中から $4$ つ選んで，そこに壁を作ります．壁のある境界線は行き来することができなくなります．このとき，次の条件を満たす $4$ 本の境界線の選び方は何通りありますか．

- 相異なる任意の二つの区画に対して，一方から他方へ行くことができる．

ただし，回転や反転によって一致するものも区別して数えるものとします．
![figure 1](\/images\/IEuFWIl5E9oONyDnalbFKWFkAVN4HkudZGSGH3Yg)