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

Author

Emeric Deutsch, Jul 30 2006

Keywords

• nonn
• tabl

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).

Examples

			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;
		

Crossrefs

Cf. A000108, A120989, A121445.

Programs

Maple

T:=proc(n,k) if k
				

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.