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

Terms

a(0) =1a(1) =1a(2) =1a(3) =3a(4) =9a(5) =19a(6) =37a(7) =87a(8) =217a(9) =507a(10) =1157a(11) =2727a(12) =6553a(13) =15627a(14) =37077a(15) =88519a(16) =212569a(17) =510715a(18) =1226853a(19) =2952615a(20) =7120921a(21) =17192427a(22) =41538293a(23) =100458759a(24) =243211865a(25) =589313755a(26) =1428931333a(27) =3467193191a(28) =8418640793a(29) =20453853003