A127533 Sum of jump-lengths of all binary trees with n edges.

0, 0, 0, 2, 17, 100, 506, 2366, 10556, 45696, 193800, 810084, 3350479, 13748020, 56071470, 227613750, 920540040, 3711935040, 14932102320, 59951235420, 240316859250, 962056169256, 3847193657076, 15370712686252, 61364157982952

Offset

0,4

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

The Krandick reference is about jumps and jump-length in full binary trees.

Links

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

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

Formula

G.f.: z^3*C^6*(C+1)/sqrt(1-4z), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

a(n) = binomial(2*n+1,n-3) + binomial(2*n,n-3).

a(n) = Sum_{k>=0} A127532(n,k).

a(n) ~ n -> 4^n*(3-275/(8*n)+29475/(128*n^2)-1268225/(1024*n^3)+195652737/ (32768*n^4))/sqrt(n*Pi). - Peter Luschny, Dec 19 2015

D-finite with recurrence -(n-3)*(3*n+2)*(n+4)*a(n) +2*n*(3*n+5)*(2*n-1)*a(n-1)=0. - R. J. Mathar, Jul 26 2022

Maple

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

Mathematica

Table[Binomial[2 n + 1, n - 3] + Binomial[2 n, n - 3], {n, 0, 24}] (* Michael De Vlieger, Dec 19 2015 *)

Prog

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

Crossrefs

Cf. A127532, A127529.

Sequence in context: A163790 A129123 A109724 * A023260 A174365 A119363

Adjacent sequences: A127530 A127531 A127532 * A127534 A127535 A127536

Keyword

nonn

Author

Emeric Deutsch, Jan 18 2007

Status

approved