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,1

Links

Table of n, a(n) for n=1..27.

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)

Example

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.

Prog

(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)

Crossrefs

Sequence in context: A352028 A048482 A094978 * A178934 A218420 A241775

Adjacent sequences: A251740 A251741 A251742 * A251744 A251745 A251746

Keyword

nonn

Author

Dhruv Matani, Dec 07 2014

Status

approved