one-line notation for permutations

One-line notation is a system for representing permutations on a collection 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 group.

First consider the permutation $\\pi=(134)(25)$ in the symmetric group $\\mathfrak{S}_{5}$ . Here $\\pi$ is written in cycle notation, so $\\pi(1)=3$ , $\\pi(2)=5$ , $\\pi(3)=4$ , $\\pi(4)=1$ , and $\\pi(5)=2$ . We can record this information in the following table:

\\begin{array}[]{clllll}i&1&2&3&4&5\\\\\\pi(i)&3&5&4&1&2\\end{array}

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

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

X=\\{x_{1}<x_{2}<\\dots<x_{n}\\}.

For an arbitrary $\\pi\\in\\mathfrak{S}_{X}$ , the one-line notation for $\\pi$ is then

\\pi=\\pi(x_{1})\\pi(x_{2})\\cdots\\pi(x_{n}).

Observe that if $\\pi$ and $\\sigma$ are distinct permutations in $\\mathfrak{S}_{X}$ , then there is some $i$ for which $\\pi(x_{i})\eq\\sigma(x_{i})$ . Hence the one-line notations for $\\pi$ and $\\sigma$ will differ in the $i$ th position. This shows that one-line notation is an injective map.Furthermore, we can immediately recover $\\pi$ from its one-line notation. If $\\pi$ has one-line notation $a_{1}a_{2}\\dots a_{n}$ , then we know that $\\pi(x_{i})=a_{i}$ for all $i$ . For example, consider the permutation in $\\mathfrak{S}_{7}$ written in one-line notation as $\\pi=1732654$ . We immediately obtain the following:

\\begin{array}[]{clllllll}i&1&2&3&4&5&6&7\\\\\\pi(i)&1&7&3&2&6&5&4\\end{array}

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

If we are willing to allow words of infinite length, we can even extend one-line notation to symmetric groups of arbitrary cardinality. Let $X$ be a set and $\\mathfrak{S}_{X}$ its symmetric group. Apply the axiom of choice to select a well-ordering on $X$ . So we may write the elements of $X$ in order as the tuple $(x_{1},x_{2},\\dots,x_{\\alpha},x_{\\alpha+1},\\dots)$ . Then for each $\\pi\\in\\mathfrak{S}_{X}$ the one-line notation for $\\pi$ is the tuple

(\\pi(x_{1}),\\pi(x_{2}),\\dots,\\pi(x_{\\alpha}),\\pi(x_{\\alpha+1}),\\dots).

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