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,1

Comments

Column sums of A106375.

Links

Table of n, a(n) for n=1..28.

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.

Example

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

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

Crossrefs

Cf. A106375.

Sequence in context: A316697 A032170 A084081 * A359068 A151514 A321007

Adjacent sequences: A106373 A106374 A106375 * A106377 A106378 A106379

Keyword

nonn

Author

Emeric Deutsch, May 05 2005

Status

approved