PERMUTATIONS AND C 7.1 Introduction Chapter vi TIONS Sometimes we come across problems of counting and choosing as follows : ‘We want to form three digit numbers using digits 1, 2 and 3 without repetition of any digit in any number. How many such numbers can be formed ? ‘We can choose first digit as 1, 2 or 3. Since we do not wish to repeat any digit, the second digit can be chosen in two ways from 1,2, 3 excluding the digit chosen. The digit left is the third digit. Look at the tree in figure 7.1. Six numbers 123, 132, 213, 231, 312, 321 can be formed. Rucha has two tops and three matching pants and two pairs of shoes. She wants to go to a party. In how many ways can she dress herself ? Figure 7.2 ne wv AANA Let the tops be called T, and T>. Let the pants be called P), P,, P3 and let pairs of shoes be called $, and Sy. Consider the tree in figure 7.2. So the possible combinations are T,P,Sj, T,P)Sp, T P28), T,P2S. T,P38,, T,P382, T,P,S, TP yS», T>P,$1, TPS, T,P3S;, T,P3S, i.e. 12 in all.176 MATHEMATICS Dev has three school bags, two lunchboxes and two ballpens. In how many ways can he choose to go to school with one item of each type ? Let the bags be called B,, By, B, the lunchboxes be called C,, C, and the pens be called P), P,. Possible combinations are B;C,P,, B,C,P>, ByC>P,, ByC,P>, ByC,P,, ByC,P), 4P}, ByC>P,, B3C,Py, ByC,P,, ByCP;, ByC,P>. Again in 12 ways ! ‘Now this type of listing is tedious and not always possible ! We wish to try a password to open file. The password consists of six different digits. How many trials will be required ? 10 x 9 X 8 X 7 X 6 X 5 = 151200! This type of counting problems are solved by fundamental principle of counting or multiplication principle. Fundamental Principle of Counting : If an event can occur in m ways and corresponding to each way another event can occur in p ways, the total number of occurrences of the events is mp. In fact if A is the set of elements of occurrences of the first event and B is the set of elements of occurrences of the second event, we know n(A) = m, n(B) = p and therefore n(A X B) = mp. Similarly if one event can occur in p ways and corresponding to it a second event can occur in g ways and corresponding to them a third event can occur in r ways, then the three events together can occur in pgr ways. Now in earlier example first event (selection of top by Rucha) can occur in 2 ways, second event (selection of pants by Rucha) can occur in 3 ways and selection of shoes can occur in 2 ways. Hence Rucha can dress herself in 2 X 3 X 2 = 12 ways. Similarly Dev can prepare schoolbag in 3 X 2 X 2 = 12 ways. Thus fundamental principle of counting gives precise results without elaborate listing, Example 1 : How many four digit numbers can be formed using 1, 2, 4, 6, 8 ? (Repetition of digits is not allowed.) Solution : We have to fill four places : unit place, tens place, hundred place and thousand place using 5 digits. Th HO Ten U First place can be filled in 5 ways. Since repetition is not allowed, so second, third and fourth place can be [ [11] filled in corresponding 4, 3 and 2 ways respectively. Hence according to the fundamental principle of counting, the number of four digit numbers formed using 1, 2, 4, 6, 8 is 5X 4X3X2= 120. Example 2 : How many four letter words (with or without meaning or dictionary occurrence and without repetition of letter) can be formed using letters of the word KENY ? How many of them will have first letter E ? Solution : Four letters words using K, E, N, Y are 4 X 3 X 2 X | in number. The number of words is 24. If the first letter is E, consider the box [E] | |]. We have to fill three places with three letters K, N, Y. Hence their number is 3+2+1 = 6.PERMUTATIONS AND COMBINATIONS 177 Example 3 : How many three digit even numbers can be formed using digits 0, 1, 2,... 9 2 (No repetition of digits) Solution ; Last digit has to be 0, 2, 4, 6 or 8 to form an even number. Consider the above array. If the last digit is zero, other two digits can be chosen in 9 X 8 = 72 ways. If the last digit is 2, first digit can be choosen in 8 ways (it cannot be zero) and second also in 8 ways (now zero is allowed). Thus 8 X 8 = 64 numbers with each of 2, 4, 6, 8 as last digit are formed. Therefore the total number is 64 X 4 + 72 = 328. (Think : How many odd ? How many total 2) Example 4 : How many three digit numbers are there which do not contain 2 at all ? Which contain 2 at least once ? Which contain 2 at most once ? (See that repetitions is allowed.) Solution : First digit can be any one of 1, 3, 4, 5.5 9. [ [1] Second digit can be any one of 0, 1, 3, 4, 5,...9. Third digit can be any one of 0, 1, 3, 4, Syn 9 Total number of three digit numbers not having 2 at all is 8X9X9 = 648. (i) Now, total number of three digit numbers is 9X 10 X 10=900 (First digit is non-zero) 900 — 648 = 252 contain 2 at least once. @ 2 at most once means numbers occuring not having 2 at all and numbers having 2 once. Their number is, 900 (total) — (numbers having 2 in all the places + numbers having 2 in exactly two places) ‘Numbers having 2 in all the places is 222 (one only). ‘Numbers having 2 in two places (but not all) are The blank space can be chosen in 9 + 8 +9 = Total number of numbers having 2 in at least two places is 27. 900 — 27 = 873 numbers contain 2 in at most one place. Git) Example 5 : In how many ways can small B triangles in figure 7.3 (AABP, ABQC, “ c ABPQ, APQR) be coloured using fundamental colours RBY (Red, Blue, P ‘Q Yellow) so that no two adjacent regions are coloured using the same colour ? Solution : ABPQ has boundary R touching all regions. Figure 7.3 6 ways.178 MATHEMATICS It can be coloured using 3 colours in 3 ways. Other three regions can be coloured in 2X 2X 2=8 ways. The four regions can be coloured in 3 X 8 = 24 ways. Example 6 : How many five letter passwords can be generated using first three letters as any of the English alphabets and last two being any digit from 0 to 9? (See repetition is allowed.) Solution : First three letters can be chosen in LL] l 26 X 26 X 26 ways and last two in 10 X 10 ways. Hence the possible number of passwords is 26 X 26 X 26 X 10 X 10 = 1757600. EXERCISE 1. How many signals can be formed using five different flags of different colours lying in a row on vertical masts ? Each signal may contain 2 or more flags of different colours. 2. How many odd numbers of four digits are there ? (No repetition of digits.) 3. How many words can be formed using all alphabates of the word TULSI ? (No repetitions) How many start with T ? How many end in 1? 4. How many three digit numbers are there which are multiples of 5 ? (Without repetition of digits) 5. How many cars are there with numbers like GJ-X-AB-abcd where X is any digit from 1 to 9; A is H; B is any one of alphabets in English and abed is a four digit number ? (a can be zero) 6. How many numbers are there between 99 and 1000 (i) having last digit 0, (ii) having last digit 5, (iii) divisible by 4, (iv) divisible by 2 but not by 4? 7. Dev wants to create a password with five letters for his e-mail account with following properties. (1) First three letters should be any of the English alphabets so that none of the alphabets of his name occur in any order. (2). The remaining two should be any digits from 0 to 9 but they do not represent his age. In how many ways can he do this ? Dev is 12 years old. * 7.2 Permutations The problems we studied in earlier section deal with arrangement of objects in definite order. To determine the number of three digit numbers using 1, 2, 3, 4 involves arrangements like 123, 124, 234,...etc. Here we are counting number of ‘permutations’ of 4 digits taken 3 at a time. Their number is 4 x 3 x 2 = 24, (Fundamental principle of counting).PERMUTATIONS AND COMBINATIONS 179 Definition : A permutation is an arrangement in a definite order of a number of distinct objects taking some or all at a time, The number of lincar permutations of n different objects taking r at a time where 1 Sr S ny, r @N and n EN is denoted by the symbol ,P,, if repetitions of objects is not allowed and arrangement is linear. The arrangement also called a linear permutation. Theorem 1: ,P, = n(n — 1) — 2). — 7 + 1) The number of permutations is the number of ways in which r places can be filled with n different objects in the following vacant places. (without repetition) r places The first place can be filled with any of n objects and this is possible in n ways. Since there is no repetition, correspondingly second place can be filled in (n — 1) ways, third place in (n — 2) ways etc. The last rth place can be filled in n— (r= 1) ways. (Earlier (r — 1) places are filled.) By the fundamental principle of counting. oP, = a(n — 10 = 2un(a — 7 + 1) Start with n, decreasing by 1 each time, write r integers and multiply all of them. For example 7P; = 7X 6 X 5 = 210 Py =n — In — 2)..(n — n+ 1) = nln = 1M = 2). There is a special symbol for this product n(n — 1)(m — 2)...1 and it is called factorial n and is denoted by n! (read ‘n-factorial’) or [7 Thus, ,P, = n! I= 1, 22=2+1=2,3!=3-2+ 1 n 6, 41 = 4-3-+2+1 = 24 ete. Now, n! = n(n — 1\(n — 2 = n(n = 1)! = nn — 1X — 2)! = nn 1).(n =r + Yn = DL coma = Dun =r = GT 1Sr| [Ws] |Wy three medals are assigned. Each of space Wy, W,, W3, W, can be filled in three ways (repetition allowed). Hence Dev can get a medal in 34 = 81 ways. Example 16 : How many four digit numbers can be formed using 5, 2, 3, 7, 8 ? Solution : There are four places and each can be filled in 5 ways with 5, 2, 3, 7, or 8. 54 = 625 numbers can be formed. (See n= 5 things to be arranged in r = 4 places in n” = 54 = 625 ways.) Note] If we want six digits numbers, it is possible in 5° Here r > n is possible unlike in ,P,, r SPERMUTATIONS AND COMBINATIONS 183 Example 17 : How many permutations of all alphabets of the word DAUGHTER is possible without repetition ? In how many of them vowels and consonants will be in their positions only ? Solution : There are 8 different letters in the given word. Hence there are 8! = 40320 permutations. But if the vowels A, U, E and consonants D, G, H, T, R remain in their places but can be mutually rearranged then the number of permutations is 3! x 5! = 6 X 120 = 720. Example 18 : If n(A) = m and n(B) = n (mm, n © N), then how many functions from A to B are there ? Solution ; Let A = (x), x5, x3). B= Op Ya Yare Then f= {(xp y,)}, where x, € A, y, € B so that no x; is repeated and no x, from A is left out without occurrence in some pair in f. Thus, each x; can correspond to some yy in m ways. Thus there are n Xn X n....m times choices for set f. Number of functions is n™. ‘© Note] Let A = {1, 2, 3}, B = {a, b} A, = (4,24), 3,9} fy = (A, 4), 2, 5), GB, B} Fy = 0, a), 2 2), Bd} fy = {C1 4), @ 4), G, a} Fs = {C, @), 2, 5), GB, 9} fg = {C1 4), 2, &), G, B)} ty, = (0,4), 24, 3,0} fe = (0, 2), 2, 5), G, 5} 23 =8 functions f: A — B exists. EXERCISE 7.2 1. Evaluate : (1) gP4 (2) oP3 G) gg 2 Evaluate : (1) 6! 2) @) 4 P, . sP 3. Prove P=, iP, +r, Pp1) 4 Find r (1) Gp 1 QP=78, . Pr +6 5. Find n: 7,P; = 20 4 Pp 6. If [B-, = 30800, find r. 7. Prove ,P, =", 1Pp_4 8. Find n, if (7 + 1)! = 12(n — It 9. If 2, find n. n! nt B= DW! * anal 10. How many three digit even numbers can be formed using digits of 2468 ? (With or without repetition.)11. 12. 13. 14, 15. 16. 17, 18. 19. 20. 21. 22. 23. 24. 25. 26, MATHEMATICS In how many ways can a true or false test containing n questions be answered ? There are 10 M.C.Q. questions each containing 4 options. In how many ways can the test be answered ? A coin is tossed four times and the result head (H) or tail (T) is noted. How many results are possible ? A number lock on a suitcase has four wheels. To open the suitcase a code is required which contains an English alphabet on each of first two wheels and any digit from 0 to 9 on last two wheels, How many such codes are possible if (i) repetition is allowed (ii) repetition is not allowed ? In how many ways can 6 letters be posted with 3 courier agencies available ? m men and n women (m > n) are seated in a row so that no two women occupy adjacent positions. In how many ways is it possible ? In how many ways can n children be arranged in a queue so that (i) Seta and Geeta always occupy adjacent positions ? (ii) Seeta and Geeta never occupy adjacent positions ? Find the number of four digit numbers divisible by 4 obtained using 1, 2, 3, 4, 5, 6 without repetition. Six girls are to be arranged in a sequence to offer a bouquet to six guests on dias, General Secretary Rani will be first to offer the bouquet to the guest of honour. Fifth position is reserved for Ria, Aishwarya and Isha will be consecutive in any order. Remaining girls Sneha and Smruti will occupy other two places in any order. In how many ways can this arrangement be made ? Find the number of ways in which four boys and four girls can be arranged so that (i) no two girls are adjacent (ii) all the boys are together and all the girls are together. Six girls and six boys stand in a queue alternating so that the queue starts with a girl. In how many ways is this possible ? In how many ways can alphabets of the word MONDAY be arranged taking (i) two at a time (ii) four at a time without repetition. How many permutations of all the letters of the word ZERO are there ? (No repetition) In dictionary order what is the position of the word ZERO ? How many four digit numbers divisible by 5 can be formed using 0, 1, 2, 3, 4, 5 only once ? (No repetition) How many 4 digit numbers can be formed using digits of 2745 only once ? How many are divisible 3 ? How many are divisible by 9 ? How many words having four alphabets can be formed using alphabets from the word VOWEL in which vowels occupy the place of vowels ? *PERMUTATIONS AND COMBINATIONS 185 Permutations when Some of the Objects are Identical Let us try to find permutations of the word TREE. Here E occurs twice. Temporarily call the occurrences of E as Ey, Ey. Permutations with same E Permutations with E,, Ey TREE, TREE —=_ TREE, RTEE, RTEE =. RTE,E, TE,RE, TERE —_ TE,RE, RE, TE, RETE —— RE,TE, TEER TEER ——, TE,E,R RE,E,T REET ST RE,E,T E,R ERTE —=__ ue E,RTE, E, TRE, ETRE —=__. E,TRE, E,RE,T ERET se. E,RE,T E,TE,R ETER —S—— E)TE,R E,E,TR EETR = me E,E\TR EERT —=_ Figure 7.4186 MATHEMATICS Hence, if we consider E,, E, different, as before there are 4P, = 4! permutations. But E, and E> are same and this gives us 12 = 24 = 24 permutations. Let us consider the problem more closely taking another illustration. How many four digit numbers can be formed using digits of 1112 without repetition ? Here 1 occurs thrice, Call these occurrences as 1 Ijy 1.- Occurrence with 1 same Occurrence with 1 different Iglgl,2 Tglely2 acd Iplgl,2 12 Iglelg2 Tglgly2 Figure 7.5 Aglglg2 Similarly 1121, 1211, 2111 all give six occurrences with 1,1 ;1,. Hence we get ,P, = 24 permutations with 1's different but four permutations only 1112, 1121, 1211, 2111 with I's same. In fact each of them gives 3! = 6 arrangements considering 1, 1), 1,. Hence we get 24 = 4 X 6 arrangements. In fact number of arrangements is 4= 24 = 4". Thus we have following theorem. Theorem 3 : If p, objects are alike, p, objects are alike different from earlier ones, P, objects are alike different from earlier ones and n = p, + py tot py then the number of arrangements of n things is Proof : Consider objects as ay, dys dpy5 Dy Bays Bp, ine Mys Mayor Mpy. All m objects are now different and they can be arranged in n! ways. But mutually alike objects can be arranged in p,!, py!, .... Py! ways considering them different. .. (Total number of distinct arrangements) X p,! X py! X... X py! = nl a nt Total number of distinct arrangements = rp. Thus in the above examples answers are 4PERMUTATIONS AND COMBINATIONS 187 Example 19: In how many ways can the letters of the word PERMUTATIONS be permuted ? Also find, () How many start with P and end in S ? ii) In how many of them vowels are together ? Solution : There are 12 letters containing 2 T's. Hence the number of permutations is a (i) If they start with P and end in S, remaining 10 letters contain 2 T's. J+ Required number is 49 = 1814400 (ii) There are five vowels A, E, I, O, U (all !). Consider them as one group. Hence, we have 8 words (7 + 1 group) with 2 T's. 5 vowels can be arranged in 5! ways. The required number of permutations is $ x 5! = 2419200 Example 20 : How many permutations can be made using letters of the word MATHEMATICS ? In how many of them vowels occur together ? Solution ; There are 11 letters containing 2 M's, 2 T's, 2 A's. 1 2. Number of arrangements is 37ytg7 = 4989600 A, E, L are vowels occurring. (A twice) Consonants remaining are M, T, C, S, H (M twice, T twice) Considering seven consonants and group AEAI as one leer the number of 8! permutations is Gfa7 and vowels A, E, A, I can be arranged in 3} ways. c+ The total number of arrangements = 3p4q x 4 = 10080 x 12 = 120960 Example 21 : In how many ways can seven digit numbers greater than 10,00,000 be formed using digits 1, 2, 0, 2, 4, 2,4? Solution : There are seven digits, three 2's and two 4's. First digit has to be 1, 2 or 4 according to condition. 1 The numbers beginning with 2 are Prt (One of the 2's is fixed) The number is 222 = 180 The numbers beginning with 4 are & = 20 = 120 The numbers beginning with 1 are P57 = 60188 MATHEMATICS The total number of seven digit numbers is 360 and obviously each of these seven digit numbers is greater than 100000. 1 [or consider seven digit numbers zfay = 542 = 420 1 The numbers with 0 leading are 3f57 = 22 = 60 Required number is 420 — 60 = 360] Example 22 : Find the number of ‘words’ that can be formed using all the letters of the word ALLAHABAD. (In how many of them vowels are in even positions ? Gi _In how many of them 2 L's do not occur together ? Solution ere are 9 letters and 4 A's and 2 L's in the word. f The number of permutations is Gry = 7560 (@__ Fourvowels, all A, can occur in even positions 2, 4, 6, 8 in only one way. Remaining 5 letters with 2L's can be permuted in 5} = 60 ways Hence the total number of permutations is 60. (i) Suppose two L's are combined to form a group. Now we have 8 letters with 4 A's, The number of arrangements in which both L occur together = $} = 1680 The number of arrangements in which L's do not occur together = total number of arrangements — the number of arrangements in which L's occur together = 7560 — 1680 = 5880 Example 23 : If all the letters of the word AGAIN are permuted, what is the fiftieth word in the dictionary order ? Solution : A dictionary starts with A. Words which begin with A, A are 4! = 24 in number. (G, A, I, N used). Next numbers beginning with G are 4 = 12 in number (two A's) Similarly, numbers beginning with | are 4+ = 12 in number. After these 48 words, words will begin with NAA and have GI and IG to follow. Hence 50th word is NAAIG. "= Note] What is the last word ? Writ ithout calculating { EXERCISE 7.3 1. In arrangements of all letters of the word BOOK, what is the rank of the word BOOK ?10. 11, 12. 13. 14, PERMUTATIONS AND COMBINATIONS 189 Arranging all letters of AGAIN in the dictionary order, what is the last word ? What is its rank ? There are 7 mercury lamps in a hall. Each one of them can be switched on or off independently. In how many ways will the hall be lit ? Determine the number of positive integers less than 10000 with all digits distinct. Find the sum of all the 4 digit numbers formed using digits of 2468 only once. How many permutations of all letters of the word TRIANGLE contain T and E in the end positions in any order ? How many arrangements of all the letters of word ARROW do not contain two R's together ? Find the number of permutations of letters of the word EXERCISES in which vowels are together. How many numbers between 10,000 and 20,000 can be made using all digits of 12234 ? How many of them are less than 11,000 ? Read the given sentence : 'LOOK AND GO’. How many such sentences with 3 words on the same pattern and using the same letters (first 4 letter word, 3 letter word, 2 letter word) can be formed ? Meaning not attached. How many permutations of all the letters of the word REKHA begin with R ? What is the rank of the word REKHA in dictionary order arrangement ? In how many ways can the product 2? 33 54 be written in a product form like 2+2+3+3+5+5+5+3+5 2 How many permutations of all the letters of the word INDEPENDENCE are there ? m is the number of arrangements of x things taking all at a time. n is the number of arrangements of x — 2 things taking 4 at a time. p is the number of arrangements of x — 6 things taking all at a time and if m = 30np, then find x. * Circular Permutation : Let 4 people a, b, c, d be arranged around a round dining table. In how many ways is this possible ? Cs Cs Cs ‘Cs ‘C): ‘O): c c b b d da expect 4! = 24 as answer. But 24 Figure 7.6 abed, adcb, adbe, acbd, acdb, abde are six possible arrangements. We would is the number of arrangements, as abed, beda, cdab, dabc have relatively in the same position on a circle.190 MATHEMATICS Definition : The number of ways of arranging 7 different objects on a circle is called the number of circular permutation of » objects. Theorem 4 : The number of circular permutations of n different things is (1 — 1)! Proof : Let the objects be called a, a), ay... a, In a linear order their permutations amount to ,P,, = n! But on a circle aj, dys, Gps Gy, Aguey App AY) Ay Agony Ay Qyy Ay5 Gy, Gy, @y.... dy _ , (min number) give n identical permutations on a circle. Hence the 1 n(n-1)! ee EOD number of circular permutations is Example 24 : In how many ways can seven members of a managing committee take their positions on a round table ? If the chairman sits on a particular reserved chair, how many arrangements are possible ? Solution : In circular permutation, 7 persons can be seated in (7 — 1)! = 6! = 720 ways. According to the condition given six persons can be seated in 6! Chairman has a fixed position. Number of arrangements with chairman in a fixed chair is 720. 7.3. Combination How many subsets with two elements from A = {a, 6, c, d} are there ? 6, namely {a, 5}, {a, ch, {a, d}, {8 ch. {0 d} and {c,d}. Here {a, b} = {6, a} and order of elements in a set is not important. We say that number of selections of 2 elements from set A with 4 elements is denoted by (3) or Cy or 4C, or C(4, 2) is 6. How many ordered pairs will be there with distinct elements ? (a, 5), (8, a), @, 0), (4 4), 6 a), (d, a), (8, 0, (6B), & D, Gb) A), G0) ie. 12 in all. Each subset of two elements will give 2! = 2 ordered pairs and hence there will (3) x 21 = 12 ordered pairs. But this is the same as arranging 4 elements of set A taking 2 at a time ie. 4Py 720 ways. (linear) Py = (3) x21 Similarly from digits 2, 4, 6, 8, we can select three digits in (3) = 4 ways. Now, how many numbers of three digits can be formed using 2, 4, 6, 8 ? Each triplet 2, 4, 6 will give 6 numbers as follows : 246 264 462 426 642 Figure 7.7 624PERMUTATIONS AND COMBINATIONS 191 Thus there will be (3) x 6 = 4 X 6 = 24 three digit numbers that can be formed using 2, 4, 6, 8. But this is also the number of arrangements of 4 digits in 3 places. 4) Ps (3) x6 or (4) = (6 = 3!) Definition : The number of ways of selecting r things out of m different things is called r combination number of n things and is denoted by (”) or aC, or "C, or C(n, 7). Theorem 5: (7) = 25 O Fanny (2n~r)! Dy ©? Gry? oo sotwion: (2%) > © In-r>rt er (no) = (ns) Example 26 : Solve for m : (3) = ({3). Then find (3). Solution : We know (”) = (,7,) Here let r= 5,2 — r= 13 n-5=13 n= 18 18) _ 18 (2) = (2) = #5# = 153 Example 27 : Solve : (2) = (3) and find (3). Solution : 2n(2n-1)(2n—2) _ 11n(n—1)(n—2) { nm) _ nin -(n-2)..a—=r +0 3t ~ 3t r) wl 4Qn — 1) = 11 — 2) 8-4 = 1In— 22 3n=18 n=6 6) -(@) Example 28 : If (,” 1) = 36, (7) = 84, (,%,] = 126, find m and r. ) Also, Solution : We have (,” 1) = eto = 36 @ (7) = agtog = 84 «i (21) = Gy (aii) Dividing (ii) by (i) and (iii) by (ii), at aI re Den r+ _ w vy od Goya ar = ” © fey eigeg EDM =r + D-H! _ a4 WY) gives “Ten nt 36PERMUTATIONS AND COMBINATIONS 195 n=r+1 =1 r 3 3n—3r+3=7r 10r = 3n =3 (wi) (W) reduces to [7 = 4 or 2n — 2r = 3r +3 5r—2n=—3 (vii) Solving (vi) and (vii) we get n= 9, r Example 29 : Solve (1) (8) = 28 (2) (1?) = (,125) Solution : (8) = 28 8X7X6X5 _ 79 r= 4 gives maximum value (§) = 2X2%' * : ) = 1 #28 = 8H 8) = ga 28 8 8 8 7, ( Since there are at most two solutions of (8) = 28, r = 2 or 6 @) ('?) rer+2 Here n= 12,r-+2=n—r= 12-7 2r=10 5 ra) 3) Example 30 : Solve (3°) + (3) = 12 Verification : (') = <2. 2n(2n —1(2n — 2) 2 Solution : 7S x gy = 2 + 2Qn=1)-2 2n—196 MATHEMATICS - (n+l n-l Example 31 : Find n and x ("11) : (7) :("o1) = 11:6:3. re (n+l) (nw n-1) Soluti De rij 7$ @+yt _ rin—nt _ ay ang nt rn)! _ Grp at 6 AM FH my + poe = and 2=2 6n + 6 = Ir + 11 and n = 2r 12r +6 = lr +11 or Sand n= 2r= 10 Example 32 : Prove that the product of consecutive integers is divisible by n!. Solution : Let the » consecutive intergers be r+ 1, r+ 2, 7+ Product p = (r + I)(r + 2)..(r +) _fasn! 4 n= (" ; "nt is divisible by n!. n 2n) — 2M [1-3 +5+ 7.020 — 1] ~ nt Example 33 : Prove ( Solution : (27) (Qn) _ 0:3-+5+7.. Qn DI[2- 4-6 mint _ 1:3+5+7... Qn —1)]2" [1-2+3+ ~ nint = 27 [1-3+5-7..Qn-1)] ml Example 34 : If ,P, = ,P,, , and (7) =(,")), find », v. nt G-)kn—rsiyt @- n= @—r= I and Gy = Go Solution : oom nt T and Fim —rytPERMUTATIONS AND COMBINATIONS — 197 2 (nn r-Wl=(@—r= 1)! and r=n—r41 / nor=landr=n—-rt1 2 r=(Q@—n+1=14+1=2andn=rt+1=3 Example 35 : Prove (”) + 2(-%4) + (,%9) = 7?) Solution : LHS.= (7) +(,"1) +(,"1) + (-29) “ap = ("f?) = = RHS. Example 36 : If ("2'), ("5 5, ("5") are in AP, find n. Solution : ("3 4 N+ ("3") =2("5 ‘) (in AP) ("3') +("5") + ("s') +("5') =4("5') (3) + (@) =4("5") 33) 2403) (n+ Dn (n—1n-2)(n—3(n—4) _ 4n—1I)(n— 2) — 3K — 40-5), 720 120 +n = 24(n — 5) “2 —23n + 120=0 . n=15 or & 1. Find) (8) @ (3) @ (2) 2. (8) = (6), 3. Solve (1) (,193) = (r!3) _@ (r!8s) = (,'s) 4. If ,P, = 1680 and ("*) = 70 find n and r find n. se (") 4) 2 (P) ("2") = 6:95 13, find m and »198 MATHEMATICS 6. Prove (7) x (5) = (2) x (7-2). 7. 1 (2) + (8) + (9) + (2) + (9) = (17), sind x 8. Prove n (21) =(—r41)(,"1) * Practical Problems on Permutations and Combinations Example 37 : 7 points are given in a plane, no three of which are collinear. How many line segments can be drawn using them ? Solution : Any two points will determine a segment and AB = BA. So order of 6 selection is immaterial. Hence (3) = 2:6 = 21 tine segments can be drawn using them. Example 38 : 8 points of which 3 are collinear lie in a plane. How many triangles can be formed by them ? How many lines will pass through any two distinct points from them ? How many line segments are formed ? z Solution ; 8 non-collinear points can determine ABC 1 (8) triangles like ADE. We are considering (3) = 1 . . triangle formed by A, B and C. But A,B,C are pb EF g FF collinear, Figure 7.8 Number of triangles is (§) — ‘Two points determine a line. Hence (8) = 28 lines should be formed. But AB, BC and CA are not three lines but it is one line only as A, B, C are collinear. Hence from 28 lines considered, we should remove three lines AB, B@ and CA counted as three lines and add one line / containing A, B, C. 28 — 3 + 1 (line J) = 26 lines are formed. All (8) = £2 = 28 line segments are different. AB # BC etc. 28 line segments are formed. Example 39 ; In how many ways can a committee consisting of 3 boys and 2 girls to celebrate Swarnim Gujarat be selected from 5 boys and 4 girls ? In how many of them a certain boy Kiran will always be selected 2 In how many of them a certain girl Reshma will be selected ?PERMUTATIONS AND COMBINATIONS — 199 Solution : Selection of 3 boys out of 5 boys and 2 gitls out of 4, according to the fundamental principle of counting, will take place in (3) x (3) ways. 5) (4 5:4+3 : Now, (3) (3) = 37° x Fe = 10x 6=60 c+ We can select the committee in 60 ways. @ To select Kiran we have to select 2 boys out of 4 boys and 2 girls also out of 4 girls. Number of selections = (3) x (3) = 43 x 432 =6 x6=36 «i 36 committees will have Kiran as a member. To select Reshma, we have to select 3 boys out of 5 boys and I girl out of 3 girls. sons - (5) x (3 Number of selections = (3) x (7) =10x3=30 Gi) 30 committees will have Reshma as a member. Example 40 : 3 cards are chosen from a pack of 52 cards. (1) In how many ways can this be done ? (2) In how many ways can you select three cards so that all of them are face cards ? (3) In how many of the selections, all cards are of the same colour ? (4) In how many of them all cards are of the same suit ? Solution : (1) We can select three cards in (37) = 2-51-52 = 52+51+50 a = 22100 Three cards can be selected in 22100 ways. 12) (2) There are 12 face cards. Hence we can have (1%) selections. (17) = PH? = 290 Three face cards can be selected in 220 ways. (3) There are 26 cards of red colour (heart and diamond) and 26 cards of black colour (club and spade). 2. (78) + (8) is number of ways to select three cards of black or red colour. (78) = 20:35-%4 — 2600 There 5200 ways to select cards of the same colour.200 MATHEMATICS (4) There are four suits. One suit can be chosen from them in (f) ways and 3 cards from the selected suit in (4?) ways. . Numbers of selections = (3) x (t) x4= 1144 = 13-12-11 a Example 41 ; A reception committee consisting of 6 students for the annual function of a school is to be formed from 8 boys and 5 girls. In how many ways can we do it if the committee is to contain (1) exactly 4 girls (2) at most 2 girls (3) at least 3 girls ? Solution : (1) Selection of 6 students will involve 4 girls out of 5 girls and 2 boys out of 8 boys. )x( £. Numbers of selections = (3 5 i) x ( ( 8 2 8 2, = 140 2 (2) At most 2 girls means 2 or less number of girls. Following alternatives are possible. Boys Girls 4 2 5 1 6 0 .. The number of selections = (3) x (3) + (5) x (3) + (8) x (3) = 8:76:35 y sa + 7:6 8:7 xs+a xl 8) _ (8 (@)- (§) ana (8) = (3)] = 700 + 280 + 28 = 1008 @) At least 3 girls means 3 or more girls : Boys Girls 3 2 1 The number of selections = = 560 + 140 + 8 = 708 Example 42 : Three couples go to see a movie. In how many ways can they occupy a seat if spouses occupy adjacent seats ? In how many ways can ladies be seated together ?PERMUTATIONS AND COMBINATIONS 201 Solution : Couples C,, Cy, C3 can be arranged 3! = 6 GG ways. In an arrangement of a couple husband and wife can be arranged in 2! X 2! X 2! = 8 ways. OoOd There are 48 ways to make the required arrangement. @ Arrange three men and one group of ladies together ive. four units in 4P, = 4! = 24 ways. In each arrangement ladies can be permuted in 3! = 6 ways. Total number of arrangements is 24 X 6 = 144 Gi EXERCISE 7.5 1. How many triangles can be formed from nine points in plane, four of which are collinear ? How many lines can be formed using them ? 2. In how many ways can a committee consisting of 4 male and 4 female members be formed from 8 male and 6 female members of a city club ? How many committees of eight members can be formed with (I) at least 3 female members (2) exactly 2 female members (3) at most 2 female members. 3. Four cards are selected from a pack of 52 cards. (1) In how many ways can they be selected so that they are all from different suits ? (2) In how many ways can they be selected so that they are face cards ? (3) In how many ways can they be selected so that they are all of the same colour ? 4, There are two white, three red and four green marbles. Three marbles are drawn. In how many ways can this be done so that at least one red marble is selected ? 5. 15 students are divided into three groups with equal number. In how many ways can this be done ? 6. In an award function 12 celebrities occupy place around two round tables with accommodation for 8 and 4 persons. In how many ways can this take place ? 7. In how many ways can n persons be arranged in a queue so that certain 2 persons are not adjacent to each other ? 8. What is the number of diagonals of a convex polygon with n sides ? 9. A convex polygon has 44 diagonals. How many sides does it have ? 10. In a convex polygon of n sides, how many triangles are formed joining vertices ? How many of them will have one side in common with the polygon ? How many of them will have two sides in common with the polygon ? How many of them will have no side in common with the polygon ? + Miscellaneous Problems Example 43 : Assuming that the highest power of a prime p occuring in n! is n [2 + pit find the highest power of 5 occuring in 25! Solution : The highest power of 5 in 25! is [2] + [38] =5+1=202. MATHEMATICS Example 44 : How many zeroes will occur at the end of 52! ? Solution : The highest power of 5 in 52! is [52] + [32] = 10 +2 = 12 ‘The highest power of 2 in 52! = [52] + [52] + [2] + [32] + [3] =26+13+6+3+ 49 The highest power of 10 in 52! = 12 52! has 12 zeroes at the end. Example 45 ; If a set A has 3 elements and B has 5 elements how many functions f:A— B are there ? How many of them will have range as B ? Solution : Let A = {x}, X23}, B= {yy Yo ¥3s Yar Ysh For a function f : A —> B ordered pairs (x;, y;) are to be formed with no x; from A repeating in a pair and all x, have to be used once. Thus f= {Cy ¥,), (Yq) Gey ¥)} is a typical function f: A — B. Thus selection of y/s can be done in 5 x 5 x 5 = 125 ways. Hence number of functions f : A —> B is 125. Each function will have range consisting of at most three elements. Hence no function will have range as B. Example 46 : How many 5 card combinations of 52 cards are there containing at least one ace ? Solution ; We can select, Ace (4) Other cards (48) 1 4 2 3 3 2 4 1 Number of selections is (4) x (4) = 8,86,656 Example 47 : If m vertical bars meet m horizontal bars, how many rectangles will be formed ? Solution : A rectangle is formed when two horizontal and two vertical lines are selected. + Number of rectangles formed = (73) x (3) = m(m=1) 4, m(n=1) _ mn(m—1)(n~1) 2 2 4PERMUTATIONS AND COMBINATIONS 203 Example 48 ; In a plane, we have 25 lines out of which 15 are concurrent in A and 5 are concurrent in B. No two lines are parallel and out of other lines, no three of them are concurrent. Find the number of the points of intersection. Solution : 25 lines can intersect in (3) points. But instead of (1) points of intersection, we get only one point A and instead of (3) points of intersection we get only one point B. Number of points of intersection = (3) — (17) — (3) +2 (A and B) = 300 — 105 — 10 + 2 = 187 Example 49 : A student taking an examination has to answer 20 questions from sections A and B containing 12 questions each. It is necessary to answer at least 8 questions from each section. In how many ways can he take the examination ? Solution : Several options are available. Questions from section A Questions from section B 8 12 9 ul 10 10 0 9 12 8 (Out of 12) (Out of 12) s+ Number of ways to take examination is (°8)(3) + (C0) + (18)088) + (FS) + (8) = 2(12) + 2(12)(22) + (2)(2) = 2:12-11+10-9 2-12-11-10 12-1 0 RA SE xis | = 990 + 5280 + 4356 = 10626 Example 50 : How many triangles can be formed by 12 points 7 of which lie on one line and 5 on another parallel line ? Solution : Obviously number of triangles is ~ (Ci) + 3)() 21x5+10X7 = 105+70 = 175204 MATHEMATICS 3. 4. 5. EXERCISE 7 A group of socially active friends has 8 boys and 5 girls as members. In how many ways can a task be assigned to a team of 5 members containing (1) at least one boy and at least one girl. (2) no boy (3) at least three girls (4). at most two boys Find the numbers of integers greater than 7000 obtained by using 2, 5, 6, 8, 9, no digit being repeated. ‘A convex polygon has 54 diagonals. Find the number of vertices. Out of 8 teachers T,, T;, T3,...Tg, five are to be selected for training. T, is the junior most and he has to go for training. Ty is retiring next year and does not require any training. In how many ways should the squad be selected ? If only one teacher goes for training every week in how many ways can their order be arranged ? The training is to last for five weeks. Find the number of selections of r things out of n distinct things such that none of particular things are selected at a time. Out of five vowels a, e, i, 0, u words with four letters are to be formed. Find number of words in which any one vowel is repeated at least three times. Ina test of multiple choice questions, there are four choices for each question and there are 5 such questions. In how many ways can a student fail to get complete correct solution ? There are two parallel lines J, and /, in plane. 1, contains m different points Ay, Apsn. An: 1, contains n different points By, By,..., B,. How many triangles are possible with these vertices ? Select proper option (a), (b), (c) or (d) from given options and write in the box given on the right so that the statement becomes correct : (i) i (7) = (, 29), then r=. Oo @n (b)n-1 2) If (8) = (75), then n =... (a) 20 (b) 10 (©) Is (d) not possible @) . O (@) r! W@-y! O@-Nr @Mer-! Oo @r! O@-AN O@-Nrt @l@- I}PERMUTATIONS AND COMBINATIONS 205 (5) The number of possible outcomes when a coin is tossed 8 times is ...... [] (a) 32 (b) 64 (© 128 (@) 256 (© The sum of digits of unit place of all four digit numbers formed using 3, 4, 5, 6 without repetition is ...... (@) 24 (b) 108 © 72 (d) 96 (7) A four digit number is formed using 0, 1, 2, 3, 4. It is divisible by 20. The number of such numbers is.... (@ 12 (b) 6 (© 24 (d) 96 (8) In a get-to-gether function, everybody handshakes with everybody else. The total number of handshakes is 10S. The number of persons in the hall is .... (@ 12 (b) @15 @14 (9) The total number of 9 digit numbers with all the digits different is... [7] (@) 9! (b) 10! (©) 10! — 8! @ 960, (10) If there are eight points in a plane out of which three are collinear. The number of lines formed by them is..... (@) 28 (b) 26 (©) 56 (@) 55 (11) If there are 12 points in a plane out of which 6 each lie on two parallel lines, the number of triangles formed by them is ..... (a) 120 (b) 180 © 60 (a) 40 (12) tf (19) is maximum, 7 = on oO (a) 100 (6) 0 © 50 @51 (13) The number of rectangles formed when 10 horizontal bars intersect 8 vertical bars is (a) 1880 (b) 800 (©) 80 (d) 1260 (14) The number of ways in which seven + signs and four — signs can be arranged so that — signs do not occupy adjacent places is ...... i] (@) sPa ©) (4) © (3) (@) None of these (15) 7 persons can sit around a round dining table for dinner in .... ways. (a) 720 (b) 80 (©) 60 (@ 5040 (16) 1f (45) = (,45), then r (@) 33 (b) (©) 2 (44 (17) The number of diagonals of a decagon is ...... (@) 35 (b) 45 (©) 55 (@) 30206 MATHEMATICS (18) If @ (19) If @ (20) If @ en (? c S ) (22) If @ es (79 @ ey (7 @ (25) If @ 2) = (38), hn (5) = i (b) 9 (© 45 4 (ea) =("E)s ten e= n-r (rt On OO 8 then a = 3 (b) 9 © 12 )+ (2) + (9) + (2) + (8) = (8) w (9) © (8) 7) is maximum, r=. 35 (b) 38.5 © 39 ) an > w< = increases as r increases from 0 0 wu. « n (yn-1 oF 18) = (IB). b= mG > 10) n (8 ©o (a) 36 @n-rt1 6 @ ('3) (d) 40 @z © [4] @nti 0 Oo 0 0 QO