A228404 The number of complete binary trees with bicolored twigs. A twig is a vertex with one child on the boundary and the other child having no descendants.

1, 2, 8, 24, 76, 249, 836, 2860, 9932, 34918, 124032, 444448, 1604664, 5831765, 21316860, 78319140, 289064460, 1071275370, 3984871440, 14872552560, 55678270440, 209027020410, 786750047304, 2968257334104, 11223268563896, 42522737574604, 161415556062656, 613813414982656

Offset

0,2

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).

Formula

G.f.: 1 - x + 2*x*C^2 + x*C^4 where C is the g.f. for the Catalan numbers A000108.

Conjecture: -5*(n+3)*(n-2)*a(n) +5*(-n^2-n+18)*a(n-1) +5*(-n^2-n+48)*a(n-2) +(-5*n^2+20029*n+720)*a(n-3) +(-5*n^2-104153*n+186654)*

a(n-4) +(-5*n^2 +130153*n -508806)*a(n-5) +13650*(2*n-11)*(n-7)*a(n-6) = 0. - R. J. Mathar, Aug 08 2015

From G. C. Greubel, May 03 2021: (Start)

a(n) = C(n+2) - 2*C(n+1) + 2*C(n) with a(0) = 1, a(1) = 2, and C(n) = A000108(n).

E.g.f.: (-x^2*(1+x) + 2*exp(2*x) *( x*(1+x)*BesselI(0, 2*x) - (1+x^2)*BesselI(1, 2*x))/x^2. (End)

Example

For n = 2 there are two complete binary trees. Both consist of two twigs so can be colored 4 ways each.

Mathematica

Table[If[n<2, n+1, CatalanNumber[n+2] -2*CatalanNumber[n+1] +2*CatalanNumber[n]], {n, 0, 30}] (* G. C. Greubel, May 03 2021 *)

Prog

(PARI)
x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = 1 - x + 2*x*C^2 + x*C^4;
Vec(gf) \\ Joerg Arndt, Aug 22 2013
(Magma) [1, 2] cat [Catalan(n+2) -2*Catalan(n+1) +2*Catalan(n): n in [2..30]]; // G. C. Greubel, May 03 2021
(Sage) [1, 2]+[catalan_number(n+2) -2*catalan_number(n+1) +2*catalan_number(n) for n in (2..30)] # G. C. Greubel, May 03 2021

Crossrefs

Without the bicoloring A228403 is the result.

Cf. A000108.

Sequence in context: A130495 A026070 A093833 * A006952 A327550 A034741

Adjacent sequences: A228401 A228402 A228403 * A228405 A228406 A228407

Keyword

nonn

Author

Louis Shapiro, Aug 21 2013

Status

approved