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

Terms

a(0) =1a(1) =3a(2) =9a(3) =27a(4) =82a(5) =255a(6) =819a(7) =2727a(8) =9397a(9) =33312a(10) =120537a(11) =441855a(12) =1631017a(13) =6036879a(14) =22345074a(15) =82589247a(16) =304612975a(17) =1120960983a(18) =4116353265a(19) =15088372416a(20) =55224373105a(21) =201895801851a(22) =737506551321