Permutation & Combination

Permutation & Combination There can never be surprises in logic...Wittgenstein, Ludwig The most fundamental application of mathematics is counting. There are many natural methods used for counting This chapter is dealing with various known techniques those are much faster than the usual counting methods. We mainly focus, our methods, on counting the number of arrangements (Permutations) and the number of selections (combinations), even although we may use these techniques for counting in some other situations also . Let us start with a simple problem A group G1 of 3 circles C1, C2, C3 having different centers are situated in such a way that C2 lie entirely inside C1 ; C3 lie entirely inside C2. Another group G2 of 4 circles C1′, C2′, C3′, C4′ are also situated in a similar fashion. The two groups of circles are in such a way that each member of G1 intersect with every member of G2, as shown in the following figure (i) (ii) How many centres the circles altogether has ? How many common chords are obtained ? The answer to the first part is "3 + 4 = 7" and answer to the second part is "3 × 4 = 12" . The method in which we calculated first part of the problem is called as "addition rule" and the method we used to calculate its second part is called as the "multiplication rule". These rules altogether are the most important tools in counting, popularly known as "the fundamental counting principle". Fundamental counting principle : Suppose that an operation O1 can be done in m different ways and another operation O2 can be done in n different ways. (i) (ii) Addition rule : The number of ways in which we can do exactly one of the operations O1, O2 is m + n Multiplication rule : The number of ways in which we can do both the operations O1, O2 is mn. Note : The addition rule is true only when O1 & O2 are mutually exclusive and multiplication rule is true only when O1 & O2 are independent (The reader will understand the concepts of mutual exclusiveness and independence, in the due course) Example # 1 : There are 8 buses running from Kota to Jaipur and 10 buses running from Jaipur to Delhi. In how many ways a person can travel from Kota to Delhi via Jaipur by bus? Solution : Let E1 be the event of travelling from Kota to Jaipur & E2 be the event of travelling from Jaipur to Delhi by the person. E1 can happen in 8 ways and E2 can happen in 10 ways. Since both the events E1 and E2 are to be happened in order, simultaneously, the number of ways = 8 × 10 = 80. Example # 2 : How many numbers between 10 and 10,000 can be formed by using the digits 1, 2, 3, 4, 5 if (i) No digit is repeated in any number. (ii) Digits can be repeated. Solution : (i) Number of two digit numbers = 5 × 4 = 20 Number of three digit numbers = 5 × 4 × 3 = 60 Number of four digit numbers = 5 × 4 × 3 × 2 = 120 Total = 200 Permutation & Combination (ii) Number of two digit numbers = 5 × 5 = 25 Number of three digit numbers = 5 × 5 × 5 = 125 Number of four digit numbers = 5 × 5 × 5 × 5 = 625 Total = 775 Self Practice Problems : (1) How many 4 digit numbers are there, without repetition of digits, if each number is divisible by 5 ? (2) Using 6 different flags, how many different signals can be made by using atleast three flags, arranging one above the other? Ans. (1) 952 (2) 1920 Arrangements : n If P r denotes the number of permutations (arrangements) of n different things, taking r at a time, then n! n P r = n (n − 1) (n − 2)..... (n − r + 1) = (n − r)! NOTE : (i) Factorials of negative integers are not defined. (ii) 0 ! = 1 ! = 1 n (iii) P n = n ! = n. (n − 1) ! n (iv) (2n) ! = 2 . n ! [1. 3. 5. 7... (2n − 1)] Example # 3 : How many three digit can be formed using the digits 1, 2, 3, 4, 5, without repetition of digits? How many of these are even? Solution : Three places are to be filled with 5 different objects. ∴ Number of ways = 5P3 = 5 × 4 × 3 = 60 For the 2nd part, unit digit can be filled in two ways & the remaining two digits can be filled in 4P2 ways. ∴ Number of even numbers = 2 × 4P2 = 24. Example # 4 : If all the letters of the word 'QUEST' are arranged in all possible ways and put in dictionary order, then find the rank of the given word. Solution : Number of words beginning with E = 4P4 = 24 Number of words beginning with QE = 3P3 = 6 Number of words beginning with QS = 6 Number of words beginning withQT = 6. Next word is 'QUEST' ∴ its rank is 24 + 6 + 6 + 6 + 1 = 43. Self Practice Problems : (3) Find the sum of all four digit numbers (without repetition of digits) formed using the digits 1, 2, 3, 4, 5. (4) Find 'n', if n – 1P3 : nP4 = 1 : 9. (5) (6) Six horses take part in a race. In how many ways can these horses come in the first, second and third place, if a particular horse is among the three winners (Assume No Ties)? Find the sum of all three digit numbers those can be formed by using the digits. 0, 1, 2, 3, 4. Ans. (3) 399960 (4) 9 (5) 60 (6) 27200 Result : Let there be 'n' types of objects, with each type containing atleast r objects. Then the number of ways of arranging r objects in a row is nr. Example # 5 : How many 3 digit numbers can be formed by using the digits 0, 1, 2, 3, 4, 5. In how many of these we have atleast one digit repeated? Solution : We have to fill three places using 6 objects (repetition allowed), 0 cannot be at 100th place. The number of numbers = 180. ∴ Number of numbers in which no digit is repeated = 100 Number of numbers in which atleast one digit is repeated = 180 – 100 = 80 Permutation & Combination Example # 6 : How many functions can be defined from a set A containing 5 elements to a set B having 3 elements? How many of these are surjective functions? Solution : Image of each element of A can be taken in 3 ways. ∴ Number of functions from A to B = 35 = 243. Number of into functions from A to B = 25 + 25 + 25 – 3 = 93. ∴ Number of onto functions = 150. Self Practice Problems : (7) (8) How many functions can be defined from a set A containing 4 elements to a set B containing 5 elements? How many of these are injective functions? In how many ways 5 persons can enter into a auditorium having 4 entries? Ans. (7) 625, 120 (8) 1024. Combination : If nCr denotes the number of combinations (selections) of n different things taken r at a time, then n Pr n ! = where r ≤ n ; n ∈ N and r ∈ W. r! r! (n − r)! NOTE : (i) nCr = nCn – r (ii) nCr + nCr – 1 = n + 1Cr (iii) nCr = 0 if r ∉ {0, 1, 2, 3........, n} n Cr = Example # 7 : There are fifteen players for a cricket match. (i) In how many ways the 11 players can be selected? (ii) In how many ways the 11 players can be selected including a particular player? (iii) In how many ways the 11 players can be selected excluding two particular players? Solution : (i) 11 players are to be selected from 15 Number of ways = 15C11 = 1365. (ii) Since one player is already included, we have to select 10 from the remaining 14 Number of ways = 14C10 = 1001. (iii) Since two players are to be excluded, we have to select 11 from the remaining 13. Number of ways = 13C11 = 78. Example # 8 : If 49C3r – 2 = 49C2r + 1, find 'r'. n Solution : Cr = nCs if either r = s or r + s = n. Thus 3r – 2 = 2r + 1 ⇒ or 3r – 2 + 2r + 1 = 49 ⇒ ∴ r = 3, 10 r=3 5r – 1 = 49 ⇒ r = 10 Example # 9 : A regular polygon has 20 sides. How many triangles can be drawn by using the vertices, but not using the sides? Solution : ∴ ∴ The first vertex can be selected in 20 ways. The remaining two are to be selected from 17 vertices so that they are not consecutive. This can be done in 17C2 – 16 ways. The total number of ways = 20 × (17C2 – 16) But in this method, each selection is repeated thrice. 20 × (17 C2 − 16) = 800. Number of triangles = 3 Example # 10 : 15 persons are sitting in a row. In how many ways we can select three of them if adjacent persons are not selected ? Solution : Let P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 ,P11 , P12 , P13 ,P14 ,P15 be the persons sitting in this order. If three are selected (non consecutive) then 12 are left out. Let P,P,P,P,P,P,P,P,P,P,P,P be the left out & q, q, q be the selected. The number of ways in which these 3 q's can be placed into the 13 positions between the P's (including extremes) is the number ways of required selection. Thus number of ways = 13C3 = 286. Permutation & Combination Example # 11 : In how many ways we can select 4 letters from the letters of the word MΙSSΙSSΙPPΙ? Solution : M ΙΙΙΙ SSSS PP Number of ways of selecting 4 alike letters = 2C1 = 2. Number of ways of selecting 3 alike and 1 different letters = 2C1 × 3C1 = 6 Number of ways of selecting 2 alike and 2 alike letters = 3C2 = 3 Number of ways of selecting 2 alike & 2 different = 3C1 × 3C2 = 9 Number of ways of selecting 4 different = 4C4 = 1 Total number of ways = 2 + 6 + 3 + 9 + 1 = 21 Self Practice Problems : (9) In how many ways 7 persons can be selected from among 5 Indian, 4 British & 2 Chinese, if atleast two are to be selected from each country ? (10) Find a number of different seven digit numbers that can be written using only three digits 1,2&3 under the condition that the digit 2 occurs exactly twice in each number ? (11) In how many ways 6 boys & 6 girls can sit at a round table so that girls & boys sit alternate? (12) In how many ways 4 persons can occupy 10 chairs in a row, if no two sit on adjacent chairs? (13) In how many ways we can select 3 letters of the word PROPORTION ? Ans. (9) 100 (10) 672 (11) 86400 (12) 840 (13) 36 Arrangement of n things, those are not all different : The number of permutations of 'n' things, taken all at a time, when 'p' of them are same & of one type, q of them are same & of second type, 'r' of them are same & of a third type & the remaining n! . n − (p + q + r) things are all different, is p ! q !r ! Example # 12 : In how many ways we can arrange 3 red flowers, 4 yellow flowers and 5 white flowers in a row? In how many ways this is possible if the white flowers are to be separated in any arrangement? (Flowers of same colour are identical). Solution : Total we have 12 flowers 3 red, 4 yellow and 5 white. 12 ! = 27720. Number of arrangements = 3 ! 4 ! 5 ! For the second part, first arrange 3 red & 4 yellow 7 ! = 35 ways This can be done in 3 ! 4 ! Now select 5 places from among 8 places (including extremes) & put the white flowers there. This can be done in 8C5 = 56. ∴ The number of ways for the 2nd part = 35 × 56 = 1960. Example # 13 : In how many ways the letters of the word "ARRANGE" can be arranged without altering the relative positions of vowels & consonants? 4! = 12 ways. Solution : The consonants in their positions can be arranged in 2! 3! = 3 ways The vowels in their positions can be arranged in 2! ∴ Total number of arrangements = 12 × 3 = 36 Permutation & Combination Self Practice Problems : (14) How many words can be formed using the letters of the word ASSESSMENT if each word begin with A and end with T? (15) If all the letters of the word ARRANGE are arranged in all possible ways, in how many of words we will have the A's not together and also the R's not together? (16) How many arrangements can be made by taking four letters of the word MISSISSIPPI? Ans. (14) 840 (15) 660 (16) 176. Formation of Groups : Number of ways in which (m + n + p) different things can be divided into three different groups (m + n + p ) ! , containing m, n & p things respectively is m !n !p ! If m = n = p and the groups have identical qualitative characteristic then the number of groups (3n)! . = n! n! n! 3! Note : If 3n different things are to be distributed equally among three people then the number of ways = (3n)! (n!)3 . Example # 14 : 12 different toys are to be distributed to three children equally. In how many ways this can be done ? Solution : The problem is to divide 12 different things into three different groups. 12! = 34650. Number of ways = 4! 4! 4! Example # 15 : In how many ways 10 persons can be divided into 5 pairs? Solution : We have each group having 2 persons and the qualitative characteristic are same (Since there is no purpose mentioned or names for each pair). 10! = 945. Thus the number of ways = (2!)5 5! Self Practice Problems : (17) 9 persons enter a lift from ground floor of a building which stops in 10 floors (excluding ground floor), if it is known that persons will leave the lift in groups of 2, 3, & 4 in different floors. In how many ways this can happen? (18) In how many ways one can make four equal heaps using a pack of 52 playing cards? (19) In how many ways 11 different books can be parcelled into four packets so that three of the packets contain 3 books each and one of 2 books, if all packets have the same destination? 11! 52! (19) (17) 907200 (18) 4 (3!)4 2 (13!) 4! Ans. Circular Permutation : The number of circular permutations of n different things taken all at a time is (n − 1) !. If clockwise & anti−clockwise circular permutations are considered to be same, then it is (n − 1)! . 2 Note : Number of circular permutations of n things when p are alike and the rest are different, taken all at a (n − 1) ! . time, distinguishing clockwise and anticlockwise arrangement is p! Permutation & Combination Example # 16 : In how many ways can we arrange 6 different flowers in a circle? In how many ways we can form a garland using these flowers? Solution : The number of circular arrangements of 6 different flowers = (6 – 1)! = 120 When we form a garland, clockwise and anticlockwise arrangements are similar. Therefore, the 1 (6 – 1) ! = 60. number of ways of forming garland = 2 Example # 17 : In how many ways 6 persons can sit at a round table, if two of them prefer to sit together? Solution : Let P1, P2, P3, P4, P5, P6 be the persons, where P1, P2 want to sit together. Regard these person as 5 objects. They can be arranged in a circle in (5 – 1)! = 24 ways. Now P1, P2 can be arranged in 2! ways. Thus the total number of ways = 24 × 2 = 48. Self Practice Problems : (20) In how many ways letters of the word 'MONDAY' can be written around a circle, if vowels are to be separated in any arrangement ? (21) In how many ways we can form a garland using 3 different red flowers,5 different yellow flowers and 4 different blue flowers, if flowers of same colour must be together? Ans. (20) 72 (21) 17280 Selection of one or more objects (a) (b) (c) Number of ways in which atleast one object may be selected out of 'n' distinct objects, is n C1 + nC2 + nC3 +...............+ nCn = 2n – 1 Number of ways in which atleast one object may be selected out of 'p' alike objects of one type, 'q' alike objects of second type and 'r' alike objects of third type, is (p + 1) (q + 1) (r + 1) – 1 Number of ways in which atleast one object may be selected from 'n' objects where 'p' alike of one type, 'q' alike of second type and 'r' alike of third type and rest n – (p + q + r) are different, is (p + 1) (q + 1) (r + 1) 2n – (p + q + r) – 1 Example # 18 : There are 12 different books in a shelf. In how many ways we can select atleast one of them? Solution : We may select 1 book, 2 books,........, 12 books. ∴ The number of ways = 12C1 + 12C2 + ....... + 12C12 = 212 – 1. = 4095 Example # 19 : There are 11 fruits in a basket of which 6 are apples, 3 mangoes and 2 bananas (fruits of same species are identical). How many ways are there to select atleast one fruit? Solution : Let x be the number of apples being selected y be the number of mangoes being selected and z be the number of bananas being selected. Then x = 0, 1, 2, 3, 4, 5,6 y = 0, 1, 2, 3 z = 0, 1, 2 Total number of triplets (x, y, z) is 7 × 4 × 3 = 84 Exclude (0, 0, 0) ∴ Number of combinations = 84 – 1 = 83. Self Practice Problems (22) In a shelf there are 6 physics, 4 chemistry and 3 mathematics books. How many combinations are there if (i) books of same subject are different? (ii) books of same subject are identical? (23) From 5 apples, 4 mangoes & 3 bananas, in how many ways we can select atleast two fruits of each variety if (i) fruits of same species are identical? (ii) fruits of same species are different? Results : Ans. (22) (i) 8191 (ii) 139 (23) (i) 24 (ii) 212 – 4 Let N = pa. qb. rc...... where p, q, r...... are distinct primes & a, b, c..... are natural numbers then: (a) The total numbers of divisors of N including 1 & N is = (a + 1) (b + 1) (c + 1)........ (b) The sum of these divisors is = (p0 + p1 + p2 +.... + pa) (q0 + q1 + q2 +.... + qb) (r0 + r1 + r2 +.... + rc)........ (c) Number of ways in which N can be resolved as a product of two factors is Permutation & Combination 1 if N is not a perfect square  (a + 1) (b + 1) (c + 1) .... =  12  2 (a + 1) (b + 1) (c + 1) .... + 1 if N is a perfect square (d) Number of ways in which a composite number N can be resolved into two factors which are relatively prime (or coprime) to each other is equal to 2n−1 where n is the number of different prime factors in N. Example # 20 : Find the number of divisors of 1350. Also find the sum of all divisors. Solution : 1350 = 2 × 33 × 52 ∴ Number of divisors = (1+ 1) (3 + 1) (2 + 1) = 24 sum of divisors = (1 + 2) (1 + 3 + 32 + 33) (1 + 5 + 52) = 3720. Example # 21 : In how many ways 8100 can be resolved into product of two factors? Solution : 8100 = 22 × 34 × 52 Number of ways = 1 [(2 + 1) (4 + 1) (2 + 1) + 1] = 23 2 Self Practice Problems : (24) How many divisors of 9000 are even but not divisible by 4? Also find the sum of all such divisors. (25) In how many ways the number 8100 can be written as product of two coprime factors? Ans. (24) 12, 4056 (25) 4 Negative binomial expansion : (1 – x)– n = 1 + nC1x + n + 1C2 x2 + n + 2C3x3 + ........ to ∞ , if – 1 < x < 1. Coefficient of xr in this expansion = n+r−1 Cr (n ∈ N) Result : Number of ways in which it is possible to make a selection from m + n + p = N things, where p are alike of one kind, m alike of second kind & n alike of third kind, taken r at a time is given by coefficient of xr in the expansion of (1 + x + x2 +...... + xp) (1 + x + x2 +...... + xm) (1 + x + x2 +...... + xn). For example the number of ways in which a selection of four letters can be made from the letters of the word PROPORTION is given by coefficient of x4 in (1 + x + x2 + x3) (1 + x + x2) (1 + x + x2) (1 + x) (1 + x) (1 + x). Method of fictious partition : Number of ways in which n identical things may be distributed among p persons if each person may receive none, one or more things is n+p−1Cn. Example # 22 : Find the number of solutions of the equation x + y + z = 6, where x, y, z ∈ W. Solution : Number of solutions = coefficient of x6 in (1 + x + x2 + ....... x6)3 = coefficient of x6 in (1 – x7)3 (1 – x)–3 = coefficient of x6 in (1 – x)–3 = 3+6–1C6 = 8C2 = 28. Example # 23 : In a bakery four types of biscuits are available. In how many ways a person can buy 10 biscuits if he decide to take atleast one biscuit of each variety? Solution : Let the person select x biscuits from first variety, y from the second, z from the third and w from the fourth variety. Then the number of ways = number of solutions of the equation x + y + z + w = 10. where x = 1, 2, .........,7 y = 1, 2, .........,7 z = 1, 2, .........,7 w = 1, 2, .........,7 So, number of ways = coefficient of x10 in (x + x2 + ...... + x7)4 = coefficient of x6 in (1 + x + ....... + x6)4 Permutation & Combination = coefficient of x6 in (1 – x7)4 (1 – x)–4 = coefficient x6 in (1 – x)–4 = 4+6–1C6 = 9C3 = 84 Self Practice Problems: (26) Three distinguishable dice are rolled. In how many ways we can get a total 15? (27) In how many ways we can give 5 apples, 4 mangoes and 3 oranges (fruits of same species are similar) to three persons if each may receive none, one or more? Ans. (26) 10 (27) 3150 Derrangements : Number of ways in which 'n' letters can be put in 'n' corresponding envelopes such that no letter goes to  1 1 1 1 1  correct envelope is n !  1 − + − + − .......... + ( −1)n  n !  1 ! 2 ! 3 ! 4 ! Example # 24 : In how many ways we can put 5 writings into 5 corresponding envelopes so that no writing go to the corresponding envelope? Solution : The problem is the number of dearragements of 5 digits.  1 1 1 1  This is equal to 5!  − + −  = 44. 2 ! 3 ! 4 ! 5 !  Example # 25 : Four slip of papers with the numbers 1, 2, 3, 4 written on them are put in a box. They are drawn one by one (without replacement) at random. In how many ways it can happen that the ordinal number of atleast one slip coincide with its own number? Solution : Total number of ways = 4 ! = 24. The number of ways in which ordinal number of any slip does not coincide with its own number  1 1 1  is the number of dearrangements of 4 objects = 4 !  − + =9 2 ! 3 ! 4 ! Thus the required number of ways. = 24 – 9 = 15 Self Practice Problems: (28) In a match the column question, Column Ι contain 10 questions and Column II contain 10 answers written in some arbitrary order. In how many ways a student can answer this question so that exactly 6 of his matching are correct ? (29) In how many ways we can put 5 letters into 5 corresponding envelopes so that atleast one letter go to wrong envelope ? Ans. (28) 1890 (29) 119 Exponent of prime p in n! : Let p be a prime number, n be a positive integer and Let E p (n) denote the exponent of the prime p in the positive integer n. Then, n n   n   n  Ep (n!) =  +  2  +  3  + ...... +  s  p  p  p  p  where s is the largest positive integer such that p ≤ n < p s s+1 Permutation & Combination Example # 26 : Find exponent 2 and 3 in 100! Solution :  100   100   100   100  Exponent of 2 in 100! is represented by E2 (100!) =   +  22  +  23  + ...... +  26  2         = 50 + 25 + 12 + 6 + 3 + 1 = 97  100   100   100   100  Exponent of 3 in 100! is represented by E3 (100!) =  + 2 + 3 + 4   3   3   3   3  = 33 +11 + 3 + 1 = 48 Example # 27 : If 100! is divided by (24) (where k ∈ n), then find maximum value of k. k Solution :  100   100   100   100  Exponent of 2 in 100! is represented by E2 (100!) =   +  22  +  23  + ...... +  26  2         = 50 + 25 + 12 + 6 + 3 + 1 = 97 ⇒ 3 Exponent of 2 in 100! is 32.  100   100   100   100  Exponent of 3 in 100! is represented by E3 (100!) =  + 2 + 3 + 4   3   3   3   3  = 33 +11 + 3 + 1 = 48 ⇒ Exponent of (2 × 3) in 100! is min{48, 32} = 32 ⇒ Exponent of (24) in 100! is = 32 ⇒ maximum value of k is 32. 3 Self Practice Problems: (30) Find the number of zeros at the end of (31) Find the last non zero digits of 25!. Ans (30) 0 (31) 4 50 C 25 .