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,1

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

Links

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

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.

Example

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

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

Crossrefs

Cf. A000108, A000079, A089408, A121686.

Sequence in context: A182896 A207605 A112931 * A125810 A226504 A152195

Adjacent sequences: A121682 A121683 A121684 * A121686 A121687 A121688

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 15 2006

Status

approved