

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.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


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.


LINKS

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


FORMULA

T(n, k)=2T(n1, k1) + sum(T(n1, j)T(n1, k2j), j=1..k3) (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[n1]+(t*P[n1])^2, P[0]=1.


EXAMPLE

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;


MAPLE

P[0]:=1: for n from 1 to 5 do P[n]:=sort(expand(2*t*P[n1]+t^2*P[n1]^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


CROSSREFS

Cf. A051179, A106376.
Sequence in context: A129699 A002349 A096794 * A194734 A255528 A201701
Adjacent sequences: A106372 A106373 A106374 * A106376 A106377 A106378


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, May 05 2005


STATUS

approved



