|
Search: id:A127530
|
|
|
| A127530 |
|
Triangle read by rows: T(n,k) is the number of binary trees with n edges and k jumps (n>=0, 0<=k<=ceil(n/2)-1 for n>=1). 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. |
|
+0
3
|
|
| 1, 2, 5, 12, 2, 29, 13, 70, 60, 2, 169, 235, 25, 408, 836, 184, 2, 985, 2790, 1046, 41, 2378, 8896, 5080, 440, 2, 5741, 27410, 22164, 3410, 61, 13860, 82230, 89440, 21580, 900, 2, 33461, 241467, 340058, 118714, 9115, 85, 80782, 696732, 1233562, 588952
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
Row 0 has one term, row n (n>=1) has ceil(n/2) terms. Row sums are the Catalan numbers (A000108). T(n,0)=A000129(n-1) (the Pell numbers). Sum(k*T(n,k),k>=0)=binom(2n,n-2)-binom(2n-2,n-2)=A127531(n). The Krandick reference considers the statistic "number of jumps" 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 G=1+2zG+z^2[t(G-1)+1]G.
|
|
EXAMPLE
|
Triangle starts:
1;
2;
5;
12,2;
29,13;
70,60,2;
169,235,25;
|
|
MAPLE
|
G:= (-z^2-2*z+z^2*t+1-sqrt(z^4+4*z^3-2*z^4*t+2*z^2-4*z^3*t-4*z+z^4*t^2-2*z^2*t+1))/2/t/z^2: Gser:=simplify(series(G, z=0, 17)): for n from 1 to 14 do P[n]:=sort(coeff(Gser, z, n)) od: 1; for n from 0 to 14 do seq(coeff(P[n], t, j), j=0..ceil(n/2)-1) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A000108, A000129, A127531.
Adjacent sequences: A127527 A127528 A127529 this_sequence A127531 A127532 A127533
Sequence in context: A071293 A109623 A127532 this_sequence A110020 A070266 A125199
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 18 2007
|
|
|
Search completed in 0.002 seconds
|
