2 PERMUTATION Permutation and Combination For putting n things at n places, there is simply one way to complete the task. But if the order of things is considered, then there are several ways. In this case, we use the word arrangement and the process is termed as permutation. Example 3 : Solution How many number can be formed using the digits 7, 8 and 9 without using any mathematical symbol (e.g. 798, 798, 798, 789). Number of numbers of each form abc, abc, abc and ab are 3P3. Therefore total numbers = 4 x 3 = 24. COMBINATION If in the above case we use the word 'selection' instead of 'arrangement', then the order of things is of no importance and the process is termed as combination. While dealing with permutation and combination, there is fundamental principal of counting to be acquainted with. Example 4 : Solution: There are two boys Bl and B2. Bl has ni different toys and B2 has different toys. Find the number of ways in which Bl and B2 can exchange their toys in such a way that after exchanging they still have same number of toys but not the same set. Total number of toys = m + Now let us keep all toys at one place and ask Bl to pick up any ni toys out of these m + ru toys. He can do it in Cn ways Out of these ways there is one way when he picks up those ni toys which he was initially having. Thus required number of ways are n Cn -1. CIRCULAR PERMUTATIONS (ii). When view is one sided i.e. clockwise and anticlockwise arrangements are different. Number of circular permutations of n things taken all together Number of circular permutations of n things taken r at a time When view is two sided i.e. clockwise and anticlockwise arrangements are same. Number of circular permutations of n things taken all together 1 Number of circular permutations of n things taken r at a time 1 Number of combinations of n different things taken all together = 1 Number of combinations of n different things taken r at a time = ncr = r!(n—r)! ncr = ncn-r If = , then either x = y or x + y = n Number of combinations of n different things taken r at a time when p particular things are always included Number of combinations of n different things taken r at a time when p particular things are always to be excluded

Permutation and Combination Number of combinations of n different things taken one or more at a time 3 Number of selections of one or more things from p identical things of one type, q identical things of another type, r identical things of third type and rest is different things Example 5 : Solution Find the number of ways of arranging 4 boys and 4 girls in a circle so that boys and girls are alternate. First of all we arrange 4 girls in a circle, whose number of ways is g = 6. For any of their arrangement, the four boys can be arranged (at alternate positions) in 14 ways (as after arranging the girls, the positions in the circle are labeled). Thus totally there are 144 ways. ALL POSSIBLE SELECTIONS Selection from distinct objects: The number of selections from n different objects, taken at least one _ Cl + nC2+11C3+ + ncn = 2n — l. In other words, for every object, we have two choices i.e. either select or reject in a particular group. .. n times = 2 n Total number of choices (all possible selections) = 2.2.2 But this also includes the case when none of them is selected and the number of such cases = 1. Hence the number of selections, when at least one is selected = 2 — 1. Selection from identical objects: (a) The number of selections of r objects out of n identical objects is 1. (b) Total number of selections of zero or more objects from n identical objects is n + 1. (c) The total number of selections of at least one out of al+a2+Q+. +an objects, where al are alike (of one kind ), a2 are alike (of second kind ) and so on . . an are alike (of nth kind ), is Selection when both identical and distinct objects are present: The number of selections taking at least one out of al+a2+Q+... .+an+k objects, where al are alike (of one kind), a2 are alike (of second kind) and so on . an are alike (of nth kind), and k are distinct = .. (an-I-I) ] 2k 1. Example 6. Solution: Let a person have 3 coins of 25 paise, 4 coins of 50 paise and 2 coins of 1 rupee. Then, in how many ways can he give none or some coins to a beggar? Further find the number of ways so that (i) he gives at least one coin of one rupee. (ii) he gives at least one coin of each kind . Total number of ways of giving none or some coins is (3 + 1) (4 + 1) (2 + 1) = 60 ways (i) Number of ways of giving at least one coin of one rupee = (3 + 1) (4 + 1) x 2=40 (ii) Number of ways of giving at least one coin of each kind 24. Total number of divisors of a given natural number: To find number of divisors of a given natural number greater than 1 we can write n as oq Cc n = PI ...pnn where PI, P2, pn are distinct prime numbers and 011, 012,...un are positive integers. Now any divisor of n will be of the form d ...pk ( where 0 < < , e l, V i = Here number of divisors will be equal to numbers of ways in which we can choose PI's which can be done in (UI + + + 1) ways. e.g. Let n = 360 n = 23.32.5

4 No. of divisors of 360 = (3 + 1) (2 + 1) (1 + 1) = 24 Sum of all the divisors of n is given by -1 -1 P2 —1 24-1 33 As in above case, sum of all the divisors = 2 3 _ 1 52 5 Permutation and Combination = 1170 Remark: The number of factors of a given natural number 'n' will be odd if and only if 'n' is a perfect square. DIVISION AND DISTRIBUTION OF OBJECTS (with fixed number of objects in each group) Into groups of unequal size (different number of objects in each group): (a) (b) Number of ways in which n distinct objects can be divided into r unequal groups containing al objects in the first group, a2 objects in the second group and so on C n—al —a2 C al ! a!. Here al + a2 a3 ... + ar = n. Number of ways in which n distinct objects can be distributed among r persons such that first person gets al objects, 2nd person gets a2 objects... ,rth person gets ar objects al ! a! Explanation: Let us divide the task into two parts . In the first part, we divide the objects into groups. In the second part, these r groups can be assigned to r persons in r! ways. Into groups of equal size (each group containing same number of objects): (a) (b) Number of ways in which mxn distinct objects can be divided equally into n groups (unmarked) - (mn)! Number of ways in which mx n different objects can be distributed equally among n persons (or (mn)!n! (mn)! numbered groups)= (number of ways of dividing into groups)x(number of groups)! = Derangements: If n things are arranged in a row, the number of ways in which they can be deranged so that none of them occupies its original place is 1 r! Example 7: Solution: Suppose 4 letters are taken out of 4 different envelopes. In how many ways, can they be reinserted in the envelopes so that no letter goes in to its original envelope? Using the formula for the number of derangements that are possible out of 4 letters in 4 envelopes, we get the number of ways as : 1 1 1 1 1 1 24 1 — 1 + — 2 6 24 9. USE OF MULTINOMIAL THEOREM IN PERMUTATION AND COMBINATION The general term in the expansion of ... (1) is ... (2) where 2 oq !...u ! 011 + 012 Number of terms in the expansion of (1) is number of non-negative integral solutions of (3) i.e. number of ways of distributing n identical things among m persons when each person can get m+n—l m+n—l zero or more things = Cn or Cm I

Permutation and Combination Now in (1 + ax) n coeff. of xr 5 number of ways of selecting r a's out of n a's, which is same as coeff. of xr in We can use this concept while deaing with problems of permutation and combination. Let out of n things p are of one type and rest are different. Now we have to select r things out of these n things. For this, we to select one from p alike things and (n — 1) from rest different things or 2 from p alike and (n — 2) from rest different things and so on i.e. Coeff. of xr in (1 + x + +...+ XP) (1 + x)n-P In same way number of solutions (integral solution) of + + + ...+ = n, where , am < < bm is coefficient of xn in the expansion of al < bl; a2+1 Number of combinations of r things out of n things of which p are alike and are of one kind, q are alike and of second kind and rest (n — p — q) are different = coefficient of xr in (1 + x + + .. + XP) (1 + x + + ... + k) (1 +x) p—q—r Number of ways in which r identical things can be distributed among n persons when each person can get zero or more things = coeff. of xr in (1 + X + + .. + k) n Number of non-negative integral solutions of the equation x + 2y + 3z + 4w = n = coefficient of permutations of r things out of n things of which p are of one kind, q are of second kind and so on 2 = r! . coeff. of Win 1+1+&+...+— p! 2 q x q! Example 8. Solution: Yr 3 and number of squares = 2 Number of rectangles of any size in a square of size nx n = r=l r=l Number of ways of distribution of n distinct balls in r distinct boxes when order is considered = n! lcr-l if blank boxes are not allowed Cr-l if blank boxes are allowed. Number of ways of distribution of n identical balls into r distinct boxes n—l Cr I if blank boxes are not allowed Cr-l if blank boxes are allowed. Number of ways of distribution of n distinct balls into r distinct boxes when order is not considered = rn if blank boxes are allowed = n! coefficient xn in (ex — 1 y Find the number of ways in which 10 girls and 90 boys can sit in a row having 100 chairs such that no girls sit at the either end of the row and between any two girls, at least five boys sit. First we select 10 chairs which will be occupied by 10 girls under the given condition. Now these 10 selected chairs will divide the remaining 90 chairs into 11 parts Therefore no of ways of selecting 10 chairs No of solutions of + + + .... + = 90 under the condition > 1, , 25 = coefficient of t90 in ( t + t2 + t3+ 9 = coefficient of t43 in (1 + t + t2 ) 11 = coefficient of t43 in (1 — t) Il 53C43 53 Hence the required number of ways is C43 x 10! x 90!