A370006 Steinhaus-Johnson-Trotter rank of the Eytzinger array layout of n elements.

0, 0, 1, 5, 14, 102, 603, 4227, 24942, 311276, 3039543, 33478363, 401734770, 5222553212, 73115744891, 1096736173379, 12943332326750, 305107217238968, 5362734402377967, 102024181104606979, 2040455253185256114, 42849570085332342072, 942690540710286167499, 21681882436603204659939

Offset: 0

Author

Darío Clavijo, Feb 07 2024

Keywords

• nonn

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.

Permutations are ranked here starting from 0 for the first permutation of n elements.

A207324 is all permutations in Steinhaus-Johnson-Trotter order, so that its row number !n + a(n) is the Eytzinger array of n elements, for n>=1 and where !n = A003422(n) is the left factorial.

Links

• Sergey Slotin, Eytzinger binary search
• sympy.org, Permutations
• Wikipedia, Trotter algorithm

Crossrefs

Cf. A003422, A207324, A375825.

Programs

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:]).rank_trotterjohnson()
print([a(n) for n in range(0, 27)])