The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors 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
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
Sequence in context: A321110 A228791 A088675 * A326244 A027743 A152124
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 13 10:24 EDT 2024. Contains 373383 sequences. (Running on oeis4.)