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

Terms

a(0) =1a(1) =0a(2) =3a(3) =3a(4) =12a(5) =30a(6) =93a(7) =300a(8) =1038a(9) =3810a(10) =14781a(11) =60375a(12) =258807a(13) =1160949a(14) =5435652a(15) =26502555a(16) =134282406a(17) =705720549a(18) =3840542031a(19) =21608662710a(20) =125523530724a(21) =751831408929