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
KEYWORD
nonn
AUTHOR
Louis Shapiro, Aug 20 2013
STATUS
approved