one-line notation for permutations

One-line notation is a system for representing permutationsMathworldPlanetmath on a collectionMathworldPlanetmath of symbols by words over the alphabet consisting of those symbols. First we show how the notation works in an example, and then we show that the notation can be made to work for any symmetric groupMathworldPlanetmathPlanetmath.

First consider the permutation π=(134)(25) in the symmetric group 𝔖5. Here π is written in cycle notation, so π(1)=3, π(2)=5, π(3)=4, π(4)=1, and π(5)=2. We can record this information in the following table:


Finally, we read off the one-line notation as the second row of the table. Thus we write π=35412.

Now we define one-line notation for arbitrary finite symmetric groups. Let X be a set of finite cardinality n and let 𝔖X be the group of permutations on X. Fix once and for all a total orderMathworldPlanetmath < on X. Using this order, we may say that


For an arbitrary π𝔖X, the one-line notation for π is then


Observe that if π and σ are distinct permutations in 𝔖X, then there is some i for which π(xi)σ(xi). Hence the one-line notations for π and σ will differ in the ith position. This shows that one-line notation is an injective map. Furthermore, we can immediately recover π from its one-line notation. If π has one-line notation a1a2an, then we know that π(xi)=ai for all i. For example, consider the permutation in 𝔖7 written in one-line notation as π=1732654. We immediately obtain the following:


So now we can translate the permutation into cycle notation: π=(1)(274)(56).

If we are willing to allow words of infiniteMathworldPlanetmath length, we can even extend one-line notation to symmetric groups of arbitrary cardinality. Let X be a set and 𝔖X its symmetric group. Apply the axiom of choiceMathworldPlanetmath to select a well-ordering on X. So we may write the elements of X in order as the tuple (x1,x2,,xα,xα+1,). Then for each π𝔖X the one-line notation for π is the tuple


The same analysis as in the finite case shows that a permutation is uniquely recoverable from its representation in one-line notation.

Title one-line notation for permutations
Canonical name OnelineNotationForPermutations
Date of creation 2013-03-22 16:24:38
Last modified on 2013-03-22 16:24:38
Owner mps (409)
Last modified by mps (409)
Numerical id 4
Author mps (409)
Entry type Definition
Classification msc 05A05
Related topic Permutation
Related topic CycleNotation
Defines one-line notation