A368783 Lexicographic rank of the permutation which is the Eytzinger array layout of n elements.

0, 0, 1, 2, 15, 82, 402, 2352, 22113, 220504, 2329650, 26780256, 293266680, 3505934160, 45390355920, 633293015040, 10873520709273, 195823830637744, 3698406245739330, 73192513664010816, 1509611621730135000, 32576548307761013760, 734272503865161846480

Offset: 0

Author

Darío Clavijo, Feb 15 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.

The lexicographic rank of a permutation of n elements is its position in the ordered list of all possible permutations of n elements, and here taking the first permutation as rank 0.

Links

• geeksforgeeks.org, Lexicographic rank of a String
• Sergey Slotin, Eytzinger binary search
• sympy.org, Permutation rank

Crossrefs

Cf. A030298, A369802, A370006, A375825.

Programs

Python

from sympy.combinatorics.permutations import Permutation
def a(n):
  if n == 0: return 0
  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()
print([a(n) for n in range(0, 24)])