cp's OEIS Frontend

A251743 Pairs of nodes in a complete binary tree that are at an absolute height difference of less than 2 from each other.

%I A251743 #24 May 30 2025 11:10:49
%S A251743 3,13,49,185,713,2793,11049,43945,175273,700073,2798249,11188905,
%T A251743 44747433,178973353,715860649,2863377065,11453377193,45813246633,
%U A251743 183252462249,733008800425,2932033104553,11728128223913,46912504507049,187650001250985,750599971449513,3002399818689193,12009599140539049
%N A251743 Pairs of nodes in a complete binary tree that are at an absolute height difference of less than 2 from each other.
%F A251743 Conjectures from _Colin Barker_, Dec 09 2014: (Start)
%F A251743 a(n) = (3*2^n+2^(1+2*n)-5)/3.
%F A251743 a(n) = 6*a(n-1)-7*a(n-2)-6*a(n-3)+8*a(n-4).
%F A251743 G.f.: x*(8*x-3) / ((x-1)*(2*x-1)*(4*x-1)).
%F A251743 (End)
%e A251743 For a complete binary tree with 2 levels (root, level-1, level-2), the total number of node pairs is 7 choose 2 = 21, whereas the number of node pairs that are at levels which are at an absolute difference of less than 2 from each other are 13.
%o A251743 (Python)
%o A251743 def nc2(n):
%o A251743     return n * (n-1) // 2
%o A251743 def numAdjacentNodes(levels):
%o A251743     ret = 0
%o A251743     for level in range(1, levels+1):
%o A251743         ret += ((1 << level) + nc2(1 << level))
%o A251743     return ret
%o A251743 for height in range(1, 33):
%o A251743     print(numAdjacentNodes(height), end=', ')
%K A251743 nonn
%O A251743 1,1
%A A251743 _Dhruv Matani_, Dec 07 2014