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

1, 1, 5, 46, 631, 11586, 267369, 7442758, 242833091, 9090987610, 384209125453, 18096001098462, 939991769248239, 53388611049236386, 3291647968944928337, 218948960832551848438, 15629052780600654123739, 1191728692751208814306986, 96675526164560545405689141

Offset: 0

Author

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

Keywords

• nonn
• easy

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

Examples

			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
		

Links

• William Y. C. Chen, A general bijective algorithm for trees, PNAS December 1, 1990 vol. 87 no. 24 9635-9639.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 870

Crossrefs

Cf. A053492, A262673, A010683.

Programs

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

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

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

Extensions

New name from Vaclav Kotesovec, Feb 16 2015