login
Number of jumps in all binary trees with n edges.
2

%I #41 Dec 06 2022 17:14:39

%S 0,0,2,13,64,285,1210,5005,20384,82212,329460,1314610,5230016,

%T 20764055,82317690,326012925,1290244800,5103910680,20183646780,

%U 79802261190,315492902400,1247247742650,4930910180196,19495286167698,77085553829824

%N Number of jumps in all binary trees with n edges.

%C 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.

%H G. C. Greubel, <a href="/A127531/b127531.txt">Table of n, a(n) for n = 1..1000</a>

%H David Anderson, E. S. Egge, M. Riehl, L. Ryan, R. Steinke, Y. Vaughan, <a href="http://arxiv.org/abs/1605.06825">Pattern Avoiding Linear Extensions of Rectangular Posets</a>, arXiv:1605.06825 [math.CO], 2016.

%H Colin Defant, <a href="https://arxiv.org/abs/1905.02309">Proofs of Conjectures about Pattern-Avoiding Linear Extensions</a>, arXiv:1905.02309 [math.CO], 2019.

%H W. Krandick, <a href="http://dx.doi.org/10.1016/j.cam.2003.08.018">Trees and jumps and real roots</a>, J. Computational and Applied Math., 162, 2004, 51-55.

%H Lin Yang and Shengliang Yang, <a href="https://doi.org/10.4208/jms.v56n1.23.01">Protected Branches in Ordered Trees</a>, J. Math. Study (2023) Vol. 56, No. 1, 1-17.

%F a(n) = Sum_{k>=0} k*A127530(n,k).

%F a(n) = binomial(2*n, n-2) - binomial(2*n - 2, n-2).

%F From _Peter Luschny_, Dec 19 2015: (Start)

%F a(n) = 4^(n-1)*(n-1)*(3*n^2-5*n-2)*Gamma(n-1/2)/(sqrt(Pi)*Gamma(n+3)).

%F a(n) ~ 4^n*(3-139/(8*n)+8595/(128*n^2)-234745/(1024*n^3)+24282657/(32768*n^4)) /sqrt(n*Pi). (End)

%F 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

%F 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

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

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

%o (Magma) [Binomial(2*n, n-2) - Binomial(2*n - 2, n-2): n in [1..30]]; // _Vincenzo Librandi_, Dec 20 2015

%o (PARI) vector(30, n, binomial(2*n,n-2) -binomial(2*n-2,n-2) ) \\ _G. C. Greubel_, Mar 19 2017

%o (Magma) [Binomial(2*n,n-2) -Binomial(2*n-2,n-2): n in [1..30]]; // _G. C. Greubel_, May 08 2019

%o (Sage) [binomial(2*n,n-2) -binomial(2*n-2,n-2) for n in (1..30)] # _G. C. Greubel_, May 08 2019

%o (GAP) List([1..30], n-> Binomial(2*n,n-2) -Binomial(2*n-2,n-2)) # _G. C. Greubel_, May 08 2019

%Y Cf. A127530.

%K nonn

%O 1,3

%A _Emeric Deutsch_, Jan 18 2007