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

Terms

a(0) =1a(1) =0a(2) =0a(3) =1a(4) =2a(5) =0a(6) =1a(7) =8a(8) =4a(9) =1a(10) =18a(11) =36a(12) =9a(13) =32a(14) =144a(15) =129a(16) =66a(17) =400a(18) =801a(19) =472a(20) =932a(21) =3201a(22) =3698a(23) =2916a(24) =9865a(25) =19728a(26) =17248a(27) =28225a(28) =78690a(29) =105536