皆さんサンクスです。
漏れも漸化式を導き出そうとしたけど、むりぽorz

>>345 さんから用語を拝借して、また、縦に2マス毎に「仮線」を引くとして、
A)　仮線を1本もまたがない
B)　仮線を1本以上またぐ
の2通り。
A)　単純に P1, P2, P3 の連結だから、A_12=B_6=3^6
B)　縦12マスだから仮線は5本、各々についてまたぐか否かを考えると、そのパターンは2^5-1=31通り。
B1) 仮線を1本またぐ、B2) 仮線を2本またぐ　…　B5) 5本またぐ、として各パターンを考える。

という方法でなんとかなる、でしょうか?? そもそもA)が合っているか自信ないのでつが…