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

Terms

a(0) =1a(1) =1a(2) =1a(3) =4a(4) =9a(5) =16a(6) =40a(7) =99a(8) =217a(9) =508a(10) =1236a(11) =2905a(12) =6864a(13) =16537a(14) =39663a(15) =94969a(16) =228953a(17) =552892a(18) =1334704a(19) =3229545a(20) =7828684a(21) =18989079a(22) =46110109a(23) =112104531a(24) =272771536a(25) =664217441a(26) =1618774405a(27) =3947949499a(28) =9634554687a(29) =23526909403