A228197 Number of n-edge ordered trees with bicolored boundary edges.
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
Offset: 0
Keywords
Examples
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.
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.
Programs
-
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 *) -
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
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