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

Terms

a(0) =1a(1) =1a(2) =1a(3) =4a(4) =9a(5) =16a(6) =61a(7) =183a(8) =433a(9) =1603a(10) =5581a(11) =15951a(12) =59449a(13) =225928a(14) =738893a(15) =2827321a(16) =11387617a(17) =41174086a(18) =163185805a(19) =686315474a(20) =2680560361a(21) =11035625413a(22) =48086847117a(23) =199640217719a(24) =853587430801