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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A228197 Number of n-edge ordered trees with bicolored boundary edges. 2
1, 2, 8, 36, 160, 692, 2928, 12200, 50304, 205940, 838928, 3405496, 13788736, 55723592, 224863712, 906365136, 3649978880, 14687731572, 59067989072, 237424661016, 953914608320, 3831159414552, 15381896102432, 61739966366256, 247750559632640, 993955865320392, 3986890331450528 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

D. E. Davenport, L. K. Pudwell, L. W. Shapiro, L. C. Woodson, The Boundary of Ordered Trees, 2014.

Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.

E. Deutsch, L. W. Shapiro, A bijection between ordered trees and 2-Motzkin paths and its many consequences, Disc. Math. 256 (2002) 655-670.

FORMULA

G.f.: (1+4*x^2*B^2*C)/(1-2*x), C is the Catalan g.f. (see A000108) and B =(1-4*x)^(-1/2) is the g.f. for the central binomial coefficients (A000984).

a(n) ~ 4^n * (1-1/(sqrt(Pi*n))). - Vaclav Kotesovec, Aug 23 2013

Conjecture: (-n+1)*a(n) +2*(5*n-8)*a(n-1) +4*(-8*n+17)*a(n-2) +16*(2*n-5)*a(n-3)=0. - R. J. Mathar, Aug 25 2013

a(n) = 2^(2*n)-2^n*JacobiP(n-1,1/2,-n,3) = 2^(2*n)-2*A082590(n-1), which satisfies the above conjecture. - Benedict W. J. Irwin, Sep 16 2016

EXAMPLE

When n=3 edges there are A000108(3)= 5 ordered trees. Four of these consist of three boundary edges each contributing 2^3 trees to the count. The last, UDUDUD, has two boundary edges giving the last 2^2 trees for a total of 36.

MATHEMATICA

CoefficientList[Series[(1-2*x-2*x*Sqrt[1-4*x])/((4*x-1)*(2*x-1)), {x, 0, 20}], x] (* Vaclav Kotesovec, Aug 23 2013 *)

Table[2^(2n)-2^n*JacobiP[n-1, 1/2, -n, 3], {n, 0, 20}] (* Benedict W. J. Irwin, Sep 16 2016 *)

PROG

(PARI)

x = 'x + O('x^66);

C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108

B = (1-4*x)^(-1/2); \\ central binomial coefficients

gf = (1+4*x^2*B^2*C)/(1-2*x);

Vec(gf) \\ Joerg Arndt, Aug 21 2013

CROSSREFS

Cf. A000108, A000984, A228178, A228180.

Sequence in context: A321110 A228791 A088675 * A326244 A027743 A152124

Adjacent sequences:  A228194 A228195 A228196 * A228198 A228199 A228200

KEYWORD

nonn

AUTHOR

Louis Shapiro, Aug 20 2013

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 November 17 16:01 EST 2019. Contains 329236 sequences. (Running on oeis4.)