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

Terms

a(0) =1a(1) =1a(2) =1a(3) =1a(4) =3a(5) =9a(6) =19a(7) =33a(8) =55a(9) =109a(10) =243a(11) =529a(12) =1071a(13) =2093a(14) =4179a(15) =8673a(16) =18255a(17) =37981a(18) =77923a(19) =159649a(20) =329935a(21) =687117a(22) =1432403a(23) =2977505a(24) =6179215a(25) =12841597a(26) =26757059a(27) =55840033a(28) =116551119a(29) =243209325