Home » Discrete Mathematics

Permutation Group and Its Types in Discrete Mathematics

In this tutorial, we will learn about the permutation group, and the types of permutation in discrete mathematics. By Prerana Jain Last updated : May 09, 2023

What is Permutation Group in Discrete Mathematics?

Let, X be a non-empty set. A permutation of X is a one-one function from X onto X. A group (G,*) is called a permutation group on a non-empty set X if the elements of G are a permutation of X and the operation * is the composition of two functions.

For instance ro = 1 2 3 4 denotes the permutation on the four 2 1 4 3 symbols { 1, 2, 3, 4} which maps 1 on 2, 2 on 1, 3 on 4 and 4 on 3. This is the permutation corresponding to the symmetry of the square which is a reflection along the vertical bisector.

Clearly, the order of the column in the symbol is immaterial so long as the corresponding elements above and below in that column remain unchanged. The number of elements of a finite set is the degree of the permutation.

Equality of two permutations

Let, f and g be two permutation on a X. Then f = g if only if f(x) = g(x) for all x in X.

Example

Let, f and g be given by:

f = 1 2 3 4         g = 3 2 1 4
2 3 4 1             4 3 2 1

Evidently f(1) = 2 = g(1), f(2) = 3 = g(2)
f(3) = 4 = g(3), f(4) = 1 = g(4)
Thus, f(x)  = g(x) for all x E {1, 2, 3, 4} which implies f = g.

Total number of permutations

Let, X, is a set consisting of n distinct elements. Then the elements of X can be permitted in n! different ways. If Sn be the set consisting of all permutation of degree n then the set Sn will have n! different permutation of degree n. This set Sn is called the symmetric set of permutation of degree n.

Types of Permutation

1. Identity permutation

If each element of permutation is replaced by itself then it is known as the identity permutation and is denoted by the symbol I.

I = a  b  c
a  b  c  is an identity permutation

2. Product of Permutation

A permutation is one- one onto the map and hence it is invertible, i.e. every permutation f on a set P ={ a1, a2, ..., an} has a unique inverse permutation denoted by f^-1.

Thus if

f =     a1      a2 ......an
        b1      b2 ......bn

Then:

f^-1 =  b1      b2 ......bn
        a1      a2 ......an

3. Cyclic Permutation

A permutation which replaces n objects cyclically is called cyclic permutation of degree n.

Consider the permutation p = 1 2 3 4 this assignment of 2 3 4 1 values could be presented.

The number of elements permuted by a cycle is said to be its length and disjoint cycles are those which have no common elements. A cycle of length 1 means that the image of an element is the element itself and represents identity permutation.

4. Transposition

A cyclic permutation such (a, b) which interchanges the symbol leaving all other unchanged is called transposition. In other words, transposition is a cycle of length two of the form (a, b) i.e. it is a mapping which maps each object onto itself expecting two, each of which is mapped on the other. For example (1, 2) is a transposition.

5. Even and Odd Permutation

When a permutation is expressed as a product of even or odd number of transpositions then the permutation is called as even or odd permutation.

---