login
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.
3
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
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
KEYWORD
nonn
AUTHOR
Louis Shapiro, Aug 21 2013
STATUS
approved