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,4

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.

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

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

geeksforgeeks.org, Lexicographic rank of a String

Sergey Slotin, Eytzinger binary search

sympy.org, Permutation rank

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

Crossrefs

Cf. A030298, A369802, A370006.

Sequence in context: A036239 A268735 A215705 * A301566 A109725 A057152

Adjacent sequences: A368780 A368781 A368782 * A368784 A368785 A368786

Keyword

nonn

Author

Darío Clavijo, Feb 15 2024

Status

approved