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

Terms

a(0) =1a(1) =2a(2) =3a(3) =6a(4) =17a(5) =42a(6) =90a(7) =194a(8) =441a(9) =1006a(10) =2242a(11) =4950a(12) =10974a(13) =24376a(14) =53961a(15) =119048a(16) =262337a(17) =577782a(18) =1271117a(19) =2792718a(20) =6129342a(21) =13441616a(22) =29454517a(23) =64492800a(24) =141108878a(25) =308542280a(26) =674238780a(27) =1472532300a(28) =3214268735a(29) =7012637490