|
Search: id:A127529
|
|
|
| A127529 |
|
Triangle read by rows: T(n,k) is the number of ordered trees with n edges and jump-length equal to k (n>=0, 0<=k<=n-2). 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; the positive difference of the levels is called the jump distance; the sum of the jump distances in a given ordered tree is called the jump-length. |
|
+0
4
|
|
| 1, 1, 2, 4, 1, 8, 5, 1, 16, 17, 8, 1, 32, 49, 38, 12, 1, 64, 129, 141, 77, 17, 1, 128, 321, 453, 361, 143, 23, 1, 256, 769, 1326, 1399, 834, 247, 30, 1, 512, 1793, 3640, 4776, 3869, 1765, 402, 38, 1, 1024, 4097, 9539, 14911, 15353, 9722, 3469, 623, 47, 1, 2048, 9217
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
Rows 0 and 1 have one term each; row n (n>=2) has n-1 terms. Row sums are the Catalan numbers (A000108). T(n,0)=A011782(n). T(n,1)=A000337(n-2). Sum(k*T(n,k),k>=0)=binom(2n-1,n-3)=A003516(n-1) for n>=3. The distribution of the statistic "number of jumps" is given in A091894. The average jump distance in all ordered trees with n edges is 2 - 5/(n+2) (i.e. about 2 levels for n large). The Krandick reference considers jump-length for full binary trees.
|
|
REFERENCES
|
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.
|
|
FORMULA
|
G.f.=G=G(t,z) is given by (1-t-2z+tz)G^2-(1-2t-z+tz)G-t=0.
|
|
EXAMPLE
|
Triangle starts:
1;
1;
2;
4,1;
8,5,1;
16,17,8,1;
32,49,38,12,1;
|
|
MAPLE
|
G:=1/2/(1-2*z-t+t*z)*(-2*t+1+t*z-z+sqrt(-2*t*z+1-2*z+t^2*z^2-2*t*z^2+z^2)): Gser:=simplify(series(G, z=0, 13)): for n from 0 to 12 do P[n]:=sort(coeff(Gser, z, n)) od: 1; 1; for n from 2 to 12 do seq(coeff(P[n], t, j), j=0..n-2) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A000108, A011782, A000337, A003516, A091894.
Sequence in context: A125810 A152195 A133156 this_sequence A091977 A112829 A121466
Adjacent sequences: A127526 A127527 A127528 this_sequence A127530 A127531 A127532
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 18 2007
|
|
|
Search completed in 0.003 seconds
|
