cp's OEIS Frontend

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

%I A052894 #62 Jan 05 2025 00:45:22
%S A052894 1,1,5,46,631,11586,267369,7442758,242833091,9090987610,384209125453,
%T A052894 18096001098462,939991769248239,53388611049236386,3291647968944928337,
%U A052894 218948960832551848438,15629052780600654123739,1191728692751208814306986,96675526164560545405689141
%N A052894 a(n) is the number of Schröder trees on n vertices with a prescribed root.
%C A052894 Previous name was: A simple grammar.
%C A052894 Number of pointed trees on pointed sets k[1...k...n] with a prescribed point k. - _Gus Wiseman_, Sep 27 2015
%H A052894 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 A052894 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=870">Encyclopedia of Combinatorial Structures 870</a>
%F A052894 E.g.f.: RootOf(-2*_Z + _Z*exp(x*_Z) + 1).
%F A052894 a(n) = A053492(n)/n.
%F A052894 From _Paul D. Hanna_, Jun 19 2015: (Start)
%F A052894 E.g.f. A(x) satisfies:
%F A052894 (1) A(x) = (1/x) * Series_Reversion( 2*x - x*exp(x) ).
%F A052894 (2) A(x) = 1 + (1/x) * Sum_{n>=1} d^(n-1)/dx^(n-1) (exp(x)-1)^n * x^n / n!.
%F A052894 (3) A(x) = exp( Sum_{n>=1} d^(n-1)/dx^(n-1) (exp(x)-1)^n * x^(n-1) / n! ).
%F A052894 (End)
%F A052894 (4) A(x) = Sum_{n>=0} exp(n*x*A(x)) / 2^(n+1). - _Paul D. Hanna_, Apr 07 2018
%F A052894 a(n) = (1/(n+1)!) * Sum_{k=0..n} (n+k)! * Stirling2(n,k). - _Seiichi Manyama_, Nov 06 2023
%e A052894 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 A052894 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 A052894 m = 20; (* number of terms *)
%t A052894 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 A052894 (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 A052894 for(n=0, 20, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jun 19 2015
%o A052894 (PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
%o A052894 {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 A052894 for(n=0, 25, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jun 19 2015
%o A052894 (PARI) {Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
%o A052894 {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 A052894 for(n=0, 25, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jun 19 2015
%Y A052894 Cf. A053492, A262673, A010683.
%K A052894 nonn,easy
%O A052894 0,3
%A A052894 encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E A052894 New name from _Vaclav Kotesovec_, Feb 16 2015