OFFSET
0,3
COMMENTS
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.
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>=0} k*T(n,k) = binomial(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 01 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. - Philippe Deléham, Feb 06 2012
LINKS
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see Table 2).
FindStat - Combinatorial Statistic Finder, The number of valleys not on the x-axis of a Dyck path.
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.
T(n,m) = Sum_{k=0..n-m} k*C(n,m+k)*C(n-k-1,m)/n, n>0, T(0,0)=1. - Vladimir Kruchinin, Oct 29 2020
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; ... - Philippe Deléham, 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]] (* Jean-François Alcover, Jul 22 2011, after g.f. *)
PROG
(Maxima)
T(n, m):=if n=0 and m=0 then 1 else if n=0 then 0 else sum(k*binomial(n, m+k)*binomial(n-k-1, m), k, 0, n-m)/(n); /* Vladimir Kruchinin, Oct 29 2020 */
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jan 18 2007
STATUS
approved