Main Index Discrete mathematics Permutations
 Subject Index
comment on the page

Permutations

An injective function (mapping) of a finite set into itself is called a permutation. There follows from the definition of finite sets that shows that such a function is necessarily also surjective and consequently a permutation is always bijective. It is convenient when working with finite sets typeset structure having typeset structure elements to represent them using the segment typeset structure of the first typeset structure positive integers. Then to denote the assignment rule of a permutation typeset structure of this set we can write

↓ 1 2 3 ... n - 1 n k k k k k 1 2 3 ... n - 1 n(1)

The top row of numbers indicates the starting position of a shell. The bottom row indicates the final position of the shell. Thus to find where an object went under a permutation look up its number in the top row and its final place will be under that number.

Another common used notation is

π = ( ) 1 2 3 ... k k k k 1 2 3 ... n - 1 n(2)

As a special case of a function the permutation can be composed together and with respect to this function composition they form a semigroup with identity

ι = (1 2 3 ... n - 2 n - 1 n ) . 1 2 3 ... n - 2 n - 1 n

An inverse permutation of a permutation typeset structure is a permutation, denoted by typeset structure , in which each number is mapped to its preimage. It is computed by exchanging each number and the number of the place which it occupies

π^(-1) = (k k k k k ) . 1 2 3 ... n - 1 n 1 2 3 ... n - 1 n(3)

To write it in the form (2) reorder the columns in such a way that the elements in the first row form an increasing sequence.

This implies that the set of the all permutation on a finite set form a group. The group of the all permutations of an typeset structure element set is called the symmetric group and denoted by typeset structure.

Permutations are often written in cyclic form. A cycle is a permutation φ for which there exists an element typeset structure such that typeset structure, typeset structure, typeset structure, ..., typeset structure are the only elements of typeset structure moved by typeset structure. Although the composition of permutations is not commutative, two disjoint cycles commute with each other.

To find the inverse of a permutation that is a cycle all we have to do is write the elements of the cycle in reverse order. Thus the inverse of typeset structure is typeset structure. To find the inverse permutation write it as a product of cycles, and then reverse the order in each cycle.

A 2-cycle is called transposition. In another words, a transposition is a permutation which exchanges the place of two objects whilst leaving all the other objects unmoved. A simple transposition is a 2-cycle of the form typeset structure.

Theorem. Every permutation can be written as a product of transpositions.

However, the representation of a permutation as a product of transpositions is not unique. A simple counting argument shows that every permutation on an typeset structure element set can be written as a product of at most typeset structure transpositions.

Since the number of transpositions needed to represent a given permutation is always either even or always odd, it has always the same parity.  If a permutation typeset structure can be written as a product of an odd number of transpositions, it is then called an odd permutation. If this number is even typeset structure is an even permutation. For instance, every transposition is odd.

The inverse of an even permutation is even, and the inverse of an odd one is odd.

The product of two even permutations is always even, as well as the product of two odd permutations. All other products are odd. Thus we can define the sign of a permutation π:

sgn(π) = {+ 1, if π is even, -1, if π is odd .

A pair of elements typeset structure in  (2) is called an inversion in a permutation typeset structure if typeset structure  and typeset structure. The parity of a permutation is also given by the parity of its number of inversion. Let

P _ n = Underoverscript[∏, 1 <= i < j <= n, arg3] (j - i) .

A simple observation, that the set of non-ordered couples typeset structure, typeset structure, does not change after a permutation typeset structure is performed on it the product

P _ n(π) = Underoverscript[∏, 1 <= i < j <= n, arg3] (π(j) - π(i))

has the same sign as typeset structure. Consequently

sgn(π) = P _ n(π)/P _ n . (4)

Then

sgn(π o τ) = (Underoverscript[∏, 1 <= i < j <= n, arg3] (π(τ(j)) ... pt[∏, 1 <= i < j <= n, arg3] (π(j) - π(i))) = sgn(π) · sgn(τ) .

Therefore again, a composition of two even permutations is even, and even permutations on typeset structure form a group, called alternating group typeset structure .

Cite this web-page as:

Štefan Porubský: Permutations.
Page created .