a(n) = Sum_{k=1..n} binomial(n,k) * phi(k) * phi(n - k + 1), where phi = A000010.

Terms

a(0) =1a(1) =3a(2) =11a(3) =30a(4) =94a(5) =238a(6) =692a(7) =1596a(8) =4536a(9) =9350a(10) =27840a(11) =52884a(12) =149668a(13) =294838a(14) =782432a(15) =1463224a(16) =4095792a(17) =7460274a(18) =20229356a(19) =36847380a(20) =100317284a(21) =170262974a(22) =492659240a(23) =814679680a(24) =2184447760a(25) =3965791284a(26) =9988168320a(27) =17883230712a(28) =49362800340a(29) =80674575956