Definition:Permutation on n Letters

From ProofWiki
Jump to navigation Jump to search

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

  • Results about permutations on $n$ letters can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Permutation_on_n_Letters&oldid=709547"