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

Offset

1,3

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.

Links

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.

Formula

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

Maple

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

Mathematica

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

Prog

(Magma) [Binomial(2*n, n-2) - Binomial(2*n - 2, n-2): n in [1..30]]; // Vincenzo Librandi, Dec 20 2015
(PARI) vector(30, n, binomial(2*n, n-2) -binomial(2*n-2, n-2) ) \\ G. C. Greubel, Mar 19 2017
(Magma) [Binomial(2*n, n-2) -Binomial(2*n-2, n-2): n in [1..30]]; // G. C. Greubel, May 08 2019
(Sage) [binomial(2*n, n-2) -binomial(2*n-2, n-2) for n in (1..30)] # G. C. Greubel, May 08 2019
(GAP) List([1..30], n-> Binomial(2*n, n-2) -Binomial(2*n-2, n-2)) # G. C. Greubel, May 08 2019

Crossrefs

Cf. A127530.

Sequence in context: A081340 A211067 A296435 * A266633 A037745 A037626

Adjacent sequences: A127528 A127529 A127530 * A127532 A127533 A127534

Keyword

nonn

Author

Emeric Deutsch, Jan 18 2007

Status

approved