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

Terms

a(0) =1a(1) =3a(2) =9a(3) =30a(4) =108a(5) =405a(6) =1548a(7) =5967a(8) =23085a(9) =89451a(10) =346842a(11) =1345248a(12) =5218263a(13) =20242872a(14) =78528609a(15) =304640595a(16) =1181814705a(17) =4584708702a(18) =17785841652a(19) =68998115709a(20) =267670245492