login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052894 a(n) is the number of Schröder trees on n vertices with a prescribed root. 5
1, 1, 5, 46, 631, 11586, 267369, 7442758, 242833091, 9090987610, 384209125453, 18096001098462, 939991769248239, 53388611049236386, 3291647968944928337, 218948960832551848438, 15629052780600654123739 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=0..16.

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

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

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

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

Cf. A053492, A262673, A010683.

Sequence in context: A121631 A071214 A052873 * A292408 A295552 A066998

Adjacent sequences:  A052891 A052892 A052893 * A052895 A052896 A052897

KEYWORD

nonn,easy

AUTHOR

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

EXTENSIONS

New name from Vaclav Kotesovec, Feb 16 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 13 21:59 EDT 2019. Contains 327981 sequences. (Running on oeis4.)