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

Terms

a(0) =1a(1) =3a(2) =6a(3) =13a(4) =35a(5) =91a(6) =214a(7) =491a(8) =1151a(9) =2711a(10) =6290a(11) =14427a(12) =33010a(13) =75444a(14) =171786a(15) =389500a(16) =880533a(17) =1986357a(18) =4471290a(19) =10042661a(20) =22511404a(21) =50374282a(22) =112545858a(23) =251073154a(24) =559324988a(25) =1244426930a(26) =2765391188a(27) =6138444816a(28) =13611448023a(29) =30152472569