A061575 Number of planar planted trees with n non-root nodes and without isolated 2-valent nodes.

0, 1, 0, 2, 2, 7, 14, 41, 107, 307, 871, 2546, 7497, 22380, 67366, 204517, 625132, 1922700, 5945469, 18473841, 57649699, 180602285, 567772883, 1790663427, 5663969707, 17963483548, 57112388657, 181994536484, 581168157605

Offset

0,4

Comments

An isolated 2-valent node is a 2-valent node non-adjacent to any other 2-valent node.

References

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(2.7.11).

Links

Table of n, a(n) for n=0..28.

Formula

G.f.: Sum_{i >= 0} 1/(i+1)*binomial(2*i, i)*x^(i+1)*((1+x^3)/(1-x^2))^(i+1)*(1+x*(1+x^3)/(1-x^2))^(-(i+1)) or (1-x^2+x^3-sqrt((1-x^2+x^3)*(1-4*x+3*x^2-3*x^3)))/(2-2*x^2+2*x^3).

a(n) = Sum_{k=1..n}(((Sum_{j=1..k}(binomial(2*j-2,j-1)*(-1)^(j-k)*binomial(k,j)))*Sum_{j=0..(n-k)/2}(binomial(k,j)*binomial(n-k-j-1,n-k-2*j)))/k). - Vladimir Kruchinin, Apr 15 2016

Mathematica

Table[Sum[((Sum[Binomial[2 j - 2, j - 1] (-1)^(j - k) Binomial[k, j], {j, 1, k}]) Sum[Binomial[k, j] Binomial[n - k - j - 1, n - k - 2 j], {j,
0, (n - k)/2}])/k, {k, 1, n}], {n, 0, 28}] (* Michael De Vlieger, Apr 15 2016 *)

Prog

(Maxima)
a(n):=sum(((sum(binomial(2*j-2, j-1)*(-1)^(j-k)*binomial(k, j), j, 1, k))*sum(binomial(k, j)*binomial(n-k-j-1, n-k-2*j), j, 0, (n-k)/2))/k, k, 1, n); /* Vladimir Kruchinin, Apr 15 2016 */

Crossrefs

Sequence in context: A162460 A187306 A061274 * A306009 A290646 A133602

Adjacent sequences: A061572 A061573 A061574 * A061576 A061577 A061578

Keyword

nonn

Author

Vladeta Jovovic, Jun 13 2001

Status

approved