a(n) is the number of rooted labeled forests that satisfy the following conditions:
(i) there are 4 roots labeled 1, 2, 3, and 4;
(ii) there are n non-root vertices labeled 5,..., n+4;
(iii) the trees with roots 1 and 2 have width one;
(iv) the trees with roots 3 and 4 have height at most one.
To construct such a forest, for k=0,...,n, we take the following steps:
(1) choose k non-root vertices for trees with roots 1 and 2;
(2) construct width-one trees on roots 1 and 2 with the k non-root vertices;
(3) with the n-k remaining non-root vertices construct trees of height at most one on roots 3 and 4.
Thus a(n) is the sum (over k) of the product of the number of ways to do each step: a(n)=sum(k=0..n, binomial(n,k)*(k+1)!*2^(n-k)). (End)
