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

Terms

a(0) =1a(1) =3a(2) =12a(3) =58a(4) =219a(5) =861a(6) =3318a(7) =12372a(8) =45813a(9) =167319a(10) =604368a(11) =2165214a(12) =7696031a(13) =27172929a(14) =95383482a(15) =333071064a(16) =1157671257a(17) =4007027163a(18) =13817288372a(19) =47483201346a(20) =162669098403a(21) =555690505189