cp's OEIS Frontend

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.

%I A106376 #9 Sep 21 2024 08:42:49
%S A106376 2,5,10,24,52,121,258,616,1344,3128,6996,16160,36248,85041,191298,
%T A106376 444168,1019328,2359392,5405488,12625336,29066304,67659824,156911364,
%U A106376 365683744,849401072,1987046192,4624252776,10816019328
%N 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.
%C A106376 Column sums of A106375.
%F A106376 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 A106376 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 A106376 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 A106376 A[n_, k_] := A[n, k] = Which[
%t A106376    n == 1 && k == 1, 2,
%t A106376    n == 1 && k == 2, 1,
%t A106376    n == 1, 0,
%t A106376    k == 1, 0,
%t A106376    True, 2*A[n-1, k-1] + Sum[A[n-1, j]*A[n-1, k-2-j], {j, 1, k-3}]];
%t A106376 a[k_] := Sum[A[n, k], {n, 1, k}];
%t A106376 Table[a[k], {k, 1, 28}] (* _Jean-François Alcover_, Sep 21 2024, after Maple program *)
%Y A106376 Cf. A106375.
%K A106376 nonn
%O A106376 1,1
%A A106376 _Emeric Deutsch_, May 05 2005