cp's OEIS Frontend

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

%I A286778 #60 Aug 26 2025 06:13:05
%S A286778 0,2,22,142,734,3390,14718,61694,253438,1029118,4151294,16683006,
%T A286778 66904062,267993086,1072791550,4292935678,17175543806,68710301694,
%U A286778 274858508286,1099470733310,4397960527870,17592005689342,70368366690302,281474188181502,1125898262675454,4503596204818430,18014391395942398
%N A286778 Sum of the common path length over all 2-tuples of nodes in a complete binary tree of height n.
%C A286778 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 2-tuples of nodes in a binary tree of height n.
%C A286778 Also the sum over all 2-tuples 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.
%C A286778 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 non-root nodes v in the tree.
%H A286778 Colin Barker, <a href="/A286778/b286778.txt">Table of n, a(n) for n = 0..1000</a>
%H A286778 Svante Janson, <a href="http://www2.math.uu.se/~svante/papers/sj146.pdf">The Wiener index of simply generated random trees</a>, Random Structures Algorithms 22 (2003), no. 4, 337-358. DOI: 10.1002/rsa.10074.
%H A286778 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (9,-28,36,-16).
%F A286778 a(n) = Sum_{d=1..n} 2^d*(2^(n+1-d)-1)^2.
%F A286778 From _Robert Israel_, Jul 05 2017: (Start)
%F A286778 a(n) = 4*2^(2*n) - (4*n+2)*2^n - 2.
%F A286778 G.f.: 2*x*(2*x+1)/((4*x-1)*(x-1)*(2*x-1)^2).
%F A286778 E.g.f.: 4*exp(4*x)-(8*x+2)*exp(2*x)-2*exp(x).
%F A286778 (End)
%F A286778 a(n) = 9*a(n-1) - 28*a(n-2) + 36*a(n-3) - 16*a(n-4) for n>3. - _Colin Barker_, Jul 05 2017
%F A286778 a(n)-a(n-1) = A050488(n)*2^n . - _R. J. Mathar_, Aug 26 2025
%e A286778 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.
%e A286778 The only 2-tuples 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 2-tuples have only the root as a common ancestor. Hence a(2) = 2*4 + 1*(2 + 4 + 8) + 0 = 22.
%p A286778 seq( 4*2^(2*n) - (4*n+2)*2^n - 2, n=0..30); # _Robert Israel_, Jul 05 2017
%t A286778 LinearRecurrence[{9,-28,36,-16},{0,2,22,142},40] (* _Harvey P. Dale_, Apr 30 2018 *)
%o A286778 (Sage)
%o A286778 [sum(2^d*(2^(n+1-d)-1)^2 for d in range(1,n+1)) for n in range(20)]
%o A286778 (PARI) a(n) = sum(d=1, n, 2^d*(2^(n+1-d)-1)^2); \\ _Michel Marcus_, Jul 05 2017
%o A286778 (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
%Y A286778 Cf. A036799 (total path length of a binary tree of height n).
%K A286778 nonn,easy,changed
%O A286778 0,2
%A A286778 _F. Skerman_, Jul 05 2017