A121685 Triangle read by rows: T(n,k) is the number of binary trees having n edges and k branches (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, 4, 1, 8, 4, 2, 16, 12, 12, 2, 32, 32, 48, 16, 4, 64, 80, 160, 80, 40, 5, 128, 192, 480, 320, 240, 60, 10, 256, 448, 1344, 1120, 1120, 420, 140, 14, 512, 1024, 3584, 3584, 4480, 2240, 1120, 224, 28, 1024, 2304, 9216, 10752, 16128, 10080, 6720, 2016, 504, 42

Offset: 1

Author

Emeric Deutsch, Aug 15 2006

Keywords

• nonn
• tabl

Comments

The row sums are the Catalan numbers (A000108). T(n,1)=2^n = A000079(n). T(n,n)=A089408(n+1). Sum(k*T(n,k),k=1..n)=A121686(n).

Examples

			Triangle starts:
2;
4,1;
8,4,2;
16,12,12,2;
32,32,48,16,4;
		

Crossrefs

Cf. A000108, A000079, A089408, A121686.

Programs

Maple

c:=n->binomial(2*n,n)/(n+1): T:=proc(n,k) if k mod 2 = 0 then c(k/2)*binomial(n-1,k-1)*2^(n-k) else c((k-1)/2)*binomial(n-1,k-1)*2^(n-k+1) fi end: for n from 1 to 11 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

Formula

T(n,k)=2^(n-k)*c(k/2)*binomial(n-1,k-1) if k is even and 2^(n-k+1)*c((k-1)/2)*binomial(n-1,k-1) if k is odd, where c(m)=binomial(2m,m)/(m+1) are the Catalan numbers (A000108). G.f.=(1-2z+2tz)(1-2z-sqrt[(1-2z)^2-4t^2*z^2])/(2t^2*z^2) - 1.