A127532 -id:A127532 - cp's OEIS frontend

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

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

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

Cf. A127532, A127529.

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

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

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

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

A127535 Triangle read by rows: T(n,k) is the number of even trees with 2n edges and jump-length equal to k (0<=k<=n-1).

Original entry on oeis.org

1, 2, 1, 4, 6, 2, 8, 22, 20, 5, 16, 66, 107, 70, 14, 32, 178, 428, 496, 252, 42, 64, 450, 1449, 2498, 2235, 924, 132, 128, 1090, 4410, 10234, 13662, 9878, 3432, 429, 256, 2562, 12479, 36558, 66107, 71370, 43043, 12870, 1430, 512, 5890, 33512, 118588

Offset: 1

Emeric Deutsch, Jan 19 2007

An even tree is an ordered tree in which each vertex has an even outdegree. 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.

The Krandick reference considers jumps and jump-length only in full binary trees.

			Triangle starts:
1;
2,1;
4,6,2;
8,22,20,5;
16,66,107,70,14;

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

Cf. A001764, A000079, A000108, A127536, A127529, A127532.

eq:=(2*t-1-t^2+2*z-t*z)*G^3-(2+2*t*z-2*t-5*z)*G^2+(4*z-t*z-1)*G+z: g:=RootOf(eq,G): gser:=simplify(series(g,z=0,14)): for n from 1 to 11 do P[n]:=sort(expand(coeff(gser,z,n))) od: for n from 1 to 11 do seq(coeff(P[n],t,j),j=0..n-1) od; # yields sequence in triangular form

G.f.: G=G(t,z) is given by (2t-1-t^2+2z-tz)G^3-(2+2tz-2t-5z)G^2+(4z-tz-1)G+z=0.
Sum of terms in row n = C(3n,n)/(2n+1) (A001764).
T(n,0)=2^(n-1) (A000079).
T(n+1,n)=C(2n,n)/(n+1) (A000108, the Catalan numbers).
Sum(k*T(n,k),0<=k<=n-1)=A127536(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula