# Definition:Permutation on n Letters

## Contents

## Definition

Let $\N_k$ be used to denote the initial segment of natural numbers:

- $\N_k = \closedint 1 k = \set {1, 2, 3, \ldots, k}$

A **permutation on $n$ letters** is a **permutation**:

- $\pi: \N_n \to \N_n$

The usual symbols for denoting a general **permutation** are $\pi$ (not to be confused with the famous circumference over diameter), $\rho$ and $\sigma$.

### Set of Permutations

The **set of permutations of $\N_n$** is denoted $S_n$.

### Two-Row Notation

Let $\pi$ be a permutation on $n$ letters.

The **two-row notation** for $\pi$ is written as two rows of elements of $\N_n$, as follows:

- $\pi = \begin{pmatrix} 1 & 2 & 3 & \ldots & n \\ \map \pi 1 & \map \pi 2 & \map \pi 3 & \ldots & \map \pi n \end{pmatrix}$

The bottom row contains the effect of $\pi$ on the corresponding entries in the top row.

### Cycle Notation

The **two-row notation** is a cumbersome way of defining a permutation.

Instead, the **cycle notation** is usually used instead.

The $k$-cycle $\rho$ is denoted:

- $\begin {pmatrix} i & \map \rho i & \ldots & \map {\rho^{k - 1} } i \end{pmatrix}$

From Existence and Uniqueness of Cycle Decomposition, all permutations can be defined as the product of disjoint cycles.

As Disjoint Permutations Commute, the order in which they are performed does not matter.

So, for a given permutation $\rho$, the **cycle notation** for $\rho$ consists of all the disjoint cycles into which $\rho$ can be decomposed, concatenated as a product.

It is conventional to omit $1$-cycles from the expression, and to write those cycles with lowest starting number first.

## Also see

## Sources

- 1965: J.A. Green:
*Sets and Groups*... (previous) ... (next): $\S 3.6$. Products of bijective mappings. Permutations: Example $54$ - 1968: Ian D. Macdonald:
*The Theory of Groups*... (previous) ... (next): Appendix: Elementary set and number theory - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $2$: Examples of Group Structure: $\S 30$ - 1974: Thomas W. Hungerford:
*Algebra*... (previous) ... (next): $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups - 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): $\S 34$. Examples of groups: $(4) \ \text {(c)}$ - 1996: John F. Humphreys:
*A Course in Group Theory*... (previous) ... (next): Chapter $9$: Permutations