Journal of Integer Sequences, Vol. 14 (2011), Article 11.3.2

On the Permutations Generated by Cyclic Shift

Stéphane Legendre
Team of Mathematical Eco-Evolution
Ecole Normale Supérieure
75005 Paris

Philippe Paclet
Lycée Chateaubriand
00161 Roma


The set of permutations generated by cyclic shift is studied using a number system coding for these permutations. The system allows to find the rank of a permutation given how it has been generated, and to determine a permutation given its rank. It defines a code describing structural and symmetry properties of the set of permutations ordered according to generation by cyclic shift. The code is associated with an Hamiltonian cycle in a regular weighted digraph. This Hamiltonian cycle is conjectured to be of minimal weight, leading to a combinatorial Gray code listing the set of permutations.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000142 A001511 A007489 A033312.)

Received September 21 2010; revised version received December 13 2010; February 14 2011. Published in Journal of Integer Sequences, March 25 2011.

Return to Journal of Integer Sequences home page