Page 168 - DMTH202_BASIC_MATHEMATICS_II

Unit 12: Permutation

Notes
Did u know? There is an association between a permutation and a pair of Young
tableaux called as the Scented correspondence.
A permutation of ordered objects in which no object is in its ordinary place is known
as derangement (or at times, a complete permutation) and the number of such permutations is
specified by the sub factorial ! n.
By means of

n  n 

y
(x  ) y n    x n r r (3)
r
r 0  
with x = y = 1 provides
n  n 
2 n    , (4)
r
r 0  
so the number of methods of selecting 0, 1, ..., or n at a time is 2n.
The set of all permutations of a set of elements 1, ..., n can be attained by the following recursive
procedure

1 2
/
(5)
2 1
1 2 3
/
1 3 2
/
3 1 2

3 2 1
(6)
\
2 3 1
\
2 1 3
Consider permutations in which no pair of successive elements (i.e., mounting or falling
successions) take place. For n = 1, 2, ... elements, the numbers of such permutations are 1, 0, 0, 2,
14, 90, 646, 5242, 47622, ... .
Consider the set of integers 1, 2, ..., N be permuted and the consequent sequence be separated
into rising runs. Signify the regular length of the nth run as N approaches infinity, L . The first
n
few values are summed up in the following table, where e is the base of the natural logarithm.
n L n approximate
1 e – 1 1.7182818...
2
2 e  2e 1.9524...
3
2
2
3 e  3e  e 1.9957...
2
Now let us define permutation.

LOVELY PROFESSIONAL UNIVERSITY 163