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

Author

Louis Shapiro, Aug 21 2013

Keywords

• nonn

Examples

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

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

Crossrefs

Without the bicoloring A228403 is the result.

Cf. A000108.

Programs

Magma

[1,2] cat [Catalan(n+2) -2*Catalan(n+1) +2*Catalan(n): n in [2..30]]; // G. C. Greubel, May 03 2021

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

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

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

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)