Permutations and Combinations

Permutations and Combinations FACTORIAL NOTATION 1. The continuous product of first n natural numbers is called factorial and it can be represented by notation |n or n! . So n! = 1.2.3......... (n–1) .n or n! = n (n–1) (n–2) ........3.2.1 = n { (n–1) (n–2) ........3.2.1.}  n! = n (n–1)! = n (n–1) (n–2 ) ! = n (n–1) (n–2) (n–3) ! n! n (n–1) ...........(n – r + 1) = (n  r )! Some useful results : 0! = 1 1! = 1 4! = 24 5! = 120 8! = 40320 9! = 362880 2! = 2 6! = 720 10! = 3628800 3! = 6 7! Fundamental Principle of Multiplication : Let there are two parts A and B of an operation and if these two parts can be performed in m and n different number of ways respectively, then that operation can be completed in m × n ways. Ex.1 A Hall has 3 gates. In how many ways can a man enter the hall through one gate and come out through a different gate? Sol. Suppose the gates are A, B and C. Now there are 3 ways (A, B or C) of entering into the hall. After entering into the hall, the man come out through a different gate in 2 ways. Hence, by the multiplication principle, total number of ways is = 5040 –n! = Meaningless FUNDAMENTAL PRINCIPLES OF COUNTING When one or more operations can be accomplished by number of ways then there are two principles to find the total number of ways to accomplish one, two, or all of the operations without counting them as follows : 3 × 2 = 6 ways. Ex.2 The number of three digit numbers can be formed without using the digits 0,2,3,4, 5 and 6 is (if repetition of digit is allowed)– (A) 54 (B) 64 (C) 44 (D) None of these 61 Sol. We have to determine the total number of three digit 2. numbers formed by using the digits 1,7,8,9. clearly the repetition of digits is allowed. Permutations and Combinations Fundamental Principle of addition : If there are two operations such that they can be done independently in m and n ways respectively, then any one of these two operations can be done by (m + n) number of ways. A three digit number has three places viz. unit’s, ten’s and hundred’s. Unit’s place can be filled by any of digit 1,7,8,9, so units place can be filled in 4 ways. Similarly each one of the ten’s and hundred’s places can be filled in 4 ways. Ex.5 Find the number of two digit numbers (having  Total number of required numbers different digits) which are divisible by 5. = 4 × 4 × 4 = 64 Ans.[B] Ex.3 The number of numbers are there between 100 and 1000 in which all the digits are distinct is – (A) 648 (C) 448 (B) 548 (D) None of these Sol. Any number of required type either ends in 5 or in 0. Number of two digit numbers (with different digits) ends in 5 is 8 and that of ending in 0 is 9. Hence, by addition principle the required number of numbers is 8 + 9 = 17. Sol. 4 number between 100 and 1000 has three digits, Ex.6 A book seller has 5 books of mathematics, 6 books so we have to form all possible 3- digit numbers of physics, and 4 books of chemistry. A student can with distinct digits. We cannot have at the hundred’s purchase any one book of either mathematics or place so the hundred’s place can be filled with any physics or chemistry by 5 + 6 + 4 = 15 number of of the digits 1,2,3, ....9. So there are 9 ways of filling ways but the same student can purchase one the hundred’s place. book of mathematics, physics and chemistry Now 9 digits are left including 0. so ten’s place can each by 5 × 6 × 4 = 120 number of ways. be filled with any of the remaining 9 digits in 9 ways. Now, the unit’s place can be filled within any of the numbering 8 digits, so there are 8 ways of filling the PERMUTATIONS unit’s place. An arrangement of some given things taking some Hence the total number of required numbers or all of them, is called a permutation of these things. = 9 × 9 × 8 = 648 Ans.[A] Ex.4 The number of three digit numbers greater than 600 can be formed by using the digits 2,3,4, 6,7 if repetition of digits is allowed(A) 50 (C) 30 (B) 20 (D) None of these For Example, three different things a, b and c are given, then different arrangements which can be made by taking two things from the three given things are ab, ac, bc, ba, ca, cb Therefore, the number of permutations will be 6. Sol. Since three digit number greaterthan 600 will have 6 Important Results or 7 at hundred’s place. So hundred’s place can be 1. The number of permutations of n different things, filled in 2 ways. Each of ten’s and one’s place can taking r at a time is denoted by nPr or P (n, r) be filled in 5 ways. Hence total no. of required n! numbers n 0rn Pr = n  r ! = 2 × 5 × 5 = 50 Ans.[A] = n (n – 1) (n – 2) . . . (n – r + 1). 62 Permutations and Combinations n Ex.8 Prove that P = n – 1Pr + r. n– 1Pr – 1 Note: r n–1 n–1 (i) The number of permutations of n different things taken Sol. R.H.S = Pr + r Pr – 1 all at a time = nPn = n! = (ii) nP = 1, nP = n and nP = nP = n!. 0 1 n n–1 (iii) Pr = n ( n–1 n Pr – 1) = n (n – 1) (n – 2)(n – 2Pr – 2) = n (n – 1) (n – 2) (n – 3 Pr – 3) = . . . = Explanation : Arrangement of n things at r places may be done as follows : = First we make arrangement for first place which may be done in n ways. After this, we make arrangement for second place which may be done in (n–1) ways. Continuing this process, we shall find the arrangements for third, fourth....rth places may be done in (n–2), (n–3) ....(n–r +1) ways respectively. = n 1 ! n n 1 ! n! n r r   nr ! n r ! n r ! = nPr = L.H.S. = Hence total number of permutations of n things taking r at a time Ex.9 The value of 8P3 is = n (n–1) (n–2) .......(n–r +1) (A) 336 (B) 56 (C) 386 (D) None of these .nP1 = n Sol. 8P3 = 8.7.6 = 336 Note : .nPr = n. n–1 Pr–1 With the help of formula .nP = (n–r+1) .nP r . nP r–1 n = nP n–1 8P 8! 3 = (8  3)! = 8.7.6.5.4.3.2.1 = 8.7.6 = 336 5.4.3.21 . Ans.[A] Ex.7 If 56Pr + 6 : 54Pr + 3 = 30800 : 1, find rP2. Sol. We have 56 54  Pr 6 Pr 3  30800 1 51  r ! 30800 56!   50  r ! 54! 1  56.55 (51 – r) = 30800  r = 41  rP2 = 41P2 = 41.40 = 1640. Ex.10 The number of numbers which can be formed with the digits 2, 3, 4, 5, 6 by taking 4 digits at a time are(A) 135 (B) 120 (C) 150 (D) None of these Sol. The required numbers 5! = 5P4 = (5  4)! = 5.4.3.2.1. = 120 Ans.[B] Ex.11 In how many ways can three persons sit on 6 chairs? (A) 150 (B) 140 (C)120 (D) 110 Sol. The Required number of ways are 6P = 6.5.4 = 120 Ans.[C] 3 63 Ex.12 How many different signals can be made by 5 flags from 8 flags of different colours? (A) 6720 (C) 4720 (B) 5720 (D) None of these Sol. The total number of signals is the number of arrangements of 8 flags by taking 5 flags at a time. Hence required number of signals 8! 8! = 8P5 = (8  5)! = 3 ! = 8  7  6  5  4  3! 3! 2. Permutations and Combinations Permutations in which all things are not different: The number of permutations of n things taken all at a time when p of them are alike and of one kind, q of them are alike and of second kind, r of them are alike and of third kind and all remaining being different is n! p ! q !r! Explanation : If all n things were different then total = 6720 Ans.[A] number of permutations will be n!, but if p things are similar, then these p things can be mutually arranged Ex.13 How many numbers lying between 100 and 1000 only in one way, Whereas in the case when they can be formed with the digits 1,2,3,4,5,6 if the were different, their mutual arrangements could be repetition of digits is not allowed? p!. Similarly when q things and r things were different, (A) 30 (B) 120 their mutual arrangements could be q! and r! (C) 50 (D) None of these respectively. Thus the total number of permutations Sol. Every number lying between 100 and 1000 is a three is obtained by dividing n! by p! . q! .r!. digits number. Therefore we have to find the number of permutations of six digits 1,2,3,4,5,6 taken three Note : Above formula is applicable only when all n things at a time. are taken at a time. Hence, the required number of numbers = 6P3 = 6  5  4  3! = 120 3! Ans.[B] Ex.15 How many 7 letter words can be formed using the letters of the word ‘ARIHANT’? Ex.14 How many four digit numbers are there with distinct digits? Sol. Here total letters is 7, in which 2A’s, but the rest are (A) 4536 (B) 4526 different. Hence the number of words formed (C) 4516 (D) None of these 7!  2520 = Sol. The total number of arrangements of ten digits 2! 10 0,1,2,3,4,5,6,7,8,9 taking 4 at a time is P4. But these arrangements also include those number which Ex.16 How many different words can be formed with have 0 at thousand’s place. Such numbers are not the letters of the word “ALLAHABAD” ? four digit numbers. When 0 is fixed at thousand’s (A) 10080 (B) 8640 place, we have to arrange remaining 9 digits by (C) 15120 (D) 7560 taking 3 at a time. The number of such arrangements is 9P3. Sol. There are in all 9 letters in the given word. Out of them there are 4 ‘A’s, 2 ‘L’s and the remaining 3 are So, the total number of numbers having 0 at 8 thousand’s place = P3. different . So the total number of permutations Hence, the total numbers four digit numbers = 10P4 – 9P3 = 5040 – 504 = 4536 9! = 7560 4 ! 2! Ans.[D] Ans.[A] 64 Ex.17 How many numbers can be formed with the digits 2,3,3,4,2,3 taken all at a time. (A) 460 (C) 260 (B) 60 (D) None of these Sol. We have to arrange these six digits, out of which 2 occurs twice, 3 occurs thrice and rest are distinct. 6! The number of such arrangement = 2!  3 ! = 60 Ans.[B] 3. Permutations in which things may be repeated: The number of permutations of n different things taken r at a time when each thing can be used once, twice, .....upto r times in any permutation is nr. In particular, in above case when n things are taken at a time then total number of permutation is nn. Ex.18 A child has four pockets and three marbles. In how many ways can the child put the marbles in his pockets? Permutations and Combinations Ex.20 In how many ways 3 prizes can be distributed among 5 students, when(a) no student receives more than a prize. (b) a student can receive any number of prizes. (c) a student does not get all prizes. (A) 60,125,120 (B) 125,60,120 (C) 125,120,60 (D) None of these Sol. (a) Since the first prize can be given to any one of the student so it can be given in 5 ways. The second prize can be given in 4 ways and the third prize can be given in 3 ways as no student can get more than one prize. Therefore, number of ways of distributing 3 prizes among 5 boys. = 5 × 4 × 3 = 60 (b) Since a student can receive any number of prizes, therefore each prize can be distributed in 5 ways. Hence the number of ways of distribution of 3 prizes among 5 students is = 5 × 5 × 5 = 53 = 125. (c) Here the number of ways so that a student can receive all prizes will be 5, therefore if a student doesn’t receive all prizes, then number of ways of distributing 3 prizes among 5 students. = 53 – 5 = 120 Ans.[A] Sol. The first marble can be put into the pocket in 4 ways, 4. so the second can also be put in the pocket in 4 ways so can the third . Thus, the number of ways in which the child can put the marbles = 4 × 4 × 4 = 64 ways. Ex.19 There are 6 pockets in the coat of a person. In how many ways can he put 4 pens in these pockets? (A) 360 (C) 4096 (B) 1296 (D) None of these Sol. First pen can be put in 6 ways. Similarly each of second, third and fourth pen can be put in 6 ways. Hence total number of ways = 6 × 6 × 6 × 6 = 1296 Ans.[B] Restricted Permutations : If in a permutation, some particular things are to be placed at some particular places or some particular things are always to be included or excluded, then it is called a restricted permutation. The following are some of the restricted permutations. (a) The number of permutations of n dissimilar things taken r at a time, when m particular things always occupy definite places = n–m P r–m (b) The number of permutations of n different things taken altogether when r particular things are to be placed at some r given places. = n–r Pn–r = (n–r) ! (c) The number of permutations of n different things taken r at a time, when m particular things are always to be excluded = n–mPr (d) The number of permutations of n different things taken r at a time when m particular things are always to be included = n–m Cr–m × r! 65 Ex.21 How many numbers lying between 1000 and 2000 can be formed with the digits 1, 2, 3, 4, 5 which are divisible by 5. (A) 3 (B) 6 (C) 12 (D) 18 Permutations and Combinations (b) If given digits be n (including 0) then total number of m- digit numbers formed with them = nPm - n–1 Pm–1. because n–1Pm–1 is the number of such numbers which contain 0 at extreme left. Sol. The required numbers will contain 4 digits in which Ex.24 How many six digit numbers can be formed by first and last digits will be 1 and 5 respectively. The using the digits 0,1,2,3,4,5 and 6? remaining two places are to be filled up from the (A) 5040 (B) 4320 remaining three digits and it can be done in 3P2 = 6 (C) 720 (4 ) 5760 ways. Hence the required number = 1 × 6 = 6 Ans.[B] Sol. First Method : The total numbers by taking any six digits from the given seven digits = 7P6 = 5040 Ex.22 How many different words beginning with The six digits numbers containing zero at first place S and ending with K can be made by using the letters = 6P5 = 720 of the word ‘SIKAR’ ?  Required Numbers = 5040 - 720 = 4320 (A) 6 (B) 12 Second Method : Here first we make six squares (C) 48 (D) 60 in a row in the following way Sol. After putting S and K at their respective places the 6 6 5 4 3 2 remaining 3 letters can be arranged in 3! ways. Obviously first square on extreme left can be filled Therefore required number of words = 1 × 3! = 6 in 6 ways, since any non zero six digits 1,2,3,4,5,6 Ans.[A] can occupy this square . Ex.23 How many different 3 letter words can be formed The remaining squares can be filled in with the letters of the word ‘JAIPUR’ when A and I 6 × 5 × 4 × 3 × 2 = 720 no. of ways are always to be excluded ?  Required Numbers = 6 × 720 = 4320 (A) 12 (B) 24 Ans.[B] (C) 48 (D) 60 Sol. After leaving A and I, we are remained with 4 different letters which are to be used for forming 3- letter words. Hence the required number = 4P3 = 4.3.2 = 24. Ans.[B] 5. Permutation of numbers when given digits include zero : If the given digits include 0, then two or more digit numbers formed with these digits cannot have 0 on the extreme left. In such cases we find the number of permutations in the following two ways. (a) (The number of digits which may be used at the extreme left) x (The number of ways in which the remaining places may be filled up) COMBINATIONS The different groups or selections of a given number of things by taking some or all at a time without paying any regard to their order, are called their combinations. For example, if three things a, b and c are given then ab, bc and ac are three different groups, because ab and ba will give only one group, similarly bc and cb will give one group and ac and ca will give another group. Thus taking two things out of three different things a, b and c, the following three groups can be formed : ab, bc, ca 66 Permutations and Combinations The number of combinations of n different things taken r at a time is denoted by nC or C (n, r ) r nC r So nCr = n! = r !(n  r )! n(n  1)(n  2).....(n  r  1) r! Particular cases :nCr = nC n pr r! =1 nC = 1 0 Some Important Results : * nCr = nCn–r * nCx = nCy  x + y = n * nCr + nCr–1 = n+1Cr * * * * n n n–1 . Cr–1 r nC = 1 (n  r  1) nC r r–1 r nC = nC 1 n–1 = n Greatest value of nCr = nCn/2, when n is even = nC(n–1)/2 or nC(n+1)/2 , when n is odd nC r = Ex.25 If nCr – 1 = 36, nCr = 84 and nCr + 1 = 126, then find r. n Cr 84  Sol. n C r 1 36  n  r 1 7  r 3 n  C n  r 1    n r   r Cr 1    3n – 3r + 3 = 7r  10r – 3n = 3 . . . (i) n and C r 1 n Cr  n  r  1  1 126  r 1 84 n    Cr n  r 1    n r Cr 1   nr 3  r 1 2 Difference between Permutation and Combination : (a) In combinations the order of things has no role to  2n – 2r = 3r + 3 play, while in permutations the order of things plays  5r – 2n = – 3 an important role.  10 r – 4n = – 6 (b) In combinations the different groups are formed by Substracting (ii) from (i) n=9 taking some or all given things, while in case of 10r – 27 = 3  10 r = 30 permutations all possible arrangements of things are  r=3 made in each group. Thus the number of permutations is always greater than the number of Ex.26 In how many ways can a committee of 6 persons combinations. be made out of 10 persons ? (A) 210 (B) 300 Note: (C) 151200 (D) None of these In general, we use the methods of finding Sol. We have to select 6 persons from 10 given persons. combinations in case of forming groups, teams or This can be done in 10C6 ways therefore number of committees, while the methods of finding committees. permutations are used in forming numbers with the 10! 10. 9. 8. 7 = 10C6 = 10C4 = 4! 6 ! = 4. 3.2.1 = 210 help of digits, words with the help of letters, Ans.[A] distribution of prizes etc. 67 Permutations and Combinations Ex.27 In how many ways a committee of 5 members can be selected from 6 men and 5 women, consisting Ex.29 In how many ways 11 players can be selected out of 3 men and 2 women? of 15 players when (A) 200 (B) 100 (a) one particular player is always to be selected. (C) 300 (D) None of these (b) one particular player is never to be selected. Sol. Three men out of 6 men can be selected in 6C3 (A) 364,1365 (B) 1001,364 ways. Two women out of 5 women can be selected (C) 3003, 364 (D) 3003,1001 in 5C2 ways. Therefore total number of ways = Sol. (a) In this case 10 players are to be selected out of 6C × 5C = 200 ways. Ans.[A] 3 2 14 players and it can be done in Ex.28 Out of 5 men and 2 women, a committee of 3 is to be formed. In how many ways can it be formed if atleast one woman is to be included? (A) 20 (C) 25 14C 10 = 14C 4= 14.13.12.11 = 1001 ways 1. 2. 3. 4 (b) In this case 11 players are to be selected out of 14 players and it can be done in (B) 30 (D) None of these 14C Sol. The committee can be formed in the following ways: 11 = 14C 3= 14.13.12 = 364 ways 1. 2. 3 Ans.[B] (i) By selecting 2 men and 1 woman (ii) By selecting 1 man and 2 women 2. Total number of combinations in different cases: 2 men out of 5 men and 1 woman out of 2 women can be chosen in 5C2 × 2C1 ways. (a) The number of combinations of n different things taking some or all (or atleast one) at a time = nC1+ nC2 + .....+ nCn = 2n – 1 (b) The number of ways to select some or all out of (p + q + r) things where p are alike of first kind, q Total number of ways of forming the committee are alike of second kind and r are alike of third kind 5 2 5 2 is = (p +1) (q +1) (r +1) – 1 = C2 × C1 + C1 × C2 = 20 + 5 = 25 Ans.[C] Explanation : Since p things are similar , therefore these p things may or may not be selected in (p +1) ways. Similarly q things of second type may 1. Restricted Combinations : or may not be selected in (q +1) ways and r things The number of combinations of n different things of third type may or may not be selected in (r +1) taking r at a time ways. Thus the number of ways in which the given objects may or may not be chosen (a) When p particular things are always to be included = (p + 1) (q +1) (r + 1) = n–pCr–p Since this includes one way in which nothing is (b) When p particular things are always to be excluded chosen. Hence the number of ways of selecting the = n–pCr things is = (p + 1) (q + 1) (r + 1) – 1 (c) When p particular things are always included and q (c) The number of ways to select some or all out of particular things are always excluded (p + q + t) things where p are alike of first kind, q = n–p–qCr–p are alike of second kind and remaining t are different is = (p +1) (q +1) 2t – 1 And 1 man out of 5 men and 2 women out of 2 women can be chosen in 5C1 × 2C2 ways. 68 Ex.30 In how many ways can I purchase one or more shirts if 6 different shirts are available ? (A) 64 (C) 63 (B) 62 (D) 126 Permutations and Combinations we see that arrangements in all figures are same.  The number of circular permutations of n n different things taken all at a time is Pn  (n – 1) !, n if clockwise and anticlockwise orders are taken as different. Sol. Total number of ways = 6C1 + 6C2+ 6C3+ 6C4 + 6C5 + 6C6 Ex.32 In how many different ways can five boys and five girls form a circle such that the boys and girls are 1= 63 Ans. [C] alternate? Ex.31 A bag contains 3 one rupee coins, 4 fifty paise Sol. After fixing up one boy on the table the remaining coins and 5 ten paise coins. How many selections of can be arranged money can be formed by taking atleast one coin from in 4! ways. There will be 5 places, one place each between two the bag ? boys which can be filled by 5 girls in 5! ways. (A) 120 (B) 60 = 26– (C) 119 (D) 59 Sol. Here are 3 things of first kind, 4 things of second kind and 5 things of third kind so the total number of selections = (3+1) (4+1) (5+1) –1 = 119 Ans.[C] CIRCULAR PERMUTATIONS (i) Arrangements round a circular table : Consider five persons A, B, C, D and E to be seated on the circumference of a circular table in order (which has no head). Now, shifting A, B, C, D and E one position in anticlockwise direction we will get arrangements as follows: Hence by the principle of multiplication, the required number of ways = 4! × 5! = 2880. (ii) Arrangements of beads or flowers (all different) around a circular necklace or garland: Consider five beads A, B, C, D and E in a necklace or five flowers A, B, C and D, E in a garland etc. If the necklace or garland on the left is turned over we obtain the arrangement on the right, i.e., anticlockwise and clockwise order of arrangements are not different. Thus the number of circular permutations of ‘n’ 1 (n – 1)!, if 2 clockwise and anticlockwise orders are taken as not different. different things taken all at a time is 69 Permutations and Combinations 18 Ex.33 Find the number of ways in which 12 different beads can be arranged to form a necklace. Sol. 12 different beads can be arranged among themselves in a circular order in (12 – 1)! = 11! ways. Now in the case of necklace there is no distinction between clockwise and anticlockwise arrangements. So the required number of 1 arrangements = 11! . 2 = 18! P12 = 6!  24 2  12 = 18  17  16  15  14  13! = 6  5  4  3  2  1  24 119  13! . 2 Note : (i) In a circular permutation the relative position among the things is important whereas the place of a thing has no significance. Thus in a circular permutation first thing can be placed anywhere. This operation (iii) number of circular permutations of ‘n’ different things can be done only in one way, then relative order taken ‘r’ at a time. begins. Thus the ways for performing remaining parts Case I: of the operation can be calculated just like the If clockwise and anticlockwise orders are taken as calculation of linear permutation for example to place different, then the required number of circular 8 different things round a circle, first we place any permutation = (nPr) / r one thing at any one place, there will be only one way to perform this operation. Then remaining 7 things will Ex.34 In how many ways can 13 persons out of 24 persons be seated around a table. occupy remaining 7 places, for which the numbers of ways = 7! . Thus required number of circular Sol. In case of circular table the clockwise and permutations is 7! anticlockwise orders are different, thus the required (ii) In a garland of flowers or a necklace of beads, it is 24 difficult to distinguish clockwise and P13 24! number of circular permutations = = . anticlockwise orders of things, so a circular 13 13  11! permutation under both these orders is considered to be the same. Case II: If clockwise and anticlockwise orders are taken as same, then the required number of circular permutations = (nPr) / (2r) Ex.36 The number of ways in which 7 persons be seated at 5 places round a table areEx.35 How many necklace of 12 beads each can be made from 18 beads of various colours? (A) 252 (C) 2520 (B) 504 (D) None of these Sol. In the case of necklace there is no distinction Sol. The required number 7 between the clockwise and anticlockwise 7.6.5.4.3 P5 = = = 504 arrangements, thus the required number of circular 5 5 permutations Ans.[B] 70 Ex.37 In how many ways can 5 beads out 7 different beads be strung into a ring ? (A) 504 (C) 252 (B) 2520 (D) None of these Sol. In this case a clockwise and corresponding anti clockwise order will give the same circular permutation. So the required number 7 = 7.6.5.4.3 P5 = = 252 2.5 2.5 Ans.[C] Permutations and Combinations (b) The number of ways in which (p + q + r) things can be divided into three groups containing p, q and r things is bp  q  r g ! p ! q! r ! Particular case : when p = q = r, then total number of combinations are 3p! 2 Restricted Circular Permutations : When there is a restriction in a Circular permutation then first of all we shall perform the restricted part of the operation and then perform the remaining part treating it similar to a linear permutation. Ex.38 In how many ways can 6 persons be seated round a circular table when two particular persons sit together ? (A) 120 (C) 48 (B) 240 (D) 24 bp!g (i) 3 when groups are differentiable. 3p! bg (ii) 3 ! p! 3 when groups are not differentiable. For example if 36 distinct objects are to be divided among 9 groups such that four groups have 2 objects each, three groups have 5 objects each and remaining two groups having 6 and 7 objects, then the required number of ways = 36! 4 3 . 2! .4! 5! .3!.6!.7! Sol. First of all let two particular persons be seated DISTRIBUTION AMONG PERSONS together. They can sit together in 2! = 2 ways. Then The number of ways in which n distinct objects can the remaining four persons may sit on remaining four be distributed among r persons in a required way = places in 4 ! = 24 ways, so the total number of ways number of ways of dividing n distinct objects in r= 2 × 24 = 48 Ans.[C] groups in the required way  r!. DIVISION INTO GROUPS (a) The number of ways in which (p + q) things can be divided into two groups of p and q things is p+qC p = p + qCq = bp  qg ! p ! q! Particular case : when p = q, then total number of combinations are 2p! (i) b g p! 2 when groups are differentiable. For example if 36 distinct objects are to be divided among 9 persons such that four of the persons are getting 2 objects each, three of the persons are getting 5 objects each and the remaining two persons are getting 6 and 7 objects, then the number of ways of doing so is 36! 4 3 2! .4! 5! .3!.6!.7!  9! . 2p! (ii) b g 2! p! 2 when groups are not differentiable. 71 Permutations and Combinations Ex.42 The number of ways of dividing 20 persons into 10 couples isEx.39 In how many ways can 15 students (A) (i) be divided into 3 groups of 5 each (ii) be sent to three different colleges in groups of 5 each. 15 ! 15 ! 15! 3 b g b g , 5! 3 15 ! 15! 15 ! (C) 3! 5 ! 3 , 3! 5 ! 3 b g 15 ! (B) 5 ! 3 , 5 ! 3 b g b g (A) 3! 5 ! (B) 20C10 210 20 ! (C) ( 2!)9 (D) None of these Sol. Here the order of the couples is not important. So, required number of ways is b g b g 20 ! 21010 ! Ans. [D] 15! (D) 5 ! 3 , 3 ! 5! b g 20 ! 3 Sol. (i) Total number of combinations of 15 students into PERMUTATIONS IN WHICH THE OPERATION OF 15 ! 3 groups of 5 each = 3 ! 5 ! 3 SELECTION IS NECESSARY There are questions of permutation in which we have (ii) In this case the groups are associated with to start with the operation of selection for the given different colleges, so the required number number of things. After this we calculate the number 15! of different arrangements for each of such selected = 5! 3 Ans.[A] group. b g b g Ex.40 In how many way can 52 playing cards be distributed into 3 groups of 17 cards each and one group of one card. 52! b g (A) 17 ! 3 52! b g (B) 17 ! 3! 3 52 ! b g (C) 17 ! 3 3 ! 2! (D) None of these Sol. The total number of ways 52 ! 52! 3 = 17 ! 17 ! 17 ! 3 ! 17 ! 3! b g Ans.[A] Ex.41 3 copies each of 4 different books are available. The number of ways in which these can be arranged on the shelf is12! (A) 12! (C) 369,600 (B) 3 ! 4 ! (D) 369,000 Sol. The total no. of ways to arrange 3 copies each of 4 different books12 ! = (3 !) 4 = 369,600 Ans.[C] Ex.43 How many words can be formed containing 4 consonants and 3 vowels out of 6 consonants and 5 vowels ? (A) 6C4 × 5C3 (B) 6C4 × 5C3× 7! (C) 6P4 × 5P3 (D) 6P4 × 5P3× 7! Sol. First we select 4 consonant out of 6 and 3 vowels out of 5. This can be done in 6C4 × 5C3 ways. After such a selection of 7 letters then can be arranged in 7! ways. So the total number of words = 6C4 × 5C3× 7! Ans. [B] Ex.44 In how many ways can 7 persons be seated round two circular tables when 4 persons can sit on the first table and 3 can sit on the other ? (A) 420 (B) 35 (C) 210 (D) 2520 Sol. First we divide 7 persons into two groups of 4 and 3 persons. The total number of such division 7! = 4 ! 3! = 35 Now for such a division of 4 and 3 persons there are 3! x 2! ways of sitting round the given two tables. Hence total number of required arrangements = 35 × 12 = 420 Ans.[A] 72 Ex.45 The number of words by taking 4 letters out of the letters of the word ‘COURTESY’, when T and S are always included are(A) 120 (C) 360 (B) 720 (D) None of these Permutations and Combinations Ex.47 There are 4 balls of different colour and 4 boxes of colours same as those of the balls. Then find the number of ways to place two balls in the boxes with respect to their colour. (A) 6 (C) 2 (B) 4 (D) None of these Sol. Since T and S are to be included in every word, therefore first we choose 2 letters out of the remaining Sol. The required number of ways letters which can be done in 6C2 ways. Now each 4! 1 1 1  group of letters will give 4! words. Therefore number 2! 1! 2! of words 1 1 1 = 4.3 =6 6 = C × 4! = 15 × 24 = 360 Ans.[C] 2 LM N 2 LM N OP Q OP Q Ans.[A] MULTINOMIAL THEOREM DEARRANGEMENT THEOREM Any change in the given order of the things is Consider the equation x1 + x2 + . . . +xr = n, where called a Dearrangement . ai  x i  bi ; a i, bi , x i I;i  1, 2, . . ., r. In order to (a) If n items are arranged in a row, then the number of ways in which they can be rearranged so that no one of them occupies the place assigned to it is find the number of solutions of the given equation satisfying the given conditions we observe that the number of solutions is the same as the coefficient of xn in the product LM N 1 1 1 1 1 OP Q n n! 1  1!  2!  3 !  4! .....( 1) n! (b) If n things are arranged at n places then the number of ways to rearrange exactly r things at right places is LM N n! 1 1 1 1 1 1    .... ( 1) n r r! 1! 2! 3 ! 4! (n  r )! OP Q Ex.46 There are 3 letters and 3 envelopes. Find the number of ways in which all letters are put in the wrong envelopes. (A) 6 (C) 2 x a1  x a1 1  x a1 2  . . . x b1 x a 2  x a 2 1  x a 2  2  . . .x b2 x a 3  x a 3 1  x a 3 2  . . .x b3 . . . . . . . x a r  x a r 1  x a r 2  . . . x b r . For example, if we have to find the number of nonnegative integral solutions of x1 + x2 + .. . + xr = n, then as above the required number is the coefficient of xn in (B) 4 (D) None of these Sol. The required number of ways LM N 1 1 1 = 3! 1  1!  2!  3 ! = 3! – 3! + OP Q = Coefficient of xn in (1 + x + x2 + . . . + xn)r = Coefficient of xn in (1 + x + x2 + . . . )r 3! –1 2!  3–1=2 = Coefficient of xn in (1 – x)– r Ans.[C] = Coefficient of xn in 73 Permutations and Combinations Application of multinomial theorem If we want to distribute n identical objects in r different groups under the condition that empty groups are not allowed. a1 + a2 + a3 +.....+ ar=n 3! Boundary conditions are 1  a1, a2......ar  n (As each box contains at least one object) = Coefficient of xn in Number of ways 1  r C1x  r1 C 2 x 2 r 2 C3 x 3  . . .    n  r 1 = coefficient of xn in (x1 + x2 +......+xn)r = coefficient of xn–r in (1 + x + x2 +.....+xn–1)r Cn  n  r 1 Cr 1 . = (n – r) + r – 1Cr–1 = n–1Cr–1 Note : If there are  objects of one kind, m objects of second kind, n objects of third kind and so on; then the number of ways of choosing r objects out of Ex.49 Find the number of ways in which 16 identical these objects is the coefficient of xr in the expansion toys are to be distributed among 3 children such that each child does not receive less than 3 toys. of (1 + x + x2 + x3 + . . . + x  ) Sol. Let x1, x2, x3 be the number of toys received by the three children Further if one object of each kind is to be included, then the number of ways of choosing r objects out Then, x1 , x2, x3 ,  3 and x1, x2, x3 = 16 of these objects is the coefficient of xr in the expansion Let u1 = x1– 3, u2 = x2 – 3 and u3 = x3 – 3 of Then, u1 , u2, u3  0 and u1 + u2 + u3 = 7 (x + x2 + x3 + . . . + x  ) Here, n = 7 and r = 3 (x + x2 + x3 + . . . + xm)  Number of ways = n+r–1Cr – 1 = 9C2= 36 (x + x2 + x3 + . . . + xn) . . . (1 + x + x2 + . . . + xm) (1 + x + x2 + . . . + xn). Ex.50 Find the number of non-negative integral solutions of x1+ x2+ x3 + 4x4 = 20. Ex.48 Find the number of non negative integral solutions Sol. Here, clearly 0  x  5, x , x , x ,  0 4 1 2 3 of and x1 + x2 + x3 = 20 – 4x4 x1 + x2 + x3 + 4x4 = 20.  r = 3 and n = 20 – 4x1 Sol. Number of non negative integral solutions of the given If x4 = 0 number of ways 20+3 – 1C3 – 1 = 22C2 equation If x4 = 1 number of ways 16+3 – 1C3 – 1 = 18C2 = coefficient of x20 in Similarly, if x4 = 2, 3, 4, 5, number of ways = 14C2, (1– x)–1 (1 – x)–1(1 – x)–1 (1 – x4)–1 10C , 6C , 2C respectively 2 2 2 = coefficient of x20 in (1 – x)– 3(1 – x4)– 1  Total number of ways = coefficient of x20 in = 22C2 + 18C2 + 14C2 + 10C2 + 6C2 + 2C2 = 536 (1 + 3C x + 4C x2 + 5C x3 + 6C x4 + . . . ) 1 2 3 4 (1 + x4 + x8 + . . . ) = 1 + 6C4 + 10C8 + 14C12 + 18C16 + 22C20 = 536. 74 Permutations and Combinations Ex.51 In how many ways can 10 identical toys be distributed among 3 children such that the first receives a maximum of 6 toys, the second receives a maximum of 7 toys and the third receives a maximum of 8 toys. Sol. Let x1, x2 and x3 be the number of toys received by the three children. Then, =    Coefficient of x4 in 4!  1  x  x2 2!     3 1 x 5 = Coefficient of x4 in 4!   x6 3 3 3  (1  x )2 x 2  x 4 (1  x ) . 1 x (1  x )  8 2 4   5 = Coefficient of x4 in 4!   x6 3 3 8 ( 1  x )  (1  x )5  x 2 (1  x 7 )  x 4 (1  x )6   8 2 4   x1+x2+x3=10, 0  x1  6, 0  x2  7, 0  x3  8  Required number of ways = coeff of xn in (x0 + x1 + x2 +...... x6)(x0 + x1 + x2 +......x7) (x0 + x1 + x2+.....x8) = coeff of x10 in 1(1  x 7 )  1(1  x 8 )  1(1  x 9 )       1  x   1  x   1  x  = coeff of x10 in 37 3 8 = 4 !  C 4  0  2 C2  4     8.7.6.5 3 7. 6 34  = 24  1.2.3.4  2  1. 2  3    = 8.7.6.5 + 6 (3.7.6) + 6.3 = 1680 + 756 + 18 = 2454 NUMBER OF DIVISORS [(1 – x7)(1 – x8)(1 – x9)] [ 1 – x]–3 = coeff of x10 in (1 – x 7 – x 8 – x 9 ......)(1 + 3 C 1 x + 4 C 2 x 2 + 5C3x3 + ......12C10x10 +.....) (i) Every natural number N can always be put in the form N = p 1  1 p 2 2 . . . p k  k where p1, p2 . . . pk are distinct primes and 1, 2, . . . k are non negative integers.    {Note that powers >10 are unimportant and hence (ii) If N = p1 1 p2 2 . . . pk k then number of divisor of N = (1 + 1) (2 + 1) . . . (k + 1) which includes 1 ignored} and N also. Note : All the divisors excluding 1 and = 12C10 – 5C3 – 4C2 – 3C1 = 66 – 10 – 6 – 3 – = 47 N are called proper divisors. Ex.52 In how many ways 5 identical balls can be (iii) The sum of the divisors of N distributed into 3 different boxes so that no box = (1 + p1 + p12 + . . . + p11) (1 + p2 + p22 + . . . + remains empty? p22) . . . (1 + pk + pk2 + . . . + pkk) 5-1 Sol. The required number of ways = C3–1 =4C 4 .3 2 = 1 .2 = 6 p11 1  1 p 2  2 1  1 p k  k 1  1 . . . . = p1  1 p2 1 pk 1 Ex.53 Find the number of permutation of 4 letters taken (iv) The number of ways of putting N as a product of two natural numbers is from the word EXAMINATION. 1 Sol. Number of permutations are : (1 + 1) (2 + 1) . . . (k + 1) if N is not a 2 (AA), (I I), (NN), E, X, M, T, O perfect square. If N is a perfect square then this is 3 5 2 1  x x   x [(1 + 1) (2 + 1) . . . (k + 1) + 1] = Coefficient of x4 in 4! 1  1!  2!  1  1!  2     75 Permutations and Combinations EXPONENT OF PRIME IN n! Let p be a given prime and n any positive integer, then maximum power of p present in n! is n p +   n n  2    3   . .., where [] denotes the p  p  greatest integer function. The proof of the above Ex.54 The sum of all numbers which can be formed with digits 1,2 and 3 is(A) 716 (C) 2148 (B) 1432 (D) None of these Sol. The sum of the digits = 1 + 2 + 3 = 6 and n = 3, so the sum of all numbers formed = 6 . 2! (111) n formula can be obtained using the fact that  m    = 12 × 111 = 1432 Ans.[B] gives the number of integral multiples of m in SOME IMPORTANT RESULTS 1, 2, . . . , n; for any positive integers n and m. The above formula does not work for composite ABOUT POINTS If there are n points in a plane of which m (< n) are numbers. For example if we have to find the maximum collinear, then power of 6 present in 32!, then the answer is not (a) Total number of different straight lines obtained by  32   32  joining these n points is  6    6 2   . . .  5 , as 5 is the number of integral   nC – mC + 1 2 2 multiples of 6 in 1, 2, . . . , 32; and 6 can be obtained (b) Total number of different triangles formed by joining on multiplying 2 by 3 also. Hence for the required these n points is nC – mC number, we find the maximum powers of 2 and 3 3 3 (say r and s) present in 32!. Using the above formula (c) Number of diagonals in polygon of n sides is r = 31 and s = 14. Hence 2 and 3 will be combined n (n  3) nC – n i.e. 2 (to form 6) 14 times. Thus maximum power of 6 2 present in 32! is 14. (d) If m parallel lines in a plane are intersected by a family of other n parallel lines. Then total number of SUM OF NUMBERS parallelograms so formed is (a) For given n different digits a1, a2, a3 ......,an the sum mn (m  1) (n  1) mC × nC 2 2 i.e. of the digits in the unit place of all numbers formed 4 (if numbers are not repeated) is (a1+ a2 + a3 + ......+ an) (n-1)! i.e. (sum of the digits) (n-1)! (b) Sum of the total numbers which can be formed with given n different digits a1, a2, a3 .....an is (a 1 + a2 + a3 + ....+ an)(n–1)!.(111 ...n ties) 76