Definitions [1]
A permutation is an arrangement in a definite order of a number of objects taken some or all at a time.
Theorems and Laws [6]
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!)`
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 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.
Theorem: `"^n P_r`= `"^n C_r` r!, 0 < r ≤ n.
Proof: Corresponding to each combination of `"^nC_r`, we have r ! permutations, because r objects in every combination can be rearranged in r ! ways.
Hence, the total number of permutations of n different things taken r at a time is `"^nCr` × r!. On the other hand, it is P n r . Thus
`"^n P_r` =`"^n C_r` * r!, 0 < r ≤ n.
Theorem: `"^nC_r` + `"^nC_r-1`= `"^(n+1)C_r`
Proof: We have `"^nC_r` + `"^nC_r-1= (n!)/[r!(n-r)!] + (n!)/[(r-1)!(n-r+1)!]`
= `(n!)/ [r*(r-1)!(n-r)!] + (n!)/[(r-1)!(n-r+1)(n-r)!]`
= `(n!)/[(r-1)!(n-r)!] [(1/r) + 1/(n-r+1)]`
= `(n!)/[(r-1)!(n-r)!] * (n-r+1+r)/[r(n-r+1)]`
= `(n+1)!/[r!(n+1-r)!`
= `"^(n+1) C_r`
