%I #31 Sep 02 2024 00:19:29
%S 0,0,1,5,14,102,603,4227,24942,311276,3039543,33478363,401734770,
%T 5222553212,73115744891,1096736173379,12943332326750,305107217238968,
%U 5362734402377967,102024181104606979,2040455253185256114,42849570085332342072,942690540710286167499,21681882436603204659939
%N Steinhaus-Johnson-Trotter rank of 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 Permutations are ranked here starting from 0 for the first permutation of n elements.
%C 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 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_trotterjohnson">Permutations</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm">Trotter algorithm</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_trotterjohnson()
%o print([a(n) for n in range(0, 27)])
%Y Cf. A003422, A207324, A375825.
%K nonn
%O 0,4
%A _DarĂo Clavijo_, Feb 07 2024