

A120988


Triangle read by rows: T(n,k) is the number of binary trees with n edges and such that the first leaf in the preorder traversal is at level k (1<=k<=n). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.


1



2, 1, 4, 2, 4, 8, 5, 9, 12, 16, 14, 24, 30, 32, 32, 42, 70, 85, 88, 80, 64, 132, 216, 258, 264, 240, 192, 128, 429, 693, 819, 833, 760, 624, 448, 256, 1430, 2288, 2684, 2720, 2490, 2080, 1568, 1024, 512, 4862, 7722, 9009, 9108, 8361, 7068, 5488, 3840, 2304, 1024
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Row sums are the Catalan numbers (A000108). T(n,1)=A000108(n1) for n>=2 (the Catalan numbers). T(n,n)=2^n. Sum(k*T(n,k),k=1..n)=A120989(n).


LINKS

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


FORMULA

T(n,k)=Sum(j*binomial(k,j)*binomial(2n2k+j,nk)/(2n2k+j), j=0..k). G.f.=1/[1tz(1+C)], where C=[1sqrt(14z)]/(2z) is the Catalan function.


EXAMPLE

T(2,1)=1 because we have the tree /\.
Triangle starts:
2;
1;4;
2,4,8;
5,9,12,16;
14,24,30,32,32;


MAPLE

T:=proc(n, k) if k<n then add(j*binomial(k, j)*binomial(2*n2*k+j, nk)/(2*n2*k+j), j=0..k) elif k=n then 2^n else 0 fi end:for n from 1 to 11 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form


CROSSREFS

Cf. A000108, A120989, A121445.
Sequence in context: A105474 A216568 A219432 * A095979 A276133 A307602
Adjacent sequences: A120985 A120986 A120987 * A120989 A120990 A120991


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Jul 30 2006


STATUS

approved



