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

Terms

a(0) =1a(1) =1a(2) =3a(3) =6a(4) =17a(5) =48a(6) =149a(7) =477a(8) =1579a(9) =5339a(10) =18375a(11) =64125a(12) =226387a(13) =807025a(14) =2900827a(15) =10501870a(16) =38258497a(17) =140146660a(18) =515897197a(19) =1907409850a(20) =7080017617a(21) =26373676870a(22) =98562581257a(23) =369433290520