

A286778


Sum of the common path length over all 2tuples of nodes in a complete binary tree of height n.


1



0, 2, 22, 142, 734, 3390, 14718, 61694, 253438, 1029118, 4151294, 16683006, 66904062, 267993086, 1072791550, 4292935678, 17175543806, 68710301694, 274858508286, 1099470733310, 4397960527870, 17592005689342, 70368366690302, 281474188181502, 1125898262675454, 4503596204818430, 18014391395942398
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Let the height of the binary tree be one less than the number of rows; i.e., a complete binary tree of height 2 has one root node, its two descends and four leaf nodes. Any node u has a unique path to the root of the binary tree. Let h(u,v) be the length of the intersection of these paths for nodes u and v. Then a(n) is defined to be the sum of h(u,v) over all ordered 2tuples of nodes in a binary tree of height n.
Also the sum over all 2tuples of nodes of the depth of their last common ancestor in the tree. Defined in this way and denoted Q(T) in the Janson link.
Let z(v) be the number of nodes in the subtree rooted at node v (so if u is the root z(u) is the number of nodes in the tree). Then a(n) is also the sum of squares of the z(v) over all nonroot nodes v in the tree.


LINKS

Colin Barker, Table of n, a(n) for n = 0..1000
Svante Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (2003), no. 4, 337358. DOI: 10.1002/rsa.10074.
Index entries for linear recurrences with constant coefficients, signature (9,28,36,16).


FORMULA

a(n) = Sum_(d=1..n} 2^d*(2^(n+1d)1)^2.
From Robert Israel, Jul 05 2017: (Start)
a(n) = 4*2^(2*n)  (4*n+2)*2^n  2.
G.f.: 2*x*(2*x+1)/(19*x+28*x^236*x^3+16*x^4).
E.g.f.: 4*exp(4*x)(8*x+2)*exp(2*x)2*exp(x).
(End)
a(n) = 9*a(n1)  28*a(n2) + 36*a(n3)  16*a(n4) for n>3.  Colin Barker, Jul 05 2017


EXAMPLE

A complete binary tree of height two consists of one root node (at depth 0), two children of the root (at depth 1) and four leaf nodes (at depth 2). Notice the common path length of node u with itself, h(u,u), is simply the depth of u.
The only 2tuples to have common path length two is a leaf with itself (4 such tuples). Each child of the root with itself has common path length one (2 such tuples), as does each leaf with its sibling (4 such tuples) and each leaf with its parent (8 such tuples). All other 2tuples have only the root as a common ancestor. Hence a(2) = 2*4 + 1*(2 + 4 + 8) + 0 = 22.


MAPLE

seq( 4*2^(2*n)  (4*n+2)*2^n  2, n=0..30); # Robert Israel, Jul 05 2017


MATHEMATICA

LinearRecurrence[{9, 28, 36, 16}, {0, 2, 22, 142}, 40] (* Harvey P. Dale, Apr 30 2018 *)


PROG

(Sage)
print [sum([2^d*(2^(n+1d)1)^2 for d in range(1, n+1)]) for n in range(20)]
(PARI) a(n) = sum(d=1, n, 2^d*(2^(n+1d)1)^2); \\ Michel Marcus, Jul 05 2017
(PARI) concat(0, Vec(2*x*(1 + 2*x) / ((1  x)*(1  2*x)^2*(1  4*x)) + O(x^30))) \\ Colin Barker, Jul 05 2017


CROSSREFS

Cf. A036799 (total path length of a binary tree of height n).
Sequence in context: A084399 A067057 A202738 * A232977 A282819 A123960
Adjacent sequences: A286775 A286776 A286777 * A286779 A286780 A286781


KEYWORD

nonn,easy


AUTHOR

F. Skerman, Jul 05 2017


STATUS

approved



