A005750 Number of planted matched trees with n nodes.

1, 1, 3, 10, 39, 160, 702, 3177, 14830, 70678, 342860, 1686486, 8393681, 42187148, 213828802, 1091711076, 5609297942, 28982708389, 150496728594, 784952565145, 4110491658233, 21602884608167, 113907912618599, 602414753753310, 3194684310627727, 16984594260224529

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

When convolved with itself gives A000151.

Number of rooted trees with n nodes and edges not attached to root are 2-colored or oriented.

Also number of 2-trees (with 2n+1 cells) rooted at a symmetric end-edge. - Vladeta Jovovic, Aug 22 2001

Examples

			A(x) = x + x^2 + 3*x^3 + 10*x^4 + 39*x^5 + 160*x^6 + 702*x^7 + ...
		

References

• S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.5.
• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 75, Eq. (3.5.3).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..1325 (terms 1..500 from Alois P. Heinz)
• Loïc Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA], 2018.
• T. Fowler, I. Gessel, G. Labelle, P. Leroux, The specification of 2-trees, Adv. Appl. Math. 28 (2) (2002) 145-168, Table 1.
• Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45. See page 20, line -3. - From _N. J. A. Sloane_, Dec 15 2012
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 428
• R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
• R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
• N. J. A. Sloane, Transforms
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A000151, A058870, A058866, A054581, A245870.

Programs

Maple

A:= proc(n) option remember; if n=0 then 0 else unapply(convert(series(x*exp(add((A(n-1)(x^k))^2/(k*x^k), k=1..2*n)), x=0,2*n), polynom), x) fi end: a:= n-> coeff(series(A(n)(x), x=0, n+1), x,n): seq(a(n), n=1..23); # Alois P. Heinz, Aug 20 2008

Mathematica

max = 23; f[x_] := Sum[c[k]*x^k, {k, 0, max}]; c[0] = 0; c[1] = 1; coes = CoefficientList[ Series[ Log[f[x]/x] - Sum[f[x^k]^2/(k*x^k), {k, 1, max}], {x, 0, max}], x]; eqns = Rest[ Thread[coes == 0]]; s[2] = Solve[eqns[[1]], c[2]][[1]]; Do[eqns = Rest[eqns] /. s[k-1]; s[k] = Solve[ eqns[[1]], c[k]][[1]], {k, 3, max}]; Table[c[k], {k, 1, max}] /. Flatten[ Table[s[k], {k, 2, max}]] (* Jean-François Alcover, Oct 25 2011, after g.f. *)
terms = 26; (* B = g.f. of A000151 *) B[] = 0; Do[B[x] = x*Exp[2*Sum[ B[x^k]/k, {k, 1, terms}]] + O[x]^terms // Normal, terms];
A[x_] = Exp[Sum[B[x^k]/k, {k, 1, terms}]] + O[x]^terms;
CoefficientList[A[x], x] (* Jean-François Alcover, Jan 11 2018 *)

PARI

seq(N) = {my(A=vector(N, j, 1)); for(n=1, N-1, A[n+1] = 2/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); Vec(sqrt(Ser(A)))} \\ Andrew Howroyd, May 13 2018

Formula

a(n+1) is Euler transform of A000151.

G.f.: A(x) = x*exp( A(x)^2/x + A(x^2)^2/(2x^2) + A(x^3)^2/(3x^3) + ... + A(x^n)^2/(n*x^n) + ...). [Harary & Palmer (3.5.8)] - Paul D. Hanna

G.f.: sqrt(B(x)/x) where B(x) is the g.f. of A000151. - Andrew Howroyd, May 13 2018

a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.646542616232..., c = 0.06185402386554883780092844840921448929211072031752507960399709674242810089... - Vaclav Kotesovec, Sep 12 2014, updated Dec 26 2020

a(n) = A063687(n)+2*A058870(n). [Harary & Palmer (3.5.3)] - R. J. Mathar, Jan 13 2025

Extensions

More terms, formula and comment from Christian G. Bower, Dec 15 1999