A228403 The number of boundary twigs for complete binary twigs. A twig is a vertex with one edge on the boundary and only one other descendant.

1, 4, 10, 28, 84, 264, 858, 2860, 9724, 33592, 117572, 416024, 1485800, 5348880, 19389690, 70715340, 259289580, 955277400, 3534526380, 13128240840, 48932534040, 182965127280, 686119227300, 2579808294648, 9723892802904, 36734706144304, 139067101832008, 527495903500720, 2004484433302736

Offset: 1

Author

Louis Shapiro, Aug 21 2013

Keywords

• nonn

Comments

Essentially twice the Catalan numbers (A000108).

A068875 without the 2. - R. J. Mathar, Aug 24 2013

Examples

			For n  = 3 there are 5 complete binary trees. Of these UUUDUDDUDDUD consists of three twigs as does its mirror image UDUUDUUDUDDD. UUDUUDUDDDUD and UDUUUDUDDUDD each have one twig and UUDUDDUUDUDD has two.
		

Links

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

Programs

Mathematica

Rest[CoefficientList[Series[(1-Sqrt[1-4*x]-2*x-x^2)/x,{x,0,20}],x]] (* Vaclav Kotesovec, Aug 23 2013 *)

PARI

x = 'x + O('x^66);
C = serreverse( x/( 1/(1-x) ) ) / x; \\ Catalan A000108
gf = 2*x*C^2 - x;
Vec(gf) \\ Joerg Arndt, Aug 22 2013

Python

from itertools import accumulate
def A228403_list(size):
    if size < 1: return []
    L, accu = [1], [2]
    for _ in range(size-1):
        accu = list(accumulate(accu + [accu[-1]]))
        L.append(accu[-1])
    return L
print(A228403_list(29)) # Peter Luschny, Apr 25 2016

Formula

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

a(n) ~ 2^(2*n+1)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 23 2013