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

Terms

a(0) =1a(1) =2a(2) =4a(3) =12a(4) =48a(5) =176a(6) =592a(7) =2016a(8) =7168a(9) =25920a(10) =93440a(11) =336384a(12) =1216768a(13) =4425216a(14) =16143360a(15) =58993664a(16) =215965696a(17) =792154112a(18) =2910720000a(19) =10710884352a(20) =39464009728a(21) =145575002112a(22) =537583419392