|
|
A369802
|
|
Inversion count of the Eytzinger array layout of n elements.
|
|
1
|
|
|
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 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
|
|
|
FORMULA
|
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)
eytzinger(t)
return Permutation(t[1:]).inversions()
print([a(n) for n in range(0, 58)])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|