This site is supported by donations to The OEIS Foundation.



Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A228197 Number of n-edge ordered trees with bicolored boundary edges. 2


%S 1,2,8,36,160,692,2928,12200,50304,205940,838928,3405496,13788736,

%T 55723592,224863712,906365136,3649978880,14687731572,59067989072,

%U 237424661016,953914608320,3831159414552,15381896102432,61739966366256,247750559632640,993955865320392,3986890331450528

%N Number of n-edge ordered trees with bicolored boundary edges.

%H G. C. Greubel, <a href="/A228197/b228197.txt">Table of n, a(n) for n = 0..1000</a>

%H D. E. Davenport, L. K. Pudwell, L. W. Shapiro, L. C. Woodson, <a href="http://faculty.valpo.edu/lpudwell/papers/treeboundary.pdf">The Boundary of Ordered Trees</a>, 2014.

%H Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, Leon C. Woodson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Davenport/dav3.html">The Boundary of Ordered Trees</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.

%H E. Deutsch, L. W. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00341-2">A bijection between ordered trees and 2-Motzkin paths and its many consequences</a>, Disc. Math. 256 (2002) 655-670.

%F 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).

%F a(n) ~ 4^n * (1-1/(sqrt(Pi*n))). - _Vaclav Kotesovec_, Aug 23 2013

%F 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

%F 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

%e 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.

%t 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 *)

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

%o (PARI)

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

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

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

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

%o Vec(gf) \\ _Joerg Arndt_, Aug 21 2013

%Y Cf. A000108, A000984, A228178, A228180.

%K nonn

%O 0,2

%A _Louis Shapiro_, Aug 20 2013

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 December 16 04:22 EST 2019. Contains 330013 sequences. (Running on oeis4.)