|
| |
|
|
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.
|
|
3
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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.
Also the number of Dyck n-paths with k valleys at height >= 1. [David Scambler, Sep 1 2011]
Triangle T(n,k), with zeros omitted, given by (1,1,0,1,0,1,0,1,0,1,0,1,...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,1,...) where DELTA is the operator defined in A084938. - DELEHAM Philippe, Feb 06 2012
|
|
|
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) satisfies (1-t-2*z+t*z)*G^2 - (1-2*t-z+t*z)*G-t = 0.
|
|
|
EXAMPLE
| Triangle starts:
1;
1;
2;
4,1;
8,5,1;
16,17,8,1;
32,49,38,12,1;
Triangle (1,1,0,1,0,1,0,1,0,1, ...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,...) begins :
1
1, 0
2, 0, 0
4, 1, 0, 0
8, 5, 1, 0, 0
16, 17, 8, 1, 0, 0
32, 49, 38, 12, 1, 0, 0
64, 129, 141, 77, 17, 1, 0, 0 ...- DELEHAM Philippe, Feb 06 2012
|
|
|
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
|
|
|
MATHEMATICA
| n = 12; g[t_, z_] := 1/2/(1 - 2z - t + t*z)*(-2t + 1 + t*z - z + Sqrt[-2t*z + 1 - 2z + t^2*z^2 - 2t*z^2 + z^2]); Flatten[ CoefficientList[#, t]& /@ CoefficientList[ Simplify[Series[g[t, z], {z, 0, n}]], z]] (* From Jean-François Alcover, Jul 22 2011, after g.f. *)
|
|
|
CROSSREFS
| Cf. A000108, A011782, A000337, A003516, A091894.
Sequence in context: A125810 A152195 A133156 * A091977 A112829 A121466
Adjacent sequences: A127526 A127527 A127528 * A127530 A127531 A127532
|
|
|
KEYWORD
| nonn,tabf,changed
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 18 2007
|
| |
|
|
