a(n) = Sum_{k=0..floor(n/2)} C(n-k,k+2)*3^(n-k-2)*(4/3)^k.

Terms

a(0) =0a(1) =0a(2) =1a(3) =9a(4) =58a(5) =318a(6) =1591a(7) =7503a(8) =33976a(9) =149436a(10) =643261a(11) =2724357a(12) =11395654a(13) =47210154a(14) =194121811a(15) =793526571a(16) =3228811492a(17) =13090123272a(18) =52917410041a(19) =213437246145a(20) =859342367890