A052894 - OEIS

%I #59 Jul 14 2024 17:41:02

%S 1,1,5,46,631,11586,267369,7442758,242833091,9090987610,384209125453,

%T 18096001098462,939991769248239,53388611049236386,3291647968944928337,

%U 218948960832551848438,15629052780600654123739,1191728692751208814306986,96675526164560545405689141

%N a(n) is the number of Schröder trees on n vertices with a prescribed root.

%C Previous name was: A simple grammar.

%C Number of pointed trees on pointed sets k[1...k...n] with a prescribed point k. - _Gus Wiseman_, Sep 27 2015

%H William Y. C. Chen, <a href="https://doi.org/10.1073/pnas.87.24.9635">A general bijective algorithm for trees</a>, PNAS December 1, 1990 vol. 87 no. 24 9635-9639.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=870">Encyclopedia of Combinatorial Structures 870</a>

%F E.g.f.: RootOf(-2*_Z + _Z*exp(x*_Z) + 1).

%F a(n) = A053492(n)/n.

%F From _Paul D. Hanna_, Jun 19 2015: (Start)

%F E.g.f. A(x) satisfies:

%F (1) A(x) = (1/x) * Series_Reversion( 2*x - x*exp(x) ).

%F (2) A(x) = 1 + (1/x) * Sum_{n>=1} d^(n-1)/dx^(n-1) (exp(x)-1)^n * x^n / n!.

%F (3) A(x) = exp( Sum_{n>=1} d^(n-1)/dx^(n-1) (exp(x)-1)^n * x^(n-1) / n! ).

%F (End)

%F (4) A(x) = Sum_[n>=0} exp(n*x*A(x)) / 2^(n+1). - _Paul D. Hanna_, Apr 07 2018

%F a(n) = (1/(n+1)!) * Sum_{k=0..n} (n+k)! * Stirling2(n,k). - _Seiichi Manyama_, Nov 06 2023

%e 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

%p spec := [S,{C=Set(B,1 <= card),B=Prod(Z,S),S=Sequence(C)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

%t m = 20; (* number of terms *)

%t 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 *)

%o (PARI) {a(n) = local(A=1); A = (1/x)*serreverse(2*x - x*exp(x +x^2*O(x^n) )); n!*polcoeff(A, n)}

%o for(n=0, 20, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jun 19 2015

%o (PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}

%o {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)}

%o for(n=0, 25, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jun 19 2015

%o (PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}

%o {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)}

%o for(n=0, 25, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jun 19 2015

%Y Cf. A053492, A262673, A010683.

%K nonn,easy

%O 0,3

%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000

%E New name from _Vaclav Kotesovec_, Feb 16 2015