Permutations

A permutation is an arrangement in a definite order of a number of objects taken some or all at a time.

We are actually counting the different possible arrangements of the letters such as ROSE, REOS, ..., etc. Here, in this list, each arrangement is different from other. In other words, the order of writing the letters is important. Each arrangement is called a permutation of 4 different letters taken all at a time. Now, if we have to determine the number of 3-letter words, with or without meaning, which can be formed out of the letters of the word NUMBER, where the repetition of the letters is not allowed, we need to count the arrangements NUM, NMU, MUN, NUB, ..., etc. Here, we are counting the permutations of 6 different letters taken 3 at a time. The required number of words = 6 × 5 × 4 = 120 (by using multiplication principle). If the repetition of the letters was allowed, the required number of words would be 6 × 6 × 6 = 216.

Permutations when all the objects are distinct:

Theorem: The number of permutations of n different objects taken r at a time, where 0 < r ≤ n  and the objects do not repeat  is n ( n – 1) ( n – 2). . .( n – r + 1), which is denoted by `"^n P_r`.
Proof: There will be as many permutations as there are ways of filling in r vacant the n objects. The first place can be filled in n ways; following which, the second place can be filled in (n – 1) ways, following which the third place can be filled in (n – 2) ways,..., the rth place can be filled in (n – (r – 1)) ways. Therefore, the number of ways of filling in r vacant places in succession is n(n – 1) (n – 2) . . .   (n – (r – 1)) or n ( n – 1) (n – 2)
... (n – r + 1). 
This expression for `"^n P_r`  is cumbersome and we need a notation which will help to reduce the size of this expression. The symbol n! (read as factorial n or n factorial ) comes to our rescue. In the following text we will learn what actually n! means.

Factorial notation:The notation n! represents the product of first n natural numbers, i.e., the product 1 × 2 × 3 × . . . × (n – 1) × n is denoted as n!. We read this symbol as ‘n factorial’.
1 = 1 ! 
1 × 2 = 2 ! 
1× 2 × 3 = 3 ! 
1 × 2 × 3 × 4 = 4 ! and so on.
We define 0 ! = 1 
We can write   5 ! = 5 × 4 ! = 5 × 4 × 3 ! = 5 × 4 × 3 × 2 !  = 5 × 4 × 3 × 2 × 1! 
Clearly, for a natural number n     
n ! = n (n  –  1) ! 
= n (n  –  1) (n  –  2) !                       [provided (n ≥ 2)]
= n (n  –  1) (n  –  2) (n  –  3)!   [provided (n ≥ 3)] 
and so on.

Derivation of the formula for `"^n P_r`:
`"^n P_r= (n!)/(n-r)!` , 0 ≤ r ≤ n
Let us now go back to the stage where we had determined the following formula: 
 `"^n P_r`= n (n – 1) (n – 2) . . .  (n – r + 1)
Multiplying numerator and denomirator by (n – r) (n – r – 1) . . . 3 × 2 × 1, we get
 `"^n P_r`= [n (n – 1) (n – 2) . . .  (n – r + 1)(n-r) (n-r-1)... 3xx2xx1]/[(n-r) (n-r-1)... 3xx2xx1]
                   = n!/ (n-r)!
Thus `"^n P_r= (n!)/ (n-r)!`, where 0 < r ≤ n

Theorem: The number of permutations of n different objects taken r at a time, where repetition is allowed, is `n^r`. 
The number of 3-letter words which can be formed by the letters of the word
NUMBER = `"^6 P_3= (6!)/(3!)`= 4*5*6= 120. Here, in this case also, the repetition is not
allowed. If  the repetition is allowed,the required number of words would be `6^3` = 216. 
The number of ways in which a Chairman and a Vice-Chairman can be chosen from amongst a group of 12 persons assuming that one person can not hold more than one position, clearly
`"^12 P_2= (12!)/(10!)`= 11*12= 132.

 Permutations when all the objects are not distinct objects:  Suppose we have to find the number of ways of rearranging the letters of the word INSTITUTE. In this case there are 9 letters, in which I appears 2 times and T appears 3 times. 
Temporarily, let us treat these letters different and name them as `I_1, I_2, T_1,  T_2, T_3`. The number of permutations of 9 different letters, in this case, taken all at a time is 9 !. Consider one such permutation, say, `I_1 NT_1 SI_2 T_2 U E T_3`.  Here if `I_1, I_2` are not same and `T_1, T_2, T_3` are not same, then `I_1, I_2` can be arranged in 2! ways and `T_1, T_2, T_3 `can be arranged in 3! ways. Therefore, 2! × 3! permutations will be just the same permutation corresponding to this chosen permutation `I_1NT_1SI_2T_2UET_3`. Hence, total number of different permutations will be `9!/(2!3!)`

Theorem: The number of permutations of n objects, where p objects are of the
same kind and rest are all different = `(n!)/(p!)`.
In fact, we have a more general theorem.

Theorem: The number of permutations of n objects, where p1 objects are of one kind, p2 are of second kind, ..., pk are of kth kind and the rest, if any, are of different kind is 
`(n!)/(p_1!p_2!...p_k!)`