# Permutation

## Contents

## Definition

A **permutation** on a set is defined as a bijective function from the set to itself.

The set of all permutations on a set forms a group with the group operation being function composition, the identity element being the identity function, and the inverse of a permutation being the inverse function. This group is termed the symmetric group on the set. A permutation on a set can thus also be defined as an element of the symmetric group on the set.

## Notation

### Two-line notation for permutations

`Further information: two-line notation for permutations`

Suppose is a finite set and is a permutation of . A two-line notation for is a two-line description that uniquely determines . The first row lists the elements of . In the second row, we list, below each element of , its image under .

For instance, consider the permutation on that sends to . The two-line notation for this permutation is:

.

### One-line notation for permutations

`Further information: one-line notation for permutations`

The one-line notation for a permutation is an abbreviated form of the two-line notation where we write only the second line, because the first line is *understood*. This happens, for instance, when the elements of come with a standard ordering and it is understood that the first line, if written, would have the elements in that order.

### Cycle decomposition for permutations

`Further information: cycle decomposition for permutations, understanding the cycle decomposition`

The cycle decomposition of a permutation is an expression of the permutation as a product of disjoint cycles. For instance, the permutation on has three cycles: , and . The cycle decomposition is this .