|
Search: id:A127532
|
|
|
| A127532 |
|
Triangle read by rows: T(n,k) is the number of binary trees with n edges and jump-length equal to k (n>=0, 0<=k<=n-2). In the preorder traversal of a binary 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 binary tree is called the jump-length. |
|
+0
3
|
|
| 1, 2, 5, 12, 2, 29, 9, 4, 70, 32, 22, 8, 169, 102, 86, 56, 16, 408, 306, 296, 244, 144, 32, 985, 883, 949, 901, 712, 368, 64, 2378, 2480, 2908, 3056, 2822, 2096, 928, 128, 5741, 6828, 8633, 9830, 10074, 8976, 6144, 2304, 256, 13860, 18514, 25032, 30482, 33792
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
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)=A000129(n+1) (the Pell numbers). T(n,1)=A074084(n). Sum(k*T(n,k),k>=0)=binom(2n+1,n-3)+binom(2n,n-3)=A127533(n). The distribution of the statistic "number of jumps" is given in A127530. The average jump distance in all binary trees with n edges is 2n(3n+5)(2n-1)/[(n+3)(n+4)(3n+1)] (i.e. about 4 levels when n is 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+2tz-z^2)G^2-(1-2t+2tz)G-t=0.
|
|
EXAMPLE
|
Triangle starts:
1;
2;
5;
12,2;
29,9,4;
70,32,22,8;
|
|
MAPLE
|
G:=(-1+2*t-2*t*z-sqrt(1-4*t*z+4*t^2*z^2-4*t*z^2))/2/(z^2-1+t-2*t*z+2*z): Gser:=simplify(series(G, z=0, 17)): for n from 0 to 12 do P[n]:=sort(coeff(Gser, z, n)) od: 1; 2; 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, A000129, A074084, A127530, A127533.
Sequence in context: A101828 A071293 A109623 this_sequence A127530 A151574 A110020
Adjacent sequences: A127529 A127530 A127531 this_sequence A127533 A127534 A127535
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 18 2007
|
|
|
Search completed in 0.002 seconds
|
