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

Terms

a(0) =0a(1) =1a(2) =6a(3) =31a(4) =144a(5) =637a(6) =2730a(7) =11467a(8) =47508a(9) =194953a(10) =794574a(11) =3222583a(12) =13023192a(13) =52491349a(14) =211161138a(15) =848231779a(16) =3403688796a(17) =13647040225a(18) =54685016022a(19) =219030629455a(20) =876994213920