スタートを頂点Aとする。
n回目にAにいるパタンをa(n)通りとする。
a(0)=1である。
n回目にA以外にいるのは2^n - a(n)通りで、これがa(n + 1) と一致するから
a(n + 1) = 2^n - a(n)
この漸化式をとくと
a(n) = (2^n + 2(-1)^n)/3