Page 167 - DMTH202_BASIC_MATHEMATICS_II

Basic Mathematics-II

Notes 12.3 Permutations

A permutation, also recognized as an “arrangement number” or “order,” is a reorganization of
the essentials of an ordered list S into a one-to-one correspondence with S itself. The number of
permutations on a set of elements is provided by n!.

Example: There are 2! = 2 1 = 2 permutations of {1  2}, that is {1 2} and {2  1}, and 3! =
3 2 = 6 permutations of {1 23}, that is {1 23}, {1 32}, {2 13}, {2 31}, {3 12}, and
{3 21}. The permutations of a list can be instituted in Mathematica by means of the command
Permutations.

!
Caution A list of length can be verified to observe if it is a permutation of 1, ..., n by means
of the command Permutation Q [list] in the Mathematica package Combinatorica‘ .
The number of methods of attaining an ordered subset of elements from a set of elements is
specified by

! n
nP  (1)
k
(n k )!

where n! is a factorial.

Example: There are 4!/2! = 12 2-subsets of {1 23 4}, that is {1 2}, {1 3}, {1 4}, {2 1},
{2 3}, {2 4}, {3 1}, {3 2}, {3 4}, {4 1}, {4 2}, and {4 3}. The unordered subsets comprising elements
are recognized as the k-subsets of a specified set.
A demonstration of a permutation as a product of permutation cycles is exclusive.

Example: An example of a cyclic disintegration is the permutation {4 21 3} of
{1 23 4}. This is indicated as (2)(143), analogous to the disjoint permutation cycles (2) and (143).
There is a huge concern of independence in choosing the illustration of a cyclic decomposition
because
1. The cycles are disjoint and can so be mentioned in any order, and
2. Any rotation of a specified cycle mentions the similar cycle.
As a result, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), and (2)(143) all portray the same
permutation.
A different notation that clearly recognizes the positions engaged by elements before and after
application of a permutation on elements utilizes a matrix, where the first row is and the
second row is the new arrangement.

Example: The permutation which toggles elements 1 and 2 and fixes 3 would be
represented as

 1 2 3
  . ...(2)
 2 1 3 

Any permutation is also considered as a product of transpositions. Permutations are normally
indicated in lexicographic or transposition order.

162 LOVELY PROFESSIONAL UNIVERSITY