Mathematics-8.Unit-5.01-Permutation & Combination

Unit – 05 PERMUTATION & COMBINATION COUNTING PRINCIPLES There are two fundamental counting principles viz. Multiplication principle and Addition principle. Multiplication Principle: If one experiment has n possible outcomes and another experiment has m possible outcomes, then there are m × n possible outcomes when both of these experiments are performed. Illustration 1: A college offers 7 courses in the morning and 5 in the evening. Find the possible number of choices with the student if he wants to study one course in the morning and one in the evening. Solution: The student has seven choices from the morning courses out of which he can select one course in 7 ways. For the evening course, he has 5 choices out of which he can select one in 5 ways. Hence the total number of ways in which he can make the choice of one course in the morning and one in the evening = 7 × 5 = 35. Illustration 2: A person wants to go from station A to station C via station B. There are three routes from A to B and four routes from B to C. In how many ways can he travel from A to C? Solution: A → B in 3 ways B → C in 4 ways ⇒ A → C in 3 × 4 = 12 ways Remark: The rule of product is applicable only when the number of ways of doing each part is independent of each other i.e. corresponding to any method of doing the first part, the other part can be done by any method. Illustration 3: How many (i) 5-digit (ii) 3-digit numbers can be formed by using 1, 2, 3, 4, 5 without repetition of digits. Solution: (i) Making a 5-digit number is equivalent to filling 5 places. Places: Number of Choices: The first place can be filled in 5 ways using anyone of the given digits. The second place can be filled in 4 ways using any of the remaining 4 digits. Similarly, we can fill the 3rd, 4th and 5th place. No. of ways of filling all the five places = 5 × 4 × 3 × 2 × 1 = 120 ⇒ 120 5-digit numbers can be formed. (ii) Making a 3-digit number is equivalent to filling 3 places. Places: Number of Choices: 5 4 3 Number of ways of filling all the three places = 5 × 4 × 3 = 60 Hence the total possible 3-digit numbers = 60. Addition principle: If one experiment has n possible outcomes and another has m possible outcomes, then there are (m + n) possible outcomes when exactly one of these experiments is performed. In other words, if a job can be done by n different methods and for the first method there are a1 ways, for the second method there are a2 ways and so on . . . for the nth method, an ways, then the number of ways to get the job done is (a1 + a2 + ... + an). Illustration 4: A college offers 7 courses in the morning and 5 in the evening. Find the number of ways a student can select exactly one course, either in the morning or in the evening. Solution: The student has seven choices from the morning courses out of which he can select one course in 7 ways. For the evening course, he has 5 choices out of which he can select one course in 5 ways. Hence he has total number of 7 + 5 = 12 choices. PERMUTATIONS (ARRANGEMENT OF OBJECTS) The number of permutations of n objects, taken r at a time, is the total number of arrangements of r objects, selected from n objects where the order of the arrangement is important. Without Repetition: (a) Arranging n objects, taken r at a time is equivalent to filling r places from n things. r−Places: Number of Choices: The number of ways of arranging = The number of ways of filling r places = n(n – 1) (n – 2) ….. (n – r + 1) = = = nPr (b) The number of arrangements of n different objects taken all at a time = npn = n! With Repetition: (a) The number of permutations (arrangements) of n different objects, taken r at a time, when each object may occur once, twice, thrice…. upto r times in any arrangement = The number of ways of filling r places where each place can be filled by any one of n objects . r−Places: Number of Choices: n n n n n The number of permutations = The number of ways of filling r places = (n)r (b) The number of arrangements that can be formed using n objects out of which p are identical (and of one kind), q are identical (and of another kind), r are identical (and of another kind) and the rest are distinct is . Illustration 5: (a) How many anagrams can be made by using the letters of the word HINDUSTAN. (b) How many of these anagrams begin and end with a vowel. (c) In how many of these anagrams, all the vowels come together. (d) In how many of these anagrams, none of the vowels come together. (e) In how many of these anagrams, do the vowels and the consonants occupy the same relative positions as in HINDUSTAN. Solution: (a) The total number of anagrams = Arrangements of nine letters taken all at a time = = 181440. (b) We have 3 vowels and 6 consonants, in which 2 consonants are alike. The first place can be filled in 3 ways and the last in 2 ways. The rest of the places can be filled in ways. Hence the total number of anagrams = 3 × 2 × = 15120 (c) Assume the vowels (I, U, A) as a single letter. The letters (IUA) H, D, S, T, N, N can be arranged in ways. Also IUA can be arranged among themselves in 3! = 6 ways. Hence the total number of anagrams = × 6 = 15120 (d) Let us divide the task into two parts. In the first, we arrange the 6 consonants as shown below in ways. × C × C × C × C × C × C × (C stands for consonants and × stands for blank spaces inbetween them) Now 3 vowels can be placed in 7 places (in between the consonants) in 7p3 = = 210 ways. Hence the total number of anagrams = × 210 = 75600. (e) In this case, the vowels can be arranged among themselves in 3! = 6ways. Also, the consonants can be arranged among themselves in ways. Hence the total number of anagrams = × 6 = 2160. Illustration 6: How many 3 digit numbers can be formed using the digits 0, 1,2,3,4,5 so that (a) digits may not be repeated (b) digits may be repeated Solution: (a) Let the 3-digit number be XYZ Position (X) can be filled by 1,2,3,4,5 but not 0. So it can be filled in 5 ways. Position (Y) can be filled in 5 ways again. (Since 0 can be placed in this postion). Position (Z) can be filled in 4 ways. Hence, by the fundamental principle of counting, total number of ways is 5 x 5 x 4 = 100 ways. (b) Let the 3 digit number be XYZ Position (X) can be filled in 5 ways Position (Y) can be filled in 6ways. Position (Z) can be filled in 6 ways. Hence by the fundamental principle of counting, total number of ways is 5 x 6 x 6 = 180. CIRCULAR PERMUTATIONS TThere are arrangements in closed loops also, called as circular arrangements. Suppose n persons (a1, a2, a3,…,an) are to be arranged around a circular table. The total number of circular arrangements of n persons is = (n – 1)!. Distinction between clockwise and anti-clockwise Arrangements: Consider the following circular arrangements: In figure I, the order is clockwise whereas in figure II, the order is anti-clock wise. These are two different arrangements. When distinction is made between the clockwise and the anti-clockwise arrangements of n different objects around a circle, then the number of arrangements = (n – 1)! But if no distinction is made between the clockwise and the anti-clockwise arrangements of n different objects around a circle, then the number of arrangements is (n – 1)! For an example, consider the arrangements of beads (all different) on a necklace as shown in figures A and B. Look at (A) having 3 beads x1, x2, x3 as shown. Flip (A) over on its right. We get (B) at once. However, (A) and (B) are really the outcomes of one arrangement but are counted as two different arrangements in our calculation. To nullify this redundancy, the actual number of different arrangements is (n-1)!/2. Remarks: When the positions are numbered, circular arrangement is treated as a linear arrangement. In a linear arrangement, it does not make difference whether the positions are numbered or not. Illustration 7: Consider 23 different coloured beads in a necklace. In how many ways can the beads be placed in the necklace so that 3 specific beads always remain together? Solution: By theory, let us consider 3 beads as one. Hence we have, in effect, 21 beads, 'n' = 21. The number of arrangements = (n-1)! = 20! Also, the number of ways in which 3 beads can be arranged between themselves is 3! = 3 x 2 x 1 = 6. Thus the total number of arrangements = (1/2). 20!. 3!. Illustration 8: In how many ways 10 boys and 5 girls can sit around a circular table so that no two girls sit together. Solution: 10 boys can be seated in a circle in 9! ways. There are 10 spaces inbetween the boys, which can be occupied by 5 girls in 10p5 ways. Hence total number of ways = 9! 10p5 = . COMBINATIONS Meaning of combination is selection of objects. Selection of Objects without Repetition: The number of selections (combinations or groups) that can be formed from n different objects taken r (0 ≤ r ≤ n) at a time is Selection of objects with repetition: The number of combinations of n distinct objects, taken r at a time when each may occur once, twice, thrice,….. upto r times in any combination is nHr = n+r-1Cr . Illustration 9: Let 15 toys be distributed among 3 children subject to the condition that any child can take any number of toys. Find the required number of ways to do this if (i) toys are distinct. (ii) toys are identical. Solution: (i) Toys are distinct Here we have 3 children and we want the 15 toys to be distributed to the 3 children with repetition. In other words, it is same as selecting and arranging children 15 times out of 3 children with the condition that any child can be selected any no. of time, which can be done in 315 ways (n = 3, r = 15). (ii) Toys are identical Here we only have to select children 15 times out of 3 children with the condition that any child can be selected any number of times which can be done in 3 + 15 - 1C15 = 17C2 ways (n = 3, r = 5). RESTRICTED SELECTION / ARRANGEMENT (a) The number of ways in which r objects can be selected from n different objects if k particular objects are (a) always included = n-k Cr-k (b) never included = n-k Cr (b) The number of arrangements of n distinct objects taken r at a time so that k particular objects are (a) always included = n-k Cr-k .r! (b) never included = n-k Cr .r! Illustration 10: A delegation of four students is to be selected from a total of 12 students. In how many ways can the delegation be selected (a) If all the students are equally willing. (b) If two particular students have to be included in the delegation. (c) If two particular students do not wish to be together in the delegation. (d) If two particular students wish to be included together only. (e) If two particular students refuse to be together and two other particular student wish to be together only in the delegation. Solution: (a) Formation of delegation means selection of 4 out of 12. Hence the number of ways = 12C4 = 495. (b) If two particular students are already selected. Here we need to select only 2 out of the remaining 10. Hence the number of ways = 10C2 = 45. (c) The number of ways in which both are selected = 45. Hence the number of ways in which the two are not included together = 495 – 45 = 450. (d) There are two possible cases (i) Either both are selected. In this case, the number of ways in which the selection can be made = 45. (ii) Or both are not selected. In this case all the four students are selected from the remaining ten students. This can be done in 10C4 = 210 ways. Hence the total number of ways of selection = 45 + 210 = 255. (e) We assume that students A and B wish to be selected together and students C and D do not wish to be together. Now there are following 6 cases. (i) (A, B, C) selected, (D) not selected (ii) (A, B, D) selected (C) not selected (iii) (A, B) selected (C, D) not selected (iv) (C) selected (A, B, D) not selected (v) (D) selected (A, B, C) not selected (vi) A, B, C, D not selected For (i) the number of ways of selection = 8C1 = 8 For (ii) the number of ways of selection = 8C1 = 8 For (iii) the number of ways of selection = 8C2 = 28 For (iv) the number of ways of selection = 8C3 = 56 For (v) the number of ways of selection = 8C3 = 56 For (vi) the number of ways of selection = 8C4 = 70 Hence total number of ways = 8 + 8 + 28 + 56 + 56 + 70 = 226. Some Results Related to nCr: (i) nCr = nCn-r (b) If nCr = nCk , then r = k or n-r =k (c) nCr + nCr-1 = n+1Cr (d) nCr = n-1Cr-1 (v) (vi) (a) If n is even , nCr is greatest for r = n/2 (b) If n is odd, nCr is greatest for r = , Illustration 11: (a) How many diagonals are there in an n-sided polygon (n> 3). (b) How many triangles can be formed by joining the vertices of an n- sided polygon. How many of these triangles have (i) exactly one side common with that of the polygon (ii) exactly two sides common with that of the polygon (iii) no sides common with that of the polygon Solution: (a) The number of lines formed by joining the n vertices of a polygon = number of selections of 2 points from the given n points = nC2 = Out of nC2 lines , n lines are the sides of the polygon. Hence the number of diagonals = nC2 –n = -n = . (b) Number of triangles formed by joining the vertices of the polygon = number of selections of 3 points from n points. =nC3 = . Let the vertices of the polygon be marked as A1, A2,A3,------An. (i) Select two consecutive vertices A1, A2 of the polygon. For the required triangle, we can select the third vertex from the points A4,A5, -----An-1 . This can be done in n-4C1 ways. Also two consecutive points (end points of a side of polygon) can be selected in n ways. Hence the total number of required triangles =n. n-4C1 = n(n-4). (ii) For the required triangle, we have to select three consecutive vertices of the polygon. i.e. (A1 A2 A3), (A2 A3 A4), (A3 A4 A5),----------- ,(An A1 A2). This can be done in n ways. (iii)Triangles having no side common + triangles having exactly one side common + triangles having exactly two sides common (with those of the polygon) = Total number of triangles formed ⇒ Triangles having no side common with those of the polygon = nC3 – n(n-4) –n = -n(n-4) –n = = = . ALL POSSIBLE SELECTIONS Selection from Distinct Objects: The number of selections from n different objects, taken at least one = nC1 + nC2 + nC3 + ------ + nCn = 2n - 1. ASSIGNMENT 1. In a chass tournament, all participants were to play one game with the other. Two players fell ill after having played 3 games each. If total number of games played in the tournament is equal to 84, then total number of participants in the beginning was equal to: (A) 10 (B) 15 (C) 12 (D) 14 2. Number of ways in which four letter of the word ‘DEGREE’ can be selected is (A) 7 (B) 6 (C) (D) none of these. 3. If letters of the word ‘KUBER’ are written in all possible orders and arranged as in a dictionary, then rank of the word ‘KUBER’ will be: (A) 67 (B) 68 (C) 65 (D) 69 4. A is a set containing n elements. A subset P of A is chosen. The set A is reconstructed by replacing the elements of P. A subset Q of A is again chosen. The number of ways of chosen P and Q so that P ∩Q =  is (A) 22n – 2nCn (B) 2n (C) 2n – 1 (D) 3n 5. Total number of 3 letters words that can be formed from the letters of the word ‘SAHARANPUR’, is equal to: (A) 210 (B) 237 (C) 247 (D) 227 6. If n objects are arranged in a row, then the number of ways of selecting three objects so that no two of them are next to each other is (A) (B) n-2C3 (C) n-3C3 + n-3C2 (D) none of these. 7. A teacher takes 3 children from her class to the zoo at a time as often as she can, but she doesn’t take the same set of three children more than once. She finds out that she goes to the zoo 84 times more than a particular child goes to the zoo, Total number of students in her class in equal to: (A) 12 (B) 14 (C) 10 (D) 11 8: Five balls of different colours are to be placed in three boxes of different sizes. Each box can hold all five balls. The number of ways in which we can place the balls in the boxes ( order is not considered in the box) so that no box remains empty is (A) 150 (B) 300 (C) 200 (D) none of these 9. Total number of ways of selecting two numbers from the set {1, 2, 3, 4, …., 3n} so that their sum is divisible by 3 is equal to: (A) (B) (C) (D) 10: There are 20 persons among whom are two brothers. The number of ways in which we can arrange them around a circle so that there is exactly one person between the brothers is . (A) 19! (B) 2 18! (C) 2! 17! (D) none of these 11. Total number of 4 digit number that are greater than 3000, that can be formed using the digits 1, 2, 3, 4, 5, 6 (no digit is being repeated in any number) is equal to: (A) 120 (B) 240 (C) 480 (D) 80 12. Let A be the set of 4-digit numbers a1a2a3a4 where a1> a2> a3> a4, then n(A) is equal to (A) 126 (B) 84 (C) 210 (D) none of these 13. The total number of flags with three horizontal strips, in order, that can be formed using 2 identical red, 2 identical green and 2 identical white strips, is equal to: (A) 4! (B) 3.(4!) (C) 2.(4!) (D) None of these 14. Two teams are to play a series of 5 matches between them. A match ends in a win or loss or draw for a team. A number of people forecast the result of each match and no two people make the same forecast for the series of matches. The smallest group of people in which one person forecasts correctly for all the matches will contain n people, where n is (A) 81 (B) 243 (C) 486 (D) none of these 15. Total number of four digit numbers having all different digits, is equal to (A) 4536 (B) 504 (C) 5040 (D) 720 16. The number of ways in which 6 men can be arranged in a row so that three particular men are consecutive, is (A) 4P4 (B) 4P4 × 3P3 (C) 6P6 × 3P3 (D) 3P3 × 3P3 17. Total number of ways in which a person can put 8 different rings in the figures of his right hand is equal to: (A) (B) (C) (D) 18. Value of expression 47C4 + is equal to (A) 52C4 (B) 52C2 (C) 52C6 (D) none of these 19. A convex polygon has 44 diagonals. The number of it’s sides is equal to: (A) 9 (B) 10 (C) 11 (D) 12 20. A polygon has 65 diagonals. The number of its sides is (A) 8 (B) 10 (C) 11 (D) 13 21. Everybody in a room shakes hand with everybody else. The total number of hand shake is equal to 153. The total number of persons in the room is equal to: (A) 18 (B) 19 (C) 17 (D) 16 22. Number of triangles that can be formed joining the angular points of decagon is (A) 30 (B) 20 (C) 90 (D) 120 23. A class contains 3 girls and four boys. Every Saturday five students go on a picnic, a different group of students is being sent each week. During the picnic, each girl in the group is given a doll by the accompanying teacher. All possible groups of five have gone once, the total number of dolls the girls have got is: (A) 21 (B) 45 (C) 27 (D) 24 24. The number of all the odd divisor of 3600 is (A) 45 (B) 4 (C) 18 (D) 9 25. There are ‘n’ numbered seats around a round table. Total number of ways in which persons can sit around the round table, is equal to: (A) (B) (C) (D) 26. Number of permutations of n different objects taken r (≥ 3) at a time which includes 3 particular objects, is (A) nPr × 3! (B) nPr−3 × 3! (C) n−3Pr−3 (D) rP3 × n−3Pr−3 27. Total number of words that can be formed using the alphabets of the word KUBER, so that no alphabet is repeated in any of the formed word, is equal to (A) 325 (B) 320 (C) 240 (D) 365 28. The number of words from the letters of the word ‘BHARAT’ in which B and H never come together is (A) 360 (B) 240 (C) 120 (D) none of these 29. The total number of three digit numbers, the sum of whose digits is even, is equal to: (A) 450 (B) 350 (C) 250 (D) 325 30. Number of ways 6 different flowers can be given to 10 girls, if each can receive any number of flowers is (A) 610 (B) 106 (C) 60 (D) 10C6 ANSWER SHEET 1. A 11. B 21. A 2. A 12. C 22. D 3. A 13. A 23. B 4. D 14. B 24. D 5. C 15. A 25. B 6. A, B, C 16. B 26. D 7. C 17. B 27. A 8. A 18. A 28. B 9. B 19. C 29. A 10. B 20. D 30. B