a(n) = T([n/2],[(n+1)/2]), where T = Delannoy triangle (A008288).

Terms

a(0) =1a(1) =1a(2) =3a(3) =5a(4) =13a(5) =25a(6) =63a(7) =129a(8) =321a(9) =681a(10) =1683a(11) =3653a(12) =8989a(13) =19825a(14) =48639a(15) =108545a(16) =265729a(17) =598417a(18) =1462563a(19) =3317445a(20) =8097453a(21) =18474633a(22) =45046719a(23) =103274625a(24) =251595969a(25) =579168825a(26) =1409933619a(27) =3256957317a(28) =7923848253a(29) =18359266785