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

Terms

a(0) =1a(1) =2a(2) =4a(3) =8a(4) =19a(5) =52a(6) =148a(7) =416a(8) =1141a(9) =3078a(10) =8248a(11) =22096a(12) =59319a(13) =159560a(14) =429624a(15) =1157024a(16) =3115481a(17) =8387146a(18) =22575900a(19) =60765464a(20) =163557995a(21) =440246780a(22) =1185025900a(23) =3189793984a(24) =8586134701a(25) =23111701262a(26) =62210729264a(27) =167455038112a(28) =450745122735