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

Terms

a(0) =1a(1) =0a(2) =1a(3) =2a(4) =1a(5) =8a(6) =5a(7) =18a(8) =37a(9) =40a(10) =145a(11) =178a(12) =417a(13) =872a(14) =1301a(15) =3330a(16) =5365a(17) =11080a(18) =22801a(19) =39362a(20) =86721a(21) =157128a(22) =312293a(23) =631666a(24) =1169541a(25) =2416104a(26) =4602961a(27) =9061458a(28) =18123553a(29) =34717608