A127530 -id:A127530 - cp's OEIS frontend

A127531 Number of jumps in all binary trees with n edges.

0, 0, 2, 13, 64, 285, 1210, 5005, 20384, 82212, 329460, 1314610, 5230016, 20764055, 82317690, 326012925, 1290244800, 5103910680, 20183646780, 79802261190, 315492902400, 1247247742650, 4930910180196, 19495286167698, 77085553829824, 304836321995800, 1205640294021800

Offset: 1

Emeric Deutsch, Jan 18 2007

nonn

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.

G. C. Greubel, Table of n, a(n) for n = 1..1000
David Anderson, E. S. Egge, M. Riehl, L. Ryan, R. Steinke, Y. Vaughan, Pattern Avoiding Linear Extensions of Rectangular Posets, arXiv:1605.06825 [math.CO], 2016.
Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.
Lin Yang and Shengliang Yang, Protected Branches in Ordered Trees, J. Math. Study (2023) Vol. 56, No. 1, 1-17.

Cf. A127530.

List([1..30], n-> Binomial(2*n,n-2) -Binomial(2*n-2,n-2)); # G. C. Greubel, May 08 2019

[Binomial(2*n, n-2) - Binomial(2*n - 2, n-2): n in [1..30]]; // Vincenzo Librandi, Dec 20 2015

[Binomial(2*n,n-2) -Binomial(2*n-2,n-2): n in [1..30]]; // G. C. Greubel, May 08 2019

seq(binomial(2*n,n-2)-binomial(2*n-2,n-2),n=1..28);

Table[Binomial[2n, n-2] - Binomial[2n-2, n-2], {n, 30}] (* or *) Table[4^(n-1)(n-1)(3n^2 -5n-2)Gamma[n-1/2]/(Sqrt[Pi]Gamma[n+3]), {n,30}] (* Michael De Vlieger, Dec 19 2015 *)

vector(30, n, binomial(2*n,n-2) -binomial(2*n-2,n-2) ) \\ G. C. Greubel, Mar 19 2017

[binomial(2*n,n-2) -binomial(2*n-2,n-2) for n in (1..30)] # G. C. Greubel, May 08 2019

a(n) = Sum_{k>=0} k*A127530(n,k).
a(n) = binomial(2*n, n-2) - binomial(2*n - 2, n-2).
From Peter Luschny, Dec 19 2015: (Start)
a(n) = 4^(n-1)*(n-1)*(3*n^2-5*n-2)*Gamma(n-1/2)/(sqrt(Pi)*Gamma(n+3)).
a(n) ~ 4^n*(3-139/(8*n)+8595/(128*n^2)-234745/(1024*n^3)+24282657/(32768*n^4)) /sqrt(n*Pi). (End)
D-finite with recurrence -5*(n+2)*(n-3)*a(n) +(19*n^2-26*n-5)*a(n-1) +2*(n-2)*(2*n-5)*a(n-2)=0. - R. J. Mathar, Jul 26 2022
D-finite with recurrence +(n-3)*(3*n-2)*(n+2)*a(n) -2*(n-1)*(3*n+1)*(2*n-3)*a(n-1)=0. - R. J. Mathar, Jul 26 2022

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

Original entry on oeis.org

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

Offset: 0

Emeric Deutsch, Jan 18 2007

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.
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>=0} k*T(n,k) = binomial(2n+1, n-3) + binomial(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.

			Triangle starts:
   1;
   2;
   5;
  12,  2;
  29,  9,  4;
  70, 32, 22,  8;

W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

Cf. A000108, A000129, A074084, A127530, A127533.

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

G.f.: G = G(t,z) is given by (1 - t - 2z + 2tz - z^2)*G^2 - (1 - 2t + 2tz)*G - t = 0.

cp's OEIS Frontend

A127531 Number of jumps in all binary trees with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula