# 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.

Related Tutorials

- Set Theory: What It Is, Types, Symbols, and Examples
- Set: Cardinality, Notations, Construction, Operations
- Group Theory and Its Types in Discrete Mathematics
- Discrete Mathematics Functions, Their Types, and Examples
- Properties of Binary Relation in a Set
- Rings and Types of Rings in Discrete Mathematics
- Finite-state Machine: What It Is, Components, and Types
- Normal Forms and Their Types
- Propositional Logic in Discrete Mathematics
- Operations in Propositional Logic in Discrete Mathematics

Comments and Discussions!