cp's OEIS Frontend

A370006 Steinhaus-Johnson-Trotter rank of the Eytzinger array layout of n elements.

%I A370006 #31 Sep 02 2024 00:19:29
%S A370006 0,0,1,5,14,102,603,4227,24942,311276,3039543,33478363,401734770,
%T A370006 5222553212,73115744891,1096736173379,12943332326750,305107217238968,
%U A370006 5362734402377967,102024181104606979,2040455253185256114,42849570085332342072,942690540710286167499,21681882436603204659939
%N A370006 Steinhaus-Johnson-Trotter rank of the Eytzinger array layout of n elements.
%C A370006 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 A370006 Permutations are ranked here starting from 0 for the first permutation of n elements.
%C A370006 A207324 is all permutations in Steinhaus-Johnson-Trotter order, so that its row number !n + a(n) is the Eytzinger array of n elements, for n>=1 and where !n = A003422(n) is the left factorial.
%H A370006 Sergey Slotin, <a href="https://algorithmica.org/en/eytzinger">Eytzinger binary search</a>
%H A370006 sympy.org, <a href="https://docs.sympy.org/latest/modules/combinatorics/permutations.html#sympy.combinatorics.permutations.Permutation.rank_trotterjohnson">Permutations</a>
%H A370006 Wikipedia, <a href="https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm">Trotter algorithm</a>
%o A370006 (Python)
%o A370006 from sympy.combinatorics.permutations import Permutation
%o A370006 def a(n):
%o A370006   def eytzinger(t, k=1, i=0):
%o A370006     if (k < len(t)):
%o A370006       i = eytzinger(t, k * 2, i)
%o A370006       t[k] = i
%o A370006       i += 1
%o A370006       i = eytzinger(t, k * 2 + 1, i)
%o A370006     return i
%o A370006   t = [0] * (n+1)
%o A370006   eytzinger(t)
%o A370006   return Permutation(t[1:]).rank_trotterjohnson()
%o A370006 print([a(n) for n in range(0, 27)])
%Y A370006 Cf. A003422, A207324, A375825.
%K A370006 nonn
%O A370006 0,4
%A A370006 _Darío Clavijo_, Feb 07 2024