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
Keywords
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
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
Extensions
More terms, formula and comment from Christian G. Bower, Dec 15 1999
Comments