A368783 - OEIS

%I #19 Sep 01 2024 19:46:55

%S 0,0,1,2,15,82,402,2352,22113,220504,2329650,26780256,293266680,

%T 3505934160,45390355920,633293015040,10873520709273,195823830637744,

%U 3698406245739330,73192513664010816,1509611621730135000,32576548307761013760,734272503865161846480

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

%C 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 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.

%H geeksforgeeks.org, <a href="https://www.geeksforgeeks.org/lexicographic-rank-string-duplicate-characters">Lexicographic rank of a String</a>

%H Sergey Slotin, <a href="https://algorithmica.org/en/eytzinger">Eytzinger binary search</a>

%H sympy.org, <a href="https://docs.sympy.org/latest/modules/combinatorics/permutations.html#sympy.combinatorics.permutations.Permutation.rank">Permutation rank</a>

%o (Python)

%o from sympy.combinatorics.permutations import Permutation

%o def a(n):

%o   def eytzinger(t, k=1, i=0):

%o     if (k < len(t)):

%o       i = eytzinger(t, k * 2, i)

%o       t[k] = i

%o       i += 1

%o       i = eytzinger(t, k * 2 + 1, i)

%o     return i

%o   t = [0] * (n+1)

%o   eytzinger(t)

%o   return Permutation(t[1:]).rank()

%o print([a(n) for n in range(0, 24)])

%Y Cf. A030298, A369802, A370006, A375825.

%K nonn

%O 0,4

%A _Darío Clavijo_, Feb 15 2024