|
|
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
|
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.
|
|
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).
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 *)
|
|
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);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|