%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