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.

2, 6, 22, 84, 324, 1254, 4862, 18876, 73372, 285532, 1112412, 4338536, 16938120, 66192390, 258909390, 1013586540, 3971224620, 15571021620, 61096813140, 239888764440, 942483155640, 3705043827420, 14573172387852, 57351122857944

Offset

1,1

Links

Alois P. Heinz, Table of n, a(n) for n = 1..500

Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]

Guo-Niu 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(n-1). - 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:=(1-2*z)*(1-3*z-(1-z)*sqrt(1-4*z))/z^2/sqrt(1-4*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