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).

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

Table of n, a(n) for n=0..46.

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

Cf. A000108, A000129, A127531.

Sequence in context: A317406 A286466 A127532 * A279347 A151574 A110020

Adjacent sequences: A127527 A127528 A127529 * A127531 A127532 A127533

Keyword

nonn,tabf

Author

Emeric Deutsch, Jan 18 2007

Status

approved