Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #17 Jun 12 2021 23:35:16
%S 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 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 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 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 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 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 Georg Fischer, <a href="/A057112/b057112.txt">Table of n, a(n) for n = 1..719</a>
%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/permgraf/troctahe.htm">Truncated octahedron</a>
%H G. Olshevsky, <a href="http://members.aol.com/Polycell/section1.html">Great prismatodecachoron</a>
%H 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 <a href="/index/Be#bell_ringing">Index entries for sequences related to bell ringing</a>
%F tp_seq := [seq(adj_tp_seq(n), n=1..719)];
%e Starting from the identity permutation and applying these transpositions (from right), we get:
%e [1,2,3,4,5,6,...] o (1 2) ->
%e [2,1,3,4,5,6,...] o (2 3) ->
%e [2,3,1,4,5,6,...] o (1 2) ->
%e [3,2,1,4,5,6,...] o (2 1) ->
%e [3,1,2,4,5,6,...] o (1 2) ->
%e [1,3,2,4,5,6,...] o (3 4) ->
%e [1,3,4,2,5,6,...] o (1 2) ->
%e [3,1,4,2,5,6,...] o (2 3) ->
%e [3,4,1,2,5,6,...] o (3 4) etc.
%p 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 Cf. A057113, A055089 (for the Maple definitions of fac_base and cdr), A060135 (palindromic variant of the same idea).
%K nonn,fini,full
%O 1,2
%A _Antti Karttunen_, Aug 09 2000