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,2

Comments

Essentially twice the Catalan numbers (A000108).

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

Links

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

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

Example

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.

Mathematica

Rest[CoefficientList[Series[(1-Sqrt[1-4*x]-2*x-x^2)/x, {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
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

Crossrefs

Sequence in context: A091468 A103457 A083587 * A061639 A243600 A239577

Adjacent sequences: A228400 A228401 A228402 * A228404 A228405 A228406

Keyword

nonn

Author

Louis Shapiro, Aug 21 2013

Status

approved