Home » Discrete Mathematics

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  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
            b1      b2    then

    f^-1 =  b1      b2
            a1      a2

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.



Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© some rights reserved.