Permutation and Combination
1. FUNDAMENTAL PRINCIPLE OF COUNTING
1.1 Multiplication Theorem: If an event can occur in m different ways, and following which another event can occur in n different ways; then the total number of occurrences of the events in the given order is m x n. We can extend this principle to r number of events (r is a positive integer). Thus if an event occurs in m different ways, a following event occurs in n different ways, a following event occurs in p ways, and so on, then the total number of occurrence in this given order = m x n x p x ….
1.2 Addition Theorem If an event can occur in m different ways and a second independent event can occur in n different ways; either of the two operations can be performed in (m+n) ways. And this can be extended to any number of events.
2. FACTORIAL OF A NUMBER
For any natural number, say n, the factorial n, represented by n! means the product of all natural numbers starting from that number down to 1. For example: 10! = 10x9x8x7x6x5x4x3x2x1
14! = 14x13x12x11x10x9x8x7x6x5x4x3x2x1
4! = 4x3x2x1
Hence, the factorial of a non-negative integer is defined as:
n! = 1 x 2 x 3 x 4 x 5 x 6 x ……………….x (n-1) x n
Algebra of Factorial
1! = 1
0! = 1
n! = n x {(n-1)!}, as 12! = 12x11x10x9x8x7x6x5x4x3x2x1 = 12x11!
What is Arrangement? Permutation
Always remember – Permutations are always greater than Combinations.
Permutation: Let us make arrangements of r number ‘in ordered manner’, taken at a time, of distinct elements from n number of elements. First position can be filled up in n number of ways, second position can be filled up in (n-1) number of ways, third position can be filled up in (n-2) number of ways, fourth position can be filled up in (n-3) number of ways, ……………………….., rth position can be filled up in [n-(r-1)] number of ways. Hence, total number of permutations is:
Case I: Permutation of n number of distinct elements taken all at one time, is p(n, n), i.e.
Case II: When p number of particular things is always to be included in the arrangement
Number of permutations of n distinct things taking r at a time, when p number of particular things is always to be included in each selection, is:
Why. Simple, as p number of things has always to be selected; we shall leave this set of p number of things out of arrangement procedure, and make our arrangement of (r-p) things out of (n-p) number of things.
Case III: When p number of particular things is never included in the arrangement
Number of permutations of n distinct things taking r at a time,
when p number of particular things is never to be included, is:
Why. Simple, as p number of things has never to be included; we shall leave this set of p number of things out of selection from n things out of which r things have to be selected, and make our selection of r things out of (n-p) number of things.
Case IV: When Permutations of objects when all objects are not distinct
Number of ways in which n things can be arranged taking them all at a time, when p1 of the things are exactly alike of 1st type, p2 of them are exactly alike of a 2nd type ………….... pr of them are exactly alike of rth type and the rest all are distinct is n!/(p1! p2! ⋯ pr!)
Case V: When Permutations of objects when repetitions are allowed
Let there be 10 distinct alphabets (a, b, c, d, e, f, g, h, I, j) and we have to form letters taking 5 alphabets at a time allowing the repetitions. Of course, first alphabet can be chosen in 10 numbers of ways. The second alphabet (instead of being chosen in 9 ways, had there been no repetition) can be chosen again in 10 numbers of ways. Similarly, the third, fourth and fifth alphabet can be chosen in 10 numbers of ways each. Hence, total number of permutations is:
Hence, the number of permutations of n different objects taken r at a time, allowing repetition any number of times in each arrangement is:
What is Selection? Combinatation
In the beginning of topic of Permutations, we showed you a table describing the difference between permutation and combination.
We make ‘unordered’ arrangements of alphabets taking two at a time from a set of four alphabets a, b, c, d keeping in mind that (a, b) = (b, a).
All such arrangements are (a, b), (a, c), (a, d), (b, c), (b, d), (c, d), which are 6 in numbers.
The basic difference between Permutation and Combination is that in Permutation we consider ‘arrangement’ while in Combination we consider ‘selection’.
Always remember – Permutations are always greater than Combinations.
Try to understand this, this way. Suppose we have 10 objects, say, a, b, c, d, e, f, g, h, I, j; and we make various arrangements, taking 3 at a time. Simultaneously we make selections, taking 3 at a time.
Number of Combinations: Suppose we have one ordered arrangement like this, (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a). Against this 6 number of ordered arrangement for one specific case, we shall have only one combination i.e. (a,b,c) or (a,c,b) or whatever you like out of six given under arrangements. Hence we shall divide the permutation by 6 or by 3! (not only because 6 = 3!, but 3! Is the number of arrangements of 3 objects also, taken 3 at a time).
Hence, generalizing this, if we have a set of n number of distinct objects, and we are making selection of r distinct number of objects form this set, the number of combinations is:
Qu. 001: In how many different ways can the letters of the word 'DETAIL' be arranged such that the vowels must occupy only the odd positions? A. 36, B.44, C. 64, D. 120
Sol: The given word ‘DETAIL’ consists of 6 letters, i.e. 3 vowels and 3 consonants. We can always place 3 vowels in 3 odd positions (first, third or fifth) in 3! = 6 ways. Similarly, we can always place 3 consonants in 3 even positions (second, fourth or sixth) in 3! = 6 ways. Hence, total number of permutations = 6x6 = 36. Option (A) is the answer.
Qu. 002: In how many ways can 21 books on English and 19 books on Hindi be placed in a row on a shelf such that no two books of Hindi are put together? (A) 3990 (B) 1540 (C) 1995 (D) 3672
Sol: Two cases arise:
-
All books of English are identical and all books of Hindi are identical,
-
All books of English are different and all books of Hindi are different.
Case I: There are 21 English books; hence there are 22 places where Hindi books can be placed in order that no two Hindi books are put together. Hence required solution is C(22, 19) = 22!/(19! X 3!) = (22x21x20)/(3x2x1) = 1540
Case II. 21 English books can be place in 21! ways. 19 Hindi books can be place in 19! ways. The total number of permutations is: 1540 x 21! X 19!
{And of course, there may be many more cases, like 2 or 3 or 5 or 14 books of English are same; or some number of Hindi books are same. Such cases are many and have not been considered}