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

Terms

a(0) =1a(1) =3a(2) =6a(3) =16a(4) =55a(5) =161a(6) =412a(7) =1086a(8) =3013a(9) =8199a(10) =21602a(11) =56748a(12) =150163a(13) =395885a(14) =1034872a(15) =2695210a(16) =7014705a(17) =18219971a(18) =47176414a(19) =121863960a(20) =314305951a(21) =809367049a(22) =2080584852a(23) =5340057974a(24) =13687727069a(25) =35041285439a(26) =89599274138a(27) =228842966084a(28) =583876120811