On the Permutations Generated by Cyclic Shift

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

                    legendre@ens.fr

Philippe Paclet Lycée Chateaubriand 00161 Roma Italy

                    paclet@dada.it

Abstract

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.

1 Introduction

It is well known that any natural integer a can be written uniquely in the factorial number system

a = ∑_{i=1}^{n−1} a_{i} i!, a_{i} ∈ {0, …, i},

where the uniqueness of the representation comes from the identity

∑_{i=1}^{n−1} i · i! = n! − 1.  (1)

Charles-Ange Laisant showed in 1888 [2] that the factorial number system codes the permutations generated in lexicographic order. More precisely, when the set of permutations is ordered lexicographically, the rank of a permutation written in the factorial number system provides a code determining the permutation. The code specifies which interchanges of the symbols according to lexicographic order have to be performed to generate the permutation.

In this study, a lesser-known number system on the finite ring ℤ_{n!} is used to describe properties of the set S_{n} of permutations on n symbols generated by cyclic shift. When S_{n} is ordered according to generation by cyclic shift, the rank of a permutation written in this number system entirely specifies how the permutation is generated.

This number system is a special case of a large class of methods presented by Knuth [1, §7.2.1.2] for generating S_{n}. Here, an explicit and self-contained description is given.

Example 1. As will be shown, any number α in ℤ_{5!} can be written uniquely

α = α_{3}ϖ_{5,3} + α_{2}ϖ_{5,2} + α_{1}ϖ_{5,1} + α_{0}ϖ_{5,0}

with the digits

α_{3} ∈ ℤ_{2}, α_{2} ∈ ℤ_{3}, α_{1} ∈ ℤ_{4}, α_{0} ∈ ℤ_{5},

and the base elements

ϖ_{5,3} = 3 · 4 · 5 = 60, ϖ_{5,2} = 4 · 5 = 20, ϖ_{5,1} = 5, ϖ_{5,0} = 1.

For example,

84 = 1 · 60 + 1 · 20 + 0 · 5 + 4 · 1 = 1104_{ϖ}.

We use the digits of 1104_{ϖ} to generate by cyclic shift a permutation on 5 symbols. The generation scheme is

(1) ⟶^{α_{3}=1} (21) ⟶^{α_{2}=1} (132) ⟶^{α_{1}=0} (1324) ⟶^{α_{0}=4} (51324),

and is established as follows. The orbit of the permutation (1) under cyclic shift is

\begin{matrix}0 : & (12) \\ 1 : & \underline{(21)}. \end{matrix}

We select the permutation (21) whose exponent of the cyclic shift is the leftmost digit α_{3} = 1. Next, the orbit of (21) under cyclic shift is

\begin{matrix}0 : & (213) \\ 1 : & \underline{(132)} \\ 2 : & (321). \end{matrix}

The digit α_{2} = 1 leads to (132). Next, the orbit of (132) under cyclic shift is

\begin{matrix}0 : & \underline{(1324)} \\ 1 : & (3241) \\ 2 : & (2413) \\ 3 : & (4132). \end{matrix}

The digit α_{1} = 0 leads to (1324). Finally, the last digit α_{0} = 4 leads to (51324). This permutation has rank 1104_{ϖ} = 84 in the set of permutations on 5 symbols generated by cyclic shift, indexed from 0.

We shall describe properties of S_{n} generated by cyclic shift:

1. A decomposition into k-orbits;

2. The symmetries;

3. An infinite family of regular digraphs associated with {S_{n}; n ≥ 1};

4. A conjectured combinatorial Gray code generating the permutations on n symbols. The adjacency rule associated with this code is that the last symbols of each permutation match the first symbols of the next optimally.

2 Number system

For any positive integer a, the ring (ℤ/aℤ, +, ×) of integers modulo a is denoted ℤ_{a}. The set ℤ_{a} is identified with a subset of the set ℕ of natural integers.

Proposition 2. For n ≥ 2, any element α ∈ ℤ_{n!} can be uniquely represented as

α = ∑_{i=0}^{n−2} α_{i}ϖ_{n,i}, α_{i} ∈ ℤ_{n−i},

with the base elements

ϖ_{n,0} = 1,  ϖ_{n,i} = n(n − 1) ⋯ (n − i + 1),  i = 1, …, n − 2.

The α_{i}’s are the digits of α in this number system, which we call the ϖ-system for short. Any element of ℤ_{n!} can be written uniquely

α = α_{n−2} ⋯ α_{1}α_{0}_{ϖ}.

Unless α_{n−2} = 1, the leftmost digits are set to 0, so that the representation always involves n − 1 elements, indexed 0, …, n − 2.

Proof. For simplicity, we momentarily denote ϖ_{i} = ϖ_{n,i}. For n = 2, there is a single base element, ϖ_{0} = 1, and the result clearly holds. For n ≥ 3, and α ∈ ℤ_{n!}, we set

α^{(0)} = α,
α_{i} = α^{(i)} mod (n − i), α^{(i+1)} = α^{(i)} div (n − i), i = 0, …, n − 2,

where div denotes integer division. These relations imply

α^{(i)} = (n − i)α^{(i+1)} + α_{i}, i = 0, …, n − 2.

We multiply by ϖ_{i} on both sides. For i = 0, …, n − 3, we use the identity

ϖ_{i+1} = (n − i)ϖ_{i},  (2)

and for i = n − 2, we use the identity 2ϖ_{n−2} = 0 in ℤ_{2}, to get

\begin{aligned}ϖ_{i}α^{(i)} − ϖ_{i+1}α^{(i+1)} & = & α_{i}ϖ_{i}, i = 0, …, n − 3, \\ ϖ_{n−2}α^{(n−2)} & = & α_{n−2}ϖ_{n−2}. \end{aligned}

Adding these relations together, and accounting for telescoping cancellation on the left side,

ϖ_{0}α^{(0)} = α_{n−2}ϖ_{n−2} + ⋯ + α_{0}ϖ_{0}.

As and α^{(0)} = α, we obtain the representation

α = α_{n−2}ϖ_{n−2} + ⋯ + α_{0}ϖ_{0}.

By construction, α_{i} ∈ ℤ_{n−i} for i = 0, …, n − 2. The existence of the decomposition also holds in ℕ.

We now prove the uniqueness of the decomposition in ℕ, and momentarily introduce the element ϖ_{n−1} = n!. In ℕ, the identities

∑_{i=0}^{k−1}(n − i − 1)ϖ_{i} = ϖ_{k} − 1, k ∈ {1, … n − 1}  (3)

are easily shown using induction and (2) (such identities are general to mixed radix number systems). Assume that α ∈ ℕ has two different decompositions. Then, with obvious notations,

∑_{i=0}^{n−2}(α_{i} − α′_{i})ϖ_{i} = 0.  (4)

Let k be the largest index such that α_{i} ≠ α′_{i}. If k = 0, then α_{0} ≠ α′_{0} and α_{i} = α′_{i} for i > 0. From (4) we deduce α_{0} = α′_{0}, a contradiction. If k > 0, then

∑_{i=0}^{k−1}(α_{i} − α′_{i})ϖ_{i} = (α′_{k} − α_{k})ϖ_{k}.  (5)

We may assume α′_{k} > α_{k} with no loss of generality, so that the right hand term in (5) is larger than ϖ_{k}. As α_{i} and α′_{i} are less than n − i − 1, the left hand term is less than ϖ_{k} − 1 by (3), a contradiction. The uniqueness of the decomposition also holds in ℤ_{n!}.

Arithmetics can be performed in the ring (ℤ_{n!}, +, ×) endowed with the ϖ-system. The computation of the sum and product works in the usual way of positional number systems, using the ring structure of ℤ_{n−i} for the operations on the digits of the operands. There is no carry to propagate after the leftmost digit.

Lemma 3. The base elements verify

ϖ_{n,i+k} = ϖ_{n−k,i}ϖ_{n,k},  (6)

∑_{i=0}^{k−1}(n − i − 1)ϖ_{n,i} = ϖ_{n,k} − 1, k ∈ {1, … n − 2},  (7)

∑_{i=0}^{n−2}(n − i − 1)ϖ_{n,i} = −1.  (8)

Proof. The verification of the first relation is straightforward. The identities (3) written in ℤ_{n!} give (7) and (8). For (8), we use the fact that n! − 1 = −1 in ℤ_{n!}.

Corollary 4. For α, α′ ∈ ℤ_{n!}, with digits α_{i}, α′_{i} ∈ ℤ_{n−i},

α + α′ = −1 ⟺ α_{i} + α′_{i} = −1, i = 0, …, n − 2.

Proof. We write

α + α′ = ∑_{i=0}^{n−2}(α_{i} + α′_{i})ϖ_{n,i}.

In ℤ_{n−i}, α_{i}+α′_{i} = −1 if and only if α_{i}+α′_{i} = n−i−1. By the uniqueness of the decomposition in the ϖ-system, the result follows from (8).

3 Code

The set of permutations on n symbols x_{1}, …, x_{n} is denoted S_{n}. From a permutation q on the n − 1 symbols x_{1}, …, x_{n−1}, n permutations on n symbols are generated by inserting x_{n} to the right and permuting the symbols cyclically. The insertion of x_{n} to the right defines an injection

\begin{matrix}S_{n−1} & ⟶^{ι} & S_{n} \\ q = (a_{1} ⋯ a_{n−1}) & ⟼ & (a_{1} ⋯ a_{n−1}x_{n}) = q̃. \end{matrix}

We define the cyclic shift S : S_{n−1} → S_{n} by S = Cι, where C : S_{n} → S_{n} is the circular permutation, so that

S^{0}q = (a_{1}a_{2} ⋯ a_{n−1}x_{n}) = C^{0}q̃ = q̃,
S^{1}q = (a_{2} ⋯ a_{n−1}x_{n}a_{1}) = C^{1}q̃,
⋮
S^{n−1}q = (x_{n}a_{1}a_{2} ⋯ a_{n−1}) = C^{n−1}q̃.

The set O(q) = {S^{0}q, …, S^{n−1}q} is the orbit of q. As S^{i} = S^{j} is equivalent to i = j mod n, the exponents of the cyclic shift are elements of ℤ_{n}.

Lemma 5. The set of permutations S_{n} is the disjoint union of the orbits O(q) for q ∈ S_{n−1}.

Proof. If q, r ∈ S_{n−1}, their orbits are disjoint subsets of S_{n}. Indeed, if S^{i}q = S^{j}r, there exists k ∈ ℤ_{n} such that S^{k}q = S^{0}r = r̃. The only possibility is k = 0, implying S^{0}q = q̃ = r̃, and q = r. There are (n − 1)! disjoint orbits, each of size n, so that they span S_{n}.

According to Lemma 5, the set S_{n} can be generated by cyclic shift. The generation by cyclic shift defines an order on the set of permutations, S_{n} = {p_{0}, …, p_{n!−1}}, a cyclic order in fact. For this order, the rank α of a permutation p_{α} ∈ S_{n} is an element of ℤ_{n!}.

The generation by cyclic shift of p ∈ S_{n} from (1) ∈ S_{1} can be schematized:

\{ \begin{matrix}p^{(1)} = (1) ⟶^{α_{n−2}} p^{(2)} ⟶ ⋯ ⟶^{α_{2}} p^{(n−2)} ⟶^{α_{1}} p^{(n−1)} ⟶^{α_{0}} p^{(n)} = p, \\ p^{(n−i)} = S_{n−i}^{α_{i}}p^{(n−i−1)}, \end{matrix} \}  (9)

where p^{(n−i)} ∈ S_{n−i} is generated from p^{(n−i−1)} ∈ S_{n−i−1} by the cyclic shift

S_{n−i} : S_{n−i−1} ⟶ S_{n−i}

with the exponent α_{i} ∈ ℤ_{n−i} (Example 1).

Definition 6. The sequence of exponents α_{i} ∈ ℤ_{n−i} associated with successive cyclic shifts leading from (1) ∈ S_{1} to p ∈ S_{n} is the code of p in the ϖ-system:

α = α_{n−2} ⋯ α_{0}_{ϖ} ∈ ℤ_{n!}.

Theorem 7. The rank of a permutation on n symbols generated by cyclic shift is given by its code. A permutation on n symbols generated by cyclic shift is determined by writing its rank in the ϖ-system.

Proof. We use induction on n. For n = 2, in S_{2} = {(12), (21)}, the rank of the permutation (12) is 0 = 0_{ϖ}, and the rank of the permutation (21) is 1 = 1_{ϖ}. For n > 2, let p = p_{α} ∈ S_{n} of rank α, generated by cyclic shift from q = q_{β} ∈ S_{n−1} of rank β. Then p = S_{n}^{α_{0}}q for some α_{0} ∈ ℤ_{n}, α_{0} being the rank of p within the orbit of q. As the orbits contain n elements and as β is the rank of q in S_{n−1}, the rank of p in S_{n} is

α = βn + α_{0} = βϖ_{n,1} + α_{0}ϖ_{n,0}.

By induction hypothesis, the rank β of q is given by the code

β = ∑_{i=0}^{n−3} β_{i}ϖ_{n−1,i}, β_{i} ∈ ℤ_{n−1−i}.

Eq. (6) gives, for k = 1,

ϖ_{n,i+1} = ϖ_{n−1,i}ϖ_{n,1},

so that

βϖ_{n,1} = ∑_{i=0}^{n−3} β_{i}ϖ_{n−1,i}ϖ_{n,1} = ∑_{i=0}^{n−3} β_{i}ϖ_{n,i+1} = ∑_{i=1}^{n−2} β_{i−1}ϖ_{n,i}.

Let α_{i} = β_{i−1} for i = 1, …, n − 2. As β_{i} ∈ ℤ_{n−1−i}, α_{i} ∈ ℤ_{n−i}. We obtain that

α = βϖ_{n,1} + α_{0}ϖ_{n,0} = ∑_{i=0}^{n−2} α_{i}ϖ_{n,i}, α_{i} ∈ ℤ_{n−i},

is the code of p_{α}. Conversely, let p_{α} ∈ S_{n}. We write the rank α in the ϖ-system, α = α_{n−2} ⋯ α_{0}_{ϖ}, and use scheme (9) with the exponents α_{n−2}, …, α_{0} to determine p_{α}.

\begin{matrix}α & p_{α} & α_{2} & α_{1} & α_{0} \\ 0 & 1234 & 0 & 0 & 0 \\ 1 & 2341 & 0 & 0 & 1 \\ 2 & 3412 & 0 & 0 & 2 \\ 3 & 4123 & 0 & 0 & 3 \\ 4 & 2314 & 0 & 1 & 0 \\ 5 & 3142 & 0 & 1 & 1 \\ 6 & 1423 & 0 & 1 & 2 \\ 7 & 4231 & 0 & 1 & 3 \\ 8 & 3124 & 0 & 2 & 0 \\ 9 & 1243 & 0 & 2 & 1 \\ 10 & 2431 & 0 & 2 & 2 \\ 11 & 4312 & 0 & 2 & 3 \\ 12 & 2134 & 1 & 0 & 0 \\ 13 & 1342 & 1 & 0 & 1 \\ 14 & 3421 & 1 & 0 & 2 \\ 15 & 4213 & 1 & 0 & 3 \\ 16 & 1324 & 1 & 1 & 0 \\ 17 & 3241 & 1 & 1 & 1 \\ 18 & 2413 & 1 & 1 & 2 \\ 19 & 4132 & 1 & 1 & 3 \\ 20 & 3214 & 1 & 2 & 0 \\ 21 & 2143 & 1 & 2 & 1 \\ 22 & 1432 & 1 & 2 & 2 \\ 23 & 4321 & 1 & 2 & 3 \end{matrix}

Table 1: The codes of the permutations of {1, 2, 3, 4} generated by cyclic shift.

Algorithm C in Knuth [1, §7.2.1.2] generates S_{n} by cyclic shift in a simple version of the scheme described in this section.

In the sequel, we assume that S_{n} is ordered according to generation by cyclic shift.

4 k-orbits

The ϖ-system is a family of number systems indexed by n, which are compatible in a sense precised in the next proposition. The compatibility relies on relation (6).

Proposition 8. Let k ∈ {0, …, n − 2} and p_{α} ∈ S_{n} with code α ∈ ℤ_{n!}. There exists a permutation q_{β} ∈ S_{n−k} with code β ∈ ℤ_{(n−k)!} such that

α = βϖ_{n,k} + γ, γ ∈ {0, …, ϖ_{n,k} − 1}.  (10)

The code β is made of the n − k − 1 leftmost digits of α, and γ is made of the k rightmost digits of α.

Proof. We have the decomposition

α = α_{n−2} ⋯ α_{0}_{ϖ} = α_{n−2} ⋯ α_{k}0 ⋯ 0_{ϖ} + 0 ⋯ 0α_{k−1} ⋯ α_{0}_{ϖ} = α̃ + γ.

Let β_{i} = α_{i+k} for i = 0, …, n − k − 2, so that the β’s are the n − k − 1 leftmost digits of α. As α_{i} ∈ ℤ_{n−i}, β_{i} = α_{i+k} ∈ ℤ_{n−k−i}. Hence

β = ∑_{i=0}^{n−k−2} β_{i}ϖ_{n−k,i}, β_{i} ∈ ℤ_{n−k−i},

is an element of ℤ_{(n−k)!} which is the code of a permutation q_{β} ∈ S_{n−k}. Using relation (6), we obtain

α̃ = ∑_{i=k}^{n−2} α_{i}ϖ_{n,i} = ∑_{i=0}^{n−k−2} α_{i+k}ϖ_{n,i+k} = ∑_{i=0}^{n−k−2} α_{i+k}ϖ_{n−k,i}ϖ_{n,k} = ( ∑_{i=0}^{n−k−2} β_{i}ϖ_{n−k,i}) ϖ_{n,k}.

The term

γ = ∑_{i=0}^{k−1} α_{i}ϖ_{n,i}

is made of the k rightmost digits of α. It is an element of ℤ_{n−k+1} × ⋯ × ℤ_{n} ranging from 0 to ∑_{i=0}^{k−1}(n − i − 1)ϖ_{n,i}, which equals ϖ_{n,k} − 1 by (7). We obtain

α = α̃ + γ = βϖ_{n,k} + γ.

Definition 9. For k ∈ {0, …, n − 2} and q_{β} ∈ S_{n−k}, the k-orbit of q_{β} is the following subset of S_{n}:

O_{n,k}(q_{β}) = {p_{α} ∈ S_{n}; α = βϖ_{n,k} + γ, γ = 0, …, ϖ_{n,k} − 1}.

For k = 0, the 0-orbit of q ∈ S_{n} is {q}. Indeed, for k = 0, ϖ_{n,0} = 1, γ = 0, and q = p_{α}. For k ≥ 1, a k-orbit O_{n,k}(q) can be described as the subset of S_{n} generated from q ∈ S_{n−k} by k successive cyclic shifts. Indeed, by Proposition 8, the code of p_{α} ∈ O_{n,k}(q_{β}) is obtained by appending α_{k−1} ⋯ α_{0} to the code β_{n−k−2} ⋯ β_{0}_{ϖ} of q_{β}. By scheme (9), the digits α_{k−1}, …, α_{0} describe the generation of p_{α} from q_{β}. In particular, for k = 1, the 1-orbit O_{n,1}(q) of q ∈ S_{n−1} is the orbit O(q). We may further define the (n − 1)-orbit O_{n,n−1}(q) as the whole set S_{n}, with q = (1) ∈ S_{1}.

We have the following generalization of Lemma 5:

Proposition 10. For k ∈ {0, …, n − 2}, the set of permutations S_{n} is the disjoint union of the k-orbits O_{n,k}(q) for q ∈ S_{n−k}.

Proof. The k-orbits are disjoint by the uniqueness of the decomposition (10). They are (n − k)! in number, and contain ϖ_{n,k} elements each. As (n − k)!ϖ_{n,k} = n! in ℕ, the k-orbits span S_{n}.

In decomposition (10), β specifies to which k-orbit p_{α} belongs and γ specifies the rank of p_{α} within the k-orbit. The first element of the k-orbit has rank α^{first} = βϖ_{n,k} (i.e., γ = 0). The last element has rank α^{last} = βϖ_{n,k} + ϖ_{n,k} − 1 (i.e., γ = ϖ_{n,k} − 1). The element next to the last has rank α^{last} + 1 = βϖ_{n,k} + ϖ_{n,k} = (β + 1)ϖ_{n,k}. It is the first element of the next k-orbit O_{n,k}(q_{β+1}), where q_{β+1} is the element next to q_{β} in S_{n−k}.

Lemma 11. Let p_{α} ∈ S_{n}. There exists a largest k ∈ {0, …, n − 2} and q_{β} ∈ S_{n−k} such that p_{α} is the last element of the k-orbit O_{n,k}(q_{β}), and not the last element of the (k + 1)-orbit containing this k-orbit.

Proof. If p_{α} is not the last element of the 1-orbit it belongs to, it is the last element of the 0-orbit {p_{α}}. In this trivial case, k = 0 and p_{α} = q_{β}. Otherwise the rightmost digit of α is α_{0} = n − 1. There exists a largest k ≥ 1 such that α_{i} = n − i − 1 for i = 0, …, k − 1, and α_{k} ≠ n − k − 1. This means that p_{α} is the last element of nested j-orbits, j = 1, …, k, and not the last element of the (k + 1)-orbit containing these nested j-orbits.

5 Symmetries

For compatibility with the cyclic shift, we adopt the convention that the positions of the symbols in a permutation are computed from the right, and are considered as elements of ℤ_{n} (the position of the last symbol is 0 and the position of the first symbol is n − 1).

According to scheme (9), the symbol x_{n−i} (i ≥ 2) appears at step n − i with the digit α_{i} as exponent of the cyclic shift. Its position in the generated permutation p^{(n−i)} is therefore

pos_{n−i}(x_{n−i}, p^{(n−i)}) = α_{i}.

In particular,

pos_{n}(x_{n}, p^{(n)}) = α_{0}.  (11)

For a permutation p = (a_{1}a_{2} ⋯ a_{n−1}a_{n}) ∈ S_{n}, we introduce the mirror image of p, \overline{p} = (a_{n}a_{n−1} ⋯ a_{2}a_{1}).

Proposition 12. The permutations p_{α} and p_{α′} are the mirror image of one another if and only if their ranks α and α′ verify in ℤ_{n!}

α + α′ = −1.

For example, in ℤ_{5!} we have 84 + 35 = −1, and in S_{5}, p_{84} = (51324) is the mirror image of p_{35} = (42315).

Proof. The proof is by induction on n. For n = 2, p_{0} = (12), p_{1} = (21), and 0 + 1 = 1 = −1 in ℤ_{2}. Let n > 2. By Proposition 8,

α = βϖ_{n,1} + α_{0}ϖ_{n,0}, α′ = β′ϖ_{n,1} + α′_{0}ϖ_{n,0}, q_{β}, q_{β′} ∈ S_{n−1}, α_{0}, α′_{0} ∈ ℤ_{n}.

By Corollary 4, the condition α + α′ = −1 is equivalent to β + β′ = −1 and α_{0} + α′_{0} = −1. By induction hypothesis, q_{β} is the mirror image of q_{β′} in S_{n−1} if and only if β + β′ = −1. The condition α + α′_{0} = −1 is equivalent to α′_{0} = n − 1 − α_{0}, i.e., the ranks of α_{0} and α′_{0} are symmetrical in ℤ_{n}. By (11), these ranks are the positions of symbol x_{n} when p_{α} and p_{α′} are generated by cyclic shift from q_{β} and q_{β′} respectively. This gives the result.

Corollary 13. The word constructed by concatenating the symbols of the permutations generated by cyclic shift is a palindrome.

Proof. Let p_{α} ∈ S_{n}. The rank symmetrical to α in ℤ_{n!} is (n! − 1) − α = −(α + 1). By Proposition 12, p_{−(α+1)} is the mirror image of p_{α}.

The set S_{n} has in fact deeper symmetries, coming from the recursive structure of the k-orbits.

According to Theorem 7, the generation of S_{n} by cyclic shift is obtained by performing α → α + 1 for α ∈ ℤ_{n!}, and writing α in the ϖ-system. This determines each permutation p_{α}. For a fixed k, as α runs through ℤ_{n!}, p_{α} runs through the k-orbits of S_{n}, and leaves a k-orbit to enter the next when, in the computation of α + 1, the carry propagates up to the digit α_{k}, incrementing the rank β of the k-orbit.

Proposition 14. Any two successive permutations of S_{n} are written as

p_{α} = \overline{A}B, p_{α+1} = BA,

with an integer k ∈ {0, …, n − 2} such that

|A| = k + 1.

For example, in S_{5}, p_{39} = (542\underline{31}) and p_{40} = (\underline{31}245).

Proof. If p_{α} and p_{α+1} are in the same 1-orbit then

p_{α} = (a_{1}a_{2} ⋯ a_{n}), p_{α+1} = (a_{2} ⋯ a_{n}a_{1}).

The result holds with A = (a_{1}), B = (a_{2} ⋯ a_{n}), and this corresponds to k = 0. Otherwise, by Lemma 11, there exists a largest k ≥ 1 such that p_{α} is the last element of a k-orbit, and not the last element of a (k+1)-orbit. The elements of a k-orbit are generated by successively inserting the symbols x_{n−k+1}, …, x_{n} from a permutation q_{β} ∈ S_{n−k}. The last element is

(x_{n} ⋯ x_{n−k+1}b_{1} ⋯ b_{n−k}),

where q_{β} = (b_{1} ⋯ b_{n−k}) is a permutation of the symbols x_{1}, …, x_{n−k}. The first element of the next k-orbit is

(c_{1} ⋯ c_{n−k}x_{n−k+1} ⋯ x_{n}),

where q_{β+1} = (c_{1} ⋯ c_{n−k}). As S_{n−k} is generated by cyclic shift, q_{β+1} = C_{n−k}q_{β}, with C_{n−k} the circular permutation in S_{n−k}. We obtain

\begin{aligned}p_{α} & = (x_{n} ⋯ x_{n−k+1}b_{1}b_{2} ⋯ b_{n−k}) & = \overline{A}B \\ p_{α+1} & = (b_{2} ⋯ b_{n−k}b_{1}x_{n−k+1} ⋯ x_{n}) & = BA, \end{aligned}

where A = (b_{1}x_{n−k+1} ⋯ x_{n}) contains k + 1 symbols.

According to Proposition 14, k + 1 symbols (the symbols of A) have to be erased to the left of p_{α} so that the last symbols of p_{α} (the symbols of B) match the first symbols of p_{α+1}.

Definition 15. The weight e_{n}(α) of the transition α → α + 1 is the number of symbols that have to be erased to the left of p_{α} so that the last symbols of p_{α} match the first symbols of p_{α+1}. The ϖ-ruler sequence is the sequence of weights:

E_{n} = {e_{n}(α); α = 0, …, n! − 2}.

Proposition 16. The ϖ-ruler sequence is a palindrome.

Proof. If the ranks α and α′ are symmetrical in ℤ_{n!}, α + α′ = −1. Then α_{i} + α′_{i} = −1 for i = 0, …, n − 2 by Corollary 4. By the definition of e_{n}(α) (the weight associated with the transition α → α + 1), we want to show that e_{n}(α) = e_{n}(α′ − 1). If p_{α} is the last element of a k-orbit, k ≥ 1, then α_{i} = −1 for i = 0, …, k − 1, so that α′_{i} = 0 for i = 0, …, k − 1: p_{α′} is the first element of a k-orbit, and p_{α′−1} is the last element of the previous k-orbit. Hence e_{n}(α) = e_{n}(α′ − 1) = k + 1. If p_{α} is not the last element of a k-orbit, then α_{0} ≠ −1. Hence α′_{0} ≠ 0, and p_{α′} is not the first element of a 1-orbit. In this case e_{n}(α) = e_{n}(α′ − 1) = 1.

Proposition 17. The number of terms of the ϖ-ruler sequence such that e_{n}(α) = k is

(n − k)(n − k)!.

The sum of its n! − 1 terms is

W_{n} = 1! + 2! + … + n! − n.

Proof. We have e_{n}(α) = k if and only if p_{α} is the last element of a (k − 1)-orbit, and not the last element of a k-orbit. The number of (k − 1)-orbits within a k-orbit is n − k + 1. We exclude the last (k − 1)-orbit within the k-orbit (otherwise p_{α} would be the last element of the k-orbit). This gives n − k possibilities for e_{n}(α) = k in a k-orbit. As the number of k-orbits is (n − k)!, there are (n − k)(n − k)! possibilities for e_{n}(α) = k.

The formula for the sum is shown by induction. We have W_{2} = 1 = 1! + 2! − 2, and for n > 2,

W_{n} = ∑_{k=1}^{n−1} k(n − k)(n − k)! = ∑_{k=0}^{n−2}(k + 1)(n − 1 − k)(n − 1 − k)!

= ∑_{k=1}^{n−2} k(n − 1 − k)(n − 1 − k)! + ∑_{k=0}^{n−2}(n − 1 − k)(n − 1 − k)!

= W_{n−1} + ∑_{i=1}^{n−1} i · i! = 1! + … + (n − 1)! − (n − 1) + n! − 1 = 1! + … + n! − n.

In the last line, the induction hypothesis and identity (1) have been used.

The ϖ-ruler sequence is analogous to the binary ruler function (\underline{A001511} in Sloane [3]). The terms of the ruler function give the position of the bit to flip when the binary numbers are listed according to the binary reflected Gray code. They represent the binary division of an inch. The ϖ-ruler sequence differs in that the number of intermediate ticks increases with n (Table 2).

\begin{matrix}n & E_{n} \\ 2 & 1 \\ 3 & 1^{2}21^{2} \\ 4 & 1^{3}21^{3}21^{3}31^{3}21^{3}21^{3} \\ 5 & 1^{4}21^{4}21^{4}21^{4}31^{4}21^{4}21^{4}21^{4}31^{4}21^{4}21^{4}21^{4}41^{4}21^{4}21^{4}21^{4}31^{4}21^{4}21^{4}21^{4}31^{4}21^{4}21^{4}21^{4} \end{matrix}

Table 2: The ϖ-ruler sequence for n = 2, 3, 4, 5 (1^{j} denotes 1 repeated j times).

6 Combinatorial Gray code

A combinatorial Gray code is a method for generating combinatorial objects so that successive objects differ by some pre-specified adjacency rule involving a minimality criterion (Savage [4]). Such a code can be formulated as an Hamiltonian path or cycle in a graph whose vertices are the combinatorial objects to be generated. Two vertices are joined by an edge if they differ from each other in the pre-specified way.

The code associated with the ϖ-system corresponds to an Hamiltonian path in a weighted directed graph G_{n}.

Definition 18. The vertices of the digraph G_{n} are the elements of S_{n}. For two permutations (vertices) p_{α} and p_{α′}, there is an arc from p_{α} to p_{α′} if and only if the last symbols of p_{α} match the first symbols of p_{α′} (there is no arc when there is no match). Let p_{α}, p_{α′} ∈ S_{n} be two connected vertices in G_{n}. The weight f_{n}(α, α′) ∈ {1, …, n − 1} associated with the arc (p_{α}, p_{α′}) is the number of symbols that have to be erased to the left of p_{α} so that the last symbols of p_{α} match the first symbols of p_{α′}.

By Proposition 14, for each α, there is an arc of weight e_{n}(α) = f_{n}(α, α + 1) joining p_{α} to p_{α+1}. This allows to define the Hamiltonian path

w_{n} = {(p_{α}, p_{α+1}); α = 0, …, n! − 2}

joining successive permutations. This path has total weight W_{n} = 1! + ⋯ + n! − n by Proposition 17. The path w_{n} can be closed into an Hamiltonian cycle by joining the last permutation p_{n!−1} to the first p_{0} by an arc of weight n − 1:

(x_{n} ⋯ x_{2}x_{1}) ⟶^{n−1} (x_{1}x_{2} ⋯ x_{n}).

Hence, an oriented path exists from any vertex to any other, so that G_{n} is strongly connected.

Table 3 displays the adjacency matrix of the weighted digraph G_{4} and the Hamiltonian path w_{4}.

Proposition 19. Each vertex of G_{n} has exactly j! in-arcs of weight j and j! out-arcs of weight j for j = 1, …, n − 1. Hence the vertices of G_{n} have L = 1! + ⋯ + (n − 1)! as inand out-degree, and G_{n} is L-regular. The total number of arcs is Ln!.

Proof. Let us consider the arcs of weight j ∈ {1, …, n − 1} joining a vertex to another in G_{n}:

(a_{1} ⋯ a_{j}b_{1} ⋯ b_{n−j}) ⟶^{j} (b_{1} ⋯ b_{n−j}c_{1} ⋯ c_{j}),

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 0 1 2 3 0 0 0 3 0 0 0  3  0  0  2  3  0  0  0  3  0  0  0  3
1 3 0 1 2 0 0 3 0 0 3 0  0  0  3  0  0  3  0  0  2  0  0  3  0
2 2 3 0 1 3 0 0 0 0 2 3  0  3  0  0  0  0  0  3  0  0  3  0  0
3 1 2 3 0 2 3 0 0 3 0 0  0  0  0  3  0  0  3  0  0  3  0  0  0
4 0 0 0 3 0 1 2 3 0 0 0  3  0  0  0  3  0  0  0  3  0  0  2  3
5 0 3 0 0 3 0 1 2 0 0 3  0  3  0  0  2  0  0  3  0  0  3  0  0
6 0 2 3 0 2 3 0 1 3 0 0  0  0  0  3  0  0  3  0  0  3  0  0  0
7 3 0 0 0 1 2 3 0 2 3 0  0  0  3  0  0  3  0  0  0  0  0  3  0
8 0 0 0 3 0 0 0 3 0 1 2  3  0  0  0  3  0  0  2  3  0  0  0  3
9 0 0 3 0 0 3 0 0 3 0 1  2  0  0  3  0  0  3  0  0  3  0  0  2
10 3 0 0 0 0 2 3 0 2 3 0  1  0  3  0  0  3  0  0  0  0  0  3  0
11 2 3 0 0 3 0 0 0 1 2 3  0  3  0  0  0  0  0  3  0  0  3  0  0
12 0 0 2 3 0 0 0 3 0 0 0  3  0  1  2  3  0  0  0  3  0  0  0  3
13 0 3 0 0 3 0 0 2 0 0 3  0  3  0  1  2  0  0  3  0  0  3  0  0
14 3 0 0 0 0 0 3 0 0 3 0  0  2  3  0  1  3  0  0  0  0  2  3  0
15 0 0 3 0 0 3 0 0 3 0 0  0  1  2  3  0  2  3  0  0  3  0  0  0
16 0 0 0 3 0 0 0 3 0 0 2  3  0  0  0  3  0  1  2  3  0  0  0  3
17 3 0 0 2 0 0 3 0 0 3 0  0  0  3  0  0  3  0  1  2  0  0  3  0
18 0 0 3 0 0 3 0 0 3 0 0  0  0  2  3  0  2  3  0  1  3  0  0  0
19 0 3 0 0 3 0 0 0 0 0 3  0  3  0  0  0  1  2  3  0  2  3  0  0
20 0 0 0 3 0 0 2 3 0 0 0  3  0  0  0  3  0  0  0  3  0  1  2  3
21 0 0 3 0 0 3 0 0 3 0 0  2  0  0  3  0  0  3  0  0  3  0  1  2
22 0 3 0 0 3 0 0 0 0 0 3  0  3  0  0  0  0  2  3  0  2  3  0  1
23 3 0 0 0 0 0 3 0 0 3 0  0  2  3  0  0  3  0  0  0  1  2  3  0

Table 3: The adjacency matrix of the digraph G_{4}. Lines delineate the 1-orbits. Double lines delineate the 2-orbits. Entries on the upper diagonal (in color) indicate the Hamiltonian path corresponding to the ϖ-system code, and forming the ϖ-ruler sequence.

where the c’s are a permutation of the a’s. There are j! possibilities for the c’s, the a’s and the b’s being fixed. Hence j! arcs of weight j leave each vertex. Similarly, there are j! possibilities for the a’s, the b’s and the c’s being fixed, so that j! arcs of weight j enter each vertex. By the degree sum formula, the sum of the in- or out-degrees of the n! vertices, n!(1! + ⋯ + (n − 1)!), equals the total number of arcs.

The set {G_{n}; n ≥ 1} is an infinite family of strongly connected regular digraphs.

We conjecture that the Hamiltonian path w_{n} joining successive permutations in the digraph G_{n} is of minimal total weight. Assuming the conjecture, we may state:

The ϖ-system is a combinatorial Gray code listing the permutations generated by cyclic shift. The adjacency rule is that the minimal number of symbols is erased to the left of a permutation so that the last symbols of the permutation match the first symbols of the next permutation.

7 Acknowledgments

Marco Castera initiated the problem which motivated this study. The pertinent comments of the anonymous referee were very helpful.

References

[1] D. E. Knuth, The Art of Computer Programming, Vol. 4, Combinatorial Algorithms, Addison-Wesley, 2005.

[2] C.-A. Laisant, Sur la numération factorielle, application aux permutations, Bull. Soc. Math. France 16 (1888), 176–183.

[3] N. J. A. Sloane, The On–Line Encyclopedia of Integer Sequences, published electroni-

    cally at http://www.research.att.com/~njas/sequences, 2010.

[4] C. Savage, A survey of combinatorial Gray codes, SIAM Rev. 39 (1997), 605–629.

2000 Mathematics Subject Classification: Primary 05A05, 11A63; Secondary 05C20, 05C38. Keywords: permutations, cyclic shift, number system, palindrome, combinatorial Gray code.

(Concerned with sequences \underline{A000142}, \underline{A001511}, \underline{A007489}, and \underline{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.