OFFSET
0,4
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
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
KEYWORD
nonn
AUTHOR
Darío Clavijo, Feb 15 2024
STATUS
approved