cp's OEIS Frontend

A369802 Inversion count of the Eytzinger array layout of n elements.

%I A369802 #29 Sep 02 2024 00:19:35
%S A369802 0,0,1,1,4,6,7,7,14,20,25,29,32,34,35,35,50,64,77,89,100,110,119,127,
%T A369802 134,140,145,149,152,154,155,155,186,216,245,273,300,326,351,375,398,
%U A369802 420,441,461,480,498,515,531,546,560,573,585,596,606,615,623,630
%N A369802 Inversion count of the Eytzinger array layout of n elements.
%C A369802 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.
%C A369802 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.
%H A369802 Sergey Slotin, <a href="https://algorithmica.org/en/eytzinger">Eytzinger binary search</a>
%F A369802 a(2^n-1) = A006095(n).
%F A369802 Conjecture: a(n) = (A261692(n)-n)/2.
%e A369802 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).
%o A369802 (Python)
%o A369802 from sympy.combinatorics.permutations import Permutation
%o A369802 def a(n):
%o A369802   def eytzinger(t, k=1, i=0):
%o A369802     if (k < len(t)):
%o A369802       i = eytzinger(t, k * 2, i)
%o A369802       t[k] = i
%o A369802       i += 1
%o A369802       i = eytzinger(t, k * 2 + 1, i)
%o A369802     return i
%o A369802   t = [0] * (n+1)
%o A369802   eytzinger(t)
%o A369802   return Permutation(t[1:]).inversions()
%o A369802 print([a(n) for n in range(0, 58)])
%Y A369802 Cf. A006095, A261692, A375825.
%K A369802 nonn
%O A369802 0,5
%A A369802 _Darío Clavijo_, Feb 01 2024