|
| |
|
|
A091320
|
|
Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves.
|
|
0
| |
|
|
1, 2, 1, 4, 7, 1, 8, 30, 16, 1, 16, 104, 122, 30, 1, 32, 320, 660, 365, 50, 1, 64, 912, 2920, 2875, 903, 77, 1, 128, 2464, 11312, 17430, 9856, 1960, 112, 1, 256, 6400, 39872, 88592, 78974, 28560, 3864, 156, 1, 512, 16128, 130944, 396480, 512316, 294042
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| T(n,k) is the number of even trees with 2n edges and k-1 jumps. An even tree is an ordered tree in which each vertex has an even outdegree. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 19 2007
|
|
|
REFERENCES
| P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discrete Math. 204 (1999), 203-229.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.
|
|
|
FORMULA
| T(n, k)=(1/n)*binomial(n, k)*sum(2^(n+1-2k+j)*binomial(n, j)*binomial(n-k, k-1-j), j=0..n). G.f. G(t, z) satisfies zG^3 - (1 + z - tz)G + 1 = 0.
|
|
|
EXAMPLE
| 1; 2,1; 4,7,1; 8,30,16,1; 16,104,122,30,1;
|
|
|
MAPLE
| T := proc(n, k) if k=n then 1 else (1/n)*binomial(n, k)*sum(2^(n+1-2*k+j)*binomial(n, j)*binomial(n-k, k-1-j), j=0..n) fi end: seq(seq(T(n, k), k=1..n), n=1..12);
|
|
|
CROSSREFS
| Row sums give A001764.
Sequence in context: A121722 A193591 A059579 * A048787 A030102 A072010
Adjacent sequences: A091317 A091318 A091319 * A091321 A091322 A091323
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Feb 24 2004
|
| |
|
|
