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.

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

Offset

1,1

Comments

Row sums are the Catalan numbers (A000108). T(n,1)=A000108(n-1) 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(2n-2k+j,n-k)/(2n-2k+j), j=0..k). G.f.=1/[1-tz(1+C)], where C=[1-sqrt(1-4z)]/(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*n-2*k+j, n-k)/(2*n-2*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 A377781 A276133

Adjacent sequences: A120985 A120986 A120987 * A120989 A120990 A120991

Keyword

nonn,tabl

Author

Emeric Deutsch, Jul 30 2006

Status

approved