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

Terms

a(0) =1a(1) =3a(2) =11a(3) =36a(4) =123a(5) =408a(6) =1370a(7) =4560a(8) =15235a(9) =50760a(10) =169326a(11) =564336a(12) =1881582a(13) =6271632a(14) =20907156a(15) =69689376a(16) =232304355a(17) =774343560a(18) =2581169510a(19) =8603882160a(20) =28679699578a(21) =95598937008a(22) =318663476076