|
Search: id:A120988
|
|
|
| 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. |
|
+0
2
|
|
| 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
(list; table; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
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).
|
|
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.
Adjacent sequences: A120985 A120986 A120987 this_sequence A120989 A120990 A120991
Sequence in context: A035685 A118736 A105474 this_sequence A095979 A054269 A086450
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 30 2006
|
|
|
Search completed in 0.002 seconds
|
