Permutation and Combination AN INTRODUCTION Groups And Arrangements Suppose we have three letter a,b,c and we are asked to form groups consisting of two letters each. The groups are ab,ac,bc. Now the letters of each one of these groups can be arranged in two different ways and we get the following arrangements: ab,ba;ac,ca;bc,cb. In forming the groups we ignore the order in which the letters occur. But in making arrangements we also take into account the order in which the letters are to be placed. Permutation And Combination Permutation: Each of the different arrangements which can be made by taking some or all the numbers or things at a time is called a permutation. Combination: Each of the groups or selections which can be made by taking some or all of a number of things at a time is called a combination. That means “permutation” is related with arrangements and “combination” is related with groups. Permutation And Combination Permutation And Combination We use the symbol nPr or P(n,r) to denote the number of “permutations” of n different things taken r at a time. And we use the symbol nCr or C(n,r) to denote the number of combinations of n different things taken r at a time. rW, n N, 0≤r≤n. Now nPr= n/ (n-r) and nCr = n/ ( r (n-r) ) Some facts about Permutation nPr=n(n-1)(n-2)(n-3)……upto r factors. nPr=n(n-1)(n-2)(n-3)……..(n-r+1) nPn= n and nP1=n. Examples A lady wants to select one cotton saree and one polyester saree from a shop. If there are 10 cotton varieties and 12 polyester varieties, in how many ways can she choose the two sarees? There are 12 buses running between Una and Amb. In how many ways can a man go from Una to Amb and return by a different bus? The license plates for vehicles registered in Delhi consist of 3 letters (of English alphabet) followed by 1,2,3, or 4 digits. The letter on the extreme left has to be ‘D’. For the 1-digit number plates, the number 0 is not allowed. For others, the digits and the letters, of course, can repeat, but the numbers should be significant. Determine the possible number of license plates. Solution A sequence of three letters beginning with D can be chosen in 26 x 26=676 ways as explained below: First Letter Second Letter Third Letter D 26 ways 26 ways 1 26 26 676 Solution Corresponding to each sequence of four digits, there are 9999 license plates possible as any number from 1 to 9999 can be allotted. Hence, the possible number of license plates =676 x 9999=676(10000-1) =6760000-676=6759324 Fundamental Principle of Counting (Association) If one operation can be performed in m different ways and if corresponding to each way of performing this operation, there are n different ways of performing second operation, the two operations together can be performed in m x n ways. Generalization: if there are p different ways to performing a third operation corresponding to each of m x n ways of performing the first two operations, then the three operations together can be performed in m x n x p ways, and so on. Exercise 1.1 How many numbers are there between 100 and 1000 in which all the digits are distinct? How many numbers are there between 100 and 1000 such that every digit is either 2 or 5? How many numbers are there between 100 and 1000 such that the digit in the unit’s place is 7. How many numbers are there between 100 and 1000 such that at-least one of the digits is 8. How many numbers are there between 100 and 1000 such that exactly one of the digits is 5. Exercise1.2 Find the value of 20P 3 Answer: 6840 Find the value of n if n P4 : n-1 P3 =9:1 Answer: n=9 Find the value of n if P(n,4)=20P(n,2) Answer: n=7 Combinations To find the number of combinations of n different things taken r at a time can be represented by nCr and nCr= n/rn-r, where 0≤r≤n Some facts about combinations: nC =1 n nC =1 0 nC = nC r n-r nC = nC =n n-1 1 Practical Problems on Combinations To find the number of ways in which m+n things can be divided into two groups containing m and n things respectively. C(m+n,n)=m+n/mn ways To find the number of ways in which a selection can be made out of p+q+r things of which p are alike of one kind, q are alike of another kind and remaining r are different. =(p+1)(q+1)2r -1 ways Exercise 1.3 In how many ways can a Football Eleven be selected out of 15 players? 1. 2. In how many of them a particular player is included. In haw many of them he is excluded? In first situation we have to include a particular player, so we have 14 players and we have to choose 10 players out of those remaining 14 players so the combination is 14C10 In second situation we have to excluded a particular player, so we have 14 remaining players and we have to choose 11 players out of those remaining 14 players so the combination is 14C11 Exercise 1.3 A committee of 6 members is to be formed from 6 boys and 4 girls. In how many ways can this be done if the committee contains 2 girls ? 2. atleast 2 girls ? In first case exactly 2 girls are there in the committee. So we have to choose in total 6 members. 2 girls out of 4 girls present. And remaining 4 boys out of 6 boys present. So by the principle of association the required number of ways are 6C4 X 4C2 =90 In second case atleast 2 girls means there can be 2,3 or 4 girls in the committee. So the required number of ways are 6C4 X 4C + 6C X 4C + 6C X 4C =185 2 3 3 2 4 1.