# Permutation Group | Discrete Mathematics

In this article, we will learn about the **Introduction permutation group**, and the **types of permutation in discrete mathematics**.

Submitted by Prerana Jain, on August 17, 2018

## Permutation Group

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 permutation**

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 permutation**

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions