A106376 Number of binary trees (each vertex has 0, or 1 left, or 1 right, or 2 children) with n edges and having all leaves at the same level.

2, 5, 10, 24, 52, 121, 258, 616, 1344, 3128, 6996, 16160, 36248, 85041, 191298, 444168, 1019328, 2359392, 5405488, 12625336, 29066304, 67659824, 156911364, 365683744, 849401072, 1987046192, 4624252776, 10816019328

Offset: 1

Author

Emeric Deutsch, May 05 2005

Keywords

• nonn

Comments

Column sums of A106375.

Examples

			a(3)=10 because we have eight paths of length 3 (each edge can have two orientations) and two trees in the shape of the letter Y (the bottom edge can have two orientations).
		

Crossrefs

Cf. A106375.

Programs

Maple

a:=proc(n,k) if n=1 and k=1 then 2 elif n=1 and k=2 then 1 elif n=1 then 0 elif k=1 then 0 else 2*a(n-1,k-1) + add(a(n-1,j)*a(n-1,k-2-j),j=1..k-3) fi end: seq(add(a(n,k),n=1..k),k=1..15); # a(n,k)=A106375(n,k)

Mathematica

A[n_, k_] := A[n, k] = Which[
   n == 1 && k == 1, 2,
   n == 1 && k == 2, 1,
   n == 1, 0,
   k == 1, 0,
   True, 2*A[n-1, k-1] + Sum[A[n-1, j]*A[n-1, k-2-j], {j, 1, k-3}]];
a[k_] := Sum[A[n, k], {n, 1, k}];
Table[a[k], {k, 1, 28}] (* Jean-François Alcover, Sep 21 2024, after Maple program *)

Formula

See the Maple program where a recurrence relation for the triangle A106375(n, k) is given; a(k) is the sum of the terms in column k of this triangle.