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

Terms

a(0) =1a(1) =2a(2) =6a(3) =23a(4) =94a(5) =392a(6) =1680a(7) =7387a(8) =33110a(9) =150905a(10) =698996a(11) =3287550a(12) =15685420a(13) =75877427a(14) =371994692a(15) =1847450970a(16) =9290557158a(17) =47291312897a(18) =243574276884