

A121686


Number of branches in all binary trees with n edges. A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.


3



2, 6, 22, 84, 324, 1254, 4862, 18876, 73372, 285532, 1112412, 4338536, 16938120, 66192390, 258909390, 1013586540, 3971224620, 15571021620, 61096813140, 239888764440, 942483155640, 3705043827420, 14573172387852, 57351122857944
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..500
GuoNiu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
GuoNiu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.


FORMULA

a(n) = Sum_{k=1..n} k*A121685(n,k).
G.f.: (1  2*z) * (1  3*z  (1  z)*sqrt(1  4*z))/(z^2*sqrt(1  4*z)).
Recurrence: (n + 2)*(n^2  2*n + 3)*a(n) = 2*(2*n  1)*(n^2 + 2)*a(n1).  Vaclav Kotesovec, Dec 10 2013
a(n) = 2*(n^2 + 2)*binomial(2*n, n)/((n + 1)*(n + 2)).  Vaclav Kotesovec, Dec 10 2013


EXAMPLE

a(1) = 2 because we have two binary trees with 1 edge, namely / and \, with a total of 2 branches.


MAPLE

G:=(12*z)*(13*z(1z)*sqrt(14*z))/z^2/sqrt(14*z): Gser:=series(G, z=0, 31): seq(coeff(Gser, z, n), n=1..27);


CROSSREFS

Cf. A121685.
Sequence in context: A150243 A200316 A164870 * A245904 A128723 A150244
Adjacent sequences: A121683 A121684 A121685 * A121687 A121688 A121689


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Aug 15 2006


STATUS

approved



