A369802 - OEIS

A369802

Inversion count of the Eytzinger array layout of n elements.

0, 0, 1, 1, 4, 6, 7, 7, 14, 20, 25, 29, 32, 34, 35, 35, 50, 64, 77, 89, 100, 110, 119, 127, 134, 140, 145, 149, 152, 154, 155, 155, 186, 216, 245, 273, 300, 326, 351, 375, 398, 420, 441, 461, 480, 498, 515, 531, 546, 560, 573, 585, 596, 606, 615, 623, 630

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

The Eytzinger array layout (A375825) arranges elements so that a binary search can be performed starting at element k=1 and at a given k step to 2*k or 2*k+1 according as the target is smaller or larger than the element at k.

This layout is a permutation of the elements and its inversion count (number of swaps needed to sort by the bubble sort algorithm) is a measure of how much it differs from an ordinary sorted array.

LINKS

Table of n, a(n) for n=0..56.

Sergey Slotin, Eytzinger binary search

FORMULA

a(2^n-1) = A006095(n).

Conjecture: a(n) = (A261692(n)-n)/2.

EXAMPLE

For n=5, the Eytzinger array layout is {4, 2, 5, 1, 3} and it contains a(5) = 6 element pairs which are not in ascending order (out of 10 element pairs altogether).

PROG

(Python)

from sympy.combinatorics.permutations import Permutation

def a(n):

def eytzinger(t, k=1, i=0):

if (k < len(t)):

i = eytzinger(t, k * 2, i)

t[k] = i

i += 1

i = eytzinger(t, k * 2 + 1, i)

return i

t = [0] * (n+1)