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

Author

Emeric Deutsch, Aug 15 2006

Keywords

• nonn

Examples

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

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.

Crossrefs

Cf. A121685.

Programs

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);

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