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

3, 13, 49, 185, 713, 2793, 11049, 43945, 175273, 700073, 2798249, 11188905, 44747433, 178973353, 715860649, 2863377065, 11453377193, 45813246633, 183252462249, 733008800425, 2932033104553, 11728128223913, 46912504507049, 187650001250985, 750599971449513, 3002399818689193, 12009599140539049

Offset: 1

Author

Dhruv Matani, Dec 07 2014

Keywords

• nonn

Examples

			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.
		

Programs

Python

def nc2(n):
    return n * (n-1) // 2
def numAdjacentNodes(levels):
    ret = 0
    for level in range(1, levels+1):
        ret += ((1 << level) + nc2(1 << level))
    return ret
for height in range(1, 33):
    print(numAdjacentNodes(height), end=', ')

Formula

Conjectures from Colin Barker, Dec 09 2014: (Start)

a(n) = (3*2^n+2^(1+2*n)-5)/3.

a(n) = 6*a(n-1)-7*a(n-2)-6*a(n-3)+8*a(n-4).

G.f.: x*(8*x-3) / ((x-1)*(2*x-1)*(4*x-1)).

(End)