A106375 Triangle read by rows: T(n,k) is the number of binary trees (each vertex has 0, or 1 left, or 1 right, or 2 children) with k edges and all leaves at level n.

2, 1, 0, 4, 2, 4, 4, 1, 0, 0, 8, 4, 8, 24, 18, 36, 48, 40, 36, 24, 8, 1, 0, 0, 0, 16, 8, 16, 48, 100, 136, 240, 528, 616, 1152, 1936, 2466, 3716, 4912, 5840, 7088, 7768, 7696, 7120, 5796, 4056, 2464, 1232, 456, 112, 16, 1, 0, 0, 0, 0, 32, 16, 32, 96, 200, 528, 736, 1632

Offset: 1

Author

Emeric Deutsch, May 05 2005

Keywords

• nonn
• tabf

Comments

Row n has 2^(n+1)-2 terms. In row n first nonzero term is T(n,n)=2^n and last nonzero term is T(n,2^(n+1)-2)=1. Row sums yield A051179. Column sums yield A106376.

Examples

			T(3,3)=8 because we have eight paths of length 3 (each edge can have two orientations).
Triangle begins:
2,1;
0,4,2,4,4,1;
0,0,8,4,8,24,18,36,48,40,36,24,8,1;
		

Crossrefs

Cf. A051179, A106376.

Programs

Maple

P[0]:=1: for n from 1 to 5 do P[n]:=sort(expand(2*t*P[n-1]+t^2*P[n-1]^2)) od: for n from 1 to 5 do seq(coeff(P[n],t^k),k=1..2^(n+1)-2) od; # yields sequence in triangular form

Mathematica

T[n_, k_] := T[n, k] = Which[
   n == 1 && k == 1, 2,
   n == 1 && k == 2, 1,
   n == 1 || k == 1, 0,
   True, 2*T[n-1, k-1] + Sum[T[n-1, j]*T[n-1, k-2-j], {j, 1, k-3}]];
Table[T[n, k], {n, 1, 5}, {k, 1, 2^(n+1)-2}] // Flatten (* Jean-François Alcover, Sep 21 2024, after Maple program for A106376 *)

Formula

T(n, k)=2T(n-1, k-1) + sum(T(n-1, j)T(n-1, k-2-j), j=1..k-3) (n, k>=2); T(1, 1)=2, T(1, 2)=1, T(1, k)=0 for k>=3, T(n, 1)=0 for n>=2. Generating polynomial P[n](t) of row n is given by rec. eq. P[n]=2tP[n-1]+(t*P[n-1])^2, P[0]=1.