login
A052894
a(n) is the number of Schröder trees on n vertices with a prescribed root.
18
1, 1, 5, 46, 631, 11586, 267369, 7442758, 242833091, 9090987610, 384209125453, 18096001098462, 939991769248239, 53388611049236386, 3291647968944928337, 218948960832551848438, 15629052780600654123739, 1191728692751208814306986, 96675526164560545405689141
OFFSET
0,3
COMMENTS
Previous name was: A simple grammar.
Number of pointed trees on pointed sets k[1...k...n] with a prescribed point k. - Gus Wiseman, Sep 27 2015
LINKS
William Y. C. Chen, A general bijective algorithm for trees, PNAS December 1, 1990 vol. 87 no. 24 9635-9639.
FORMULA
E.g.f.: RootOf(-2*_Z + _Z*exp(x*_Z) + 1).
a(n) = A053492(n)/n.
From Paul D. Hanna, Jun 19 2015: (Start)
E.g.f. A(x) satisfies:
(1) A(x) = (1/x) * Series_Reversion( 2*x - x*exp(x) ).
(2) A(x) = 1 + (1/x) * Sum_{n>=1} d^(n-1)/dx^(n-1) (exp(x)-1)^n * x^n / n!.
(3) A(x) = exp( Sum_{n>=1} d^(n-1)/dx^(n-1) (exp(x)-1)^n * x^(n-1) / n! ).
(End)
(4) A(x) = Sum_[n>=0} exp(n*x*A(x)) / 2^(n+1). - Paul D. Hanna, Apr 07 2018
a(n) = (1/(n+1)!) * Sum_{k=0..n} (n+k)! * Stirling2(n,k). - Seiichi Manyama, Nov 06 2023
EXAMPLE
The a(4) = 46 pointed trees of the form rootpoint[pointedbranch ... pointedbranch] on 1[1 2 3 4] are 1[1 2[2 3[3 4]]], 1[1 2[2 4[3 4]]], 1[1 2[2[2 4] 3]], 1[1 2[2[2 3] 4]], 1[1 2[2 3 4]], 1[1 3[2 3[3 4]]], 1[1 3[2[2 4] 3]], 1[1 3[3 4[2 4]]], 1[1 3[3[2 3] 4]], 1[1 3[2 3 4]], 1[1 4[2 4[3 4]]], 1[1 4[3 4[2 4]]], 1[1 4[2[2 3] 4]], 1[1 4[3[2 3] 4]], 1[1 4[2 3 4]], 1[1[1 3[3 4]] 2], 1[1[1 4[3 4]] 2], 1[1[1[1 4] 3] 2], 1[1[1[1 3] 4] 2], 1[1[1 3 4] 2], 1[1[1 2[2 4]] 3], 1[1[1 4[2 4]] 3], 1[1[1[1 4] 2] 3], 1[1[1[1 2] 4] 3], 1[1[1 2 4] 3], 1[1[1 2[2 3]] 4], 1[1[1 3[2 3]] 4], 1[1[1[1 3] 2] 4], 1[1[1[1 2] 3] 4], 1[1[1 2 3] 4], 1[1[1 2] 3[3 4]], 1[1[1 2] 4[3 4]], 1[1[1 3] 2[2 4]], 1[1[1 3] 4[2 4]], 1[1[1 4] 2[2 3]], 1[1[1 4] 3[2 3]], 1[1 2 3[3 4]], 1[1 2 4[3 4]], 1[1 2[2 4] 3], 1[1 3 4[2 4]], 1[1 2[2 3] 4], 1[1 3[2 3] 4], 1[1[1 4] 2 3], 1[1[1 3] 2 4], 1[1[1 2] 3 4], 1[1 2 3 4]. - Gus Wiseman, Sep 27 2015
MAPLE
spec := [S, {C=Set(B, 1 <= card), B=Prod(Z, S), S=Sequence(C)}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);
MATHEMATICA
m = 20; (* number of terms *)
Rest@CoefficientList[InverseSeries[Series[2*x - x*E^x, {x, 0, m}], x], x]*Range[0, m-1]! (* Jean-François Alcover, Oct 11 2022 *)
PROG
(PARI) {a(n) = local(A=1); A = (1/x)*serreverse(2*x - x*exp(x +x^2*O(x^n) )); n!*polcoeff(A, n)}
for(n=0, 20, print1(a(n), ", ")) \\ Paul D. Hanna, Jun 19 2015
(PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{a(n)=local(A=1); A = 1 + (1/x)*sum(m=1, n+1, Dx(m-1, (exp(x +x*O(x^n)) - 1)^m * x^m/m!)); n!*polcoeff(A, n)}
for(n=0, 25, print1(a(n), ", ")) \\ Paul D. Hanna, Jun 19 2015
(PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{a(n)=local(A=1+x+x*O(x^n)); A = exp(sum(m=1, n+1, Dx(m-1, (exp(x +x*O(x^n)) - 1)^m * x^(m-1)/m!)+x*O(x^n))); n!*polcoeff(A, n)}
for(n=0, 25, print1(a(n), ", ")) \\ Paul D. Hanna, Jun 19 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
EXTENSIONS
New name from Vaclav Kotesovec, Feb 16 2015
STATUS
approved