cp's OEIS Frontend

A057112 Sequence of 719 adjacent transpositions (a[n] a[n]+1), which, when starting from the identity permutation and applied successively, produce a Hamiltonian circuit/path through all 720 permutations of S_6, in such a way that S_{n-1} is always traversed before the rest of S_n.

%I A057112 #17 Jun 12 2021 23:35:16
%S A057112 1,2,1,2,1,3,1,2,3,2,1,2,3,2,1,2,3,1,3,2,3,2,3,4,1,2,1,2,1,3,1,2,3,2,
%T A057112 1,2,3,2,1,2,3,1,3,2,3,2,3,4,1,2,1,2,1,3,1,2,3,2,1,2,3,2,1,2,3,1,3,2,
%U A057112 3,2,3,4,1,2,1,2,1,3,1,2,3,2,1,2,3,2,1,2,3,1,3,2,3,2,3,4,1,2,1,2,1,3,1,2,3,2,1,2,3,2,1,2,3,1,3,2,3,2,3
%N A057112 Sequence of 719 adjacent transpositions (a[n] a[n]+1), which, when starting from the identity permutation and applied successively, produce a Hamiltonian circuit/path through all 720 permutations of S_6, in such a way that S_{n-1} is always traversed before the rest of S_n.
%C A057112 If the 120 permutations of S_5 are connected by adjacent transpositions, the graph produced is isomorphic to the prismatodecachoron (a 4-dimensional polytope) graph (see the Olshevsky link) and this sequence gives directions for a Hamiltonian circuit through its vertices. The first 24 terms give a Hamiltonian path through truncated octahedron's graph (the last path shown in the Karttunen link).
%C A057112 Comment from _N. J. A. Sloane_: This is the subject of "bell-ringing" or "change-ringing", which has been studied for hundreds of years. See for example Amer. Math. Monthly, Vol. 94, Number 8, 1987, pp. 721-.
%H A057112 Georg Fischer, <a href="/A057112/b057112.txt">Table of n, a(n) for n = 1..719</a>
%H A057112 A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/permgraf/troctahe.htm">Truncated octahedron</a>
%H A057112 G. Olshevsky, <a href="http://members.aol.com/Polycell/section1.html">Great prismatodecachoron</a>
%H A057112 Arthur T. White, <a href="https://www.jstor.org/stable/2323414">Ringing the Cosets</a>, Amer. Math. Monthly, Vol. 94, Number 8, 1987, pp. 721-746.
%H A057112 <a href="/index/Be#bell_ringing">Index entries for sequences related to bell ringing</a>
%F A057112 tp_seq := [seq(adj_tp_seq(n), n=1..719)];
%e A057112 Starting from the identity permutation and applying these transpositions (from right), we get:
%e A057112 [1,2,3,4,5,6,...] o (1 2) ->
%e A057112 [2,1,3,4,5,6,...] o (2 3) ->
%e A057112 [2,3,1,4,5,6,...] o (1 2) ->
%e A057112 [3,2,1,4,5,6,...] o (2 1) ->
%e A057112 [3,1,2,4,5,6,...] o (1 2) ->
%e A057112 [1,3,2,4,5,6,...] o (3 4) ->
%e A057112 [1,3,4,2,5,6,...] o (1 2) ->
%e A057112 [3,1,4,2,5,6,...] o (2 3) ->
%e A057112 [3,4,1,2,5,6,...] o (3 4) etc.
%p A057112 adj_tp_seq := proc(n) local fl,fd,v; fl := fac_base(n); fd := fl[1]; if((1 = fd) and (0 = convert(cdr(fl),`+`))) then RETURN(nops(fl)); fi; if(n < 6) then RETURN(2 - (`mod`(n,2))); fi; if((0 = convert(cdr(fl),`+`)) and (n < 24)) then RETURN((nops(fl)+1)-fd); fi; if(n < 18) then if(0 = (`mod`(n,2))) then RETURN(2); else RETURN(4-(`mod`(n,4))); fi; else if(n < 24) then RETURN(2+(`mod`(n,2))); else if(n < 120) then if(0 = convert(cdr(fl),`+`)) then RETURN(nops(fl)); else RETURN(adj_tp_seq(`mod`(n,24))); fi; else if(n < 720) then if(125 = n) then RETURN(5); fi; v := (`mod`(n,5)); if(0 = v) then v := (n-125)/5; RETURN(adj_tp_seq(v)+(`mod`(v+1,2))); else if(5 > (`mod`(n,10))) then RETURN(5-v); else RETURN(v); fi; fi; else if(0 = convert(cdr(fl),`+`)) then RETURN(nops(fl)); fi; RETURN(adj_tp_seq(`mod`(n,720))); fi; fi; fi; fi; end;
%Y A057112 Cf. A057113, A055089 (for the Maple definitions of fac_base and cdr), A060135 (palindromic variant of the same idea).
%K A057112 nonn,fini,full
%O A057112 1,2
%A A057112 _Antti Karttunen_, Aug 09 2000