# one-line notation for permutations

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}

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})\neq\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.

Title one-line notation for permutations OnelineNotationForPermutations 2013-03-22 16:24:38 2013-03-22 16:24:38 mps (409) mps (409) 4 mps (409) Definition msc 05A05 Permutation CycleNotation one-line notation