cp's OEIS Frontend

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

%I A368783 #22 Jun 16 2025 19:17:15
%S A368783 0,0,1,2,15,82,402,2352,22113,220504,2329650,26780256,293266680,
%T A368783 3505934160,45390355920,633293015040,10873520709273,195823830637744,
%U A368783 3698406245739330,73192513664010816,1509611621730135000,32576548307761013760,734272503865161846480
%N A368783 Lexicographic rank of the permutation which is the Eytzinger array layout of n elements.
%C A368783 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 A368783 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 A368783 geeksforgeeks.org, <a href="https://www.geeksforgeeks.org/lexicographic-rank-string-duplicate-characters">Lexicographic rank of a String</a>
%H A368783 Sergey Slotin, <a href="https://algorithmica.org/en/eytzinger">Eytzinger binary search</a>
%H A368783 sympy.org, <a href="https://docs.sympy.org/latest/modules/combinatorics/permutations.html#sympy.combinatorics.permutations.Permutation.rank">Permutation rank</a>
%o A368783 (Python)
%o A368783 from sympy.combinatorics.permutations import Permutation
%o A368783 def a(n):
%o A368783   if n == 0: return 0
%o A368783   def eytzinger(t, k=1, i=0):
%o A368783     if (k < len(t)):
%o A368783       i = eytzinger(t, k * 2, i)
%o A368783       t[k] = i
%o A368783       i += 1
%o A368783       i = eytzinger(t, k * 2 + 1, i)
%o A368783     return i
%o A368783   t = [0] * (n+1)
%o A368783   eytzinger(t)
%o A368783   return Permutation(t[1:]).rank()
%o A368783 print([a(n) for n in range(0, 24)])
%Y A368783 Cf. A030298, A369802, A370006, A375825.
%K A368783 nonn
%O A368783 0,4
%A A368783 _Darío Clavijo_, Feb 15 2024