login
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.
1

%I #9 Sep 21 2024 08:42:49

%S 2,5,10,24,52,121,258,616,1344,3128,6996,16160,36248,85041,191298,

%T 444168,1019328,2359392,5405488,12625336,29066304,67659824,156911364,

%U 365683744,849401072,1987046192,4624252776,10816019328

%N 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.

%C Column sums of A106375.

%F 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.

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

%p 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)

%t A[n_, k_] := A[n, k] = Which[

%t n == 1 && k == 1, 2,

%t n == 1 && k == 2, 1,

%t n == 1, 0,

%t k == 1, 0,

%t True, 2*A[n-1, k-1] + Sum[A[n-1, j]*A[n-1, k-2-j], {j, 1, k-3}]];

%t a[k_] := Sum[A[n, k], {n, 1, k}];

%t Table[a[k], {k, 1, 28}] (* _Jean-François Alcover_, Sep 21 2024, after Maple program *)

%Y Cf. A106375.

%K nonn

%O 1,1

%A _Emeric Deutsch_, May 05 2005