login
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

%I #2 Mar 30 2012 17:36:10

%S 2,1,4,2,4,8,5,9,12,16,14,24,30,32,32,42,70,85,88,80,64,132,216,258,

%T 264,240,192,128,429,693,819,833,760,624,448,256,1430,2288,2684,2720,

%U 2490,2080,1568,1024,512,4862,7722,9009,9108,8361,7068,5488,3840,2304,1024

%N 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.

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

%F 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.

%e T(2,1)=1 because we have the tree /\.

%e Triangle starts:

%e 2;

%e 1;4;

%e 2,4,8;

%e 5,9,12,16;

%e 14,24,30,32,32;

%p 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

%Y Cf. A000108, A120989, A121445.

%K nonn,tabl

%O 1,1

%A _Emeric Deutsch_, Jul 30 2006