login
A127530
Triangle read by rows: T(n,k) is the number of binary trees with n edges and k jumps (n >= 0, 0 <= k <= ceiling(n/2)-1 for n >= 1).
2
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
OFFSET
0,2
COMMENTS
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 Krandick reference considers the statistic "number of jumps" for full binary trees.
Row 0 has one term, row n (n >= 1) has ceiling(n/2) terms.
LINKS
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.
Row sums are the Catalan numbers (A000108).
T(n,0) = A000129(n-1) (the Pell numbers).
Sum_{k>=0} k*T(n,k) = binomial(2*n, n-2) - binomial(2n-2,n-2) = A127531(n).
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
MATHEMATICA
n = 13; g[t_, z_] := (-z^2 - 2z + z^2*t + 1 - Sqrt[z^4 + 4z^3 - 2z^4*t + 2z^2 - 4z^3*t - 4z + z^4*t^2 - 2z^2*t + 1])/2/t/z^2; Flatten[ CoefficientList[#1, t] & /@ CoefficientList[Simplify[Series[g[t, z], {z, 0, n}]], z]] (* Jean-François Alcover, Jul 22 2011, after g.f. *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jan 18 2007
STATUS
approved