Understanding Permutations and Combinations in Mathematics
Permutations and combinations are fundamental concepts in mathematics that test logical reasoning and problem-solving skills. This article covers the basics of permutations, combinations, factorial, fundamental counting principles, and example questions to help you grasp these concepts effectively. Dive into the logical world of mathematics and enhance your problem-solving abilities without the need to memorize formulas.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Permutation And Combination
Contents: 1. Introduction 2. Fundamental Principle of Counting 2.1 Product Rule 2.2 Addition Rule 3. Permutations Introduced 4. Special Cases of Permutations 5. Geometrical arrangements 6. Combinations 7. Grouping & Distribution 8. Example Questions 9. Practice Questions
1. Introduction: Permutations and Combinations is one of the most logical phenomenon of mathematics wherein there are no formulae to mug up. Rather, it tests your ability to understand the problem and interpret the situation logically. It is more of application of common sense. That is why you will see that most questions can be solved without actually knowing the techniques of permutations and combinations. Great news, isn t it?
Before proceeding further, let us quickly define Factorial!!! Factorial of a number or n! is the product of n consecutive natural numbers starting from 1 to n. Factorial word is represented by ! or L . Hence, 4! is 1x2x3x4 = 24. Note: Factorial of zero or 0!=1
2. Fundamental Principle of Counting 2.1 Product Rule If one operation can be done in x ways and corresponding to each way of performing the first operation, a second operation can be performed in y ways, then the two operations together can be performed in xy ways. If after two operations are performed in any one of the xy ways, a third operation can be done in z ways, then the three operations together can be performed in xyz ways. Let us take an example. permutation combination A, B, C and D are four places and a traveller has to go from A to D via B and C.
He can go from A to B in 4 ways and corresponding to each way he can take any one of the 2 ways to reach C. Hence A to C can be reached in 4 2=8 ways. Corresponding to each of these 8 ways of reaching C from A, there are 3 ways to reach D and the traveller can choose any one of them. Hence, A to D can be reached in 4x2x3=24 ways! Here the different operations are mutually inclusive. It implies that all the operations are being done in succession. In this case we use the word and to complete all stages of operation and the meaning of and is multiplication.
Example: A tricolor flag is to be formed having three horizontal strips of three different colors. 5 colors are available. How many differently designed flags can be prepared? Solution: First strip can be coloured in 5 ways, second strip can be coloured in any of the remaining 4 colors, and the third strip can be coloured in any of the remaining 3 colors. Hence, we can get 5x4x3 = 60 differently designed flags.
2.2 Addition Rule If there are two operations such that they can be performed independently in x and y ways respectively, then either of the two jobs can be done in (x + y) ways. Let us take the example of four placesA, B, C and D taken above. permutation combination There are 4 different roads from B to A and 2 different roads from B to C. In how many ways can a person go to A or C from B? The answer is 4+2=6 ways. Here, the different operations are mutually exclusive. It implies either of the operations is chosen. in this case we use the word or between various operations and the meaning of or is addition. The product rule and the addition rule signify the cases of and & or .
3. Permutations Introduced The arrangements of a given number of things taking some or all of them at a time are called permutations. For example, the permutations of three alphabets x, y, z taken two at a time are xy, xz, yx, yz, zx, zy. A point to be noted is that arrangement or order is very important in permutations. Hence xy is distinctly different from yx. If r things are taken at a time out of a total of n things, then the total number of permutations is denoted bynPr. n Pr=n!/(n-r)!
Now you will ask why is this so. Lets clear this. First object can be selected in n ways. Second object can be selected in (n-1) ways. Third object can be selected in (n-2) ways. Similarly the rth object can be selected in (n-(r-1)) = (n-r+1) ways. Therefore the total number of ways of arranging these r objects = n x (n-1) x (n-2) x (n-3) x x (n-r+1) ={n x (n-1) x (n-2) x (n-r+1) x (n-r) x (n-r-1) x .3 x 2 x 1} / {(n-r) x (n-r-1) x ..x 1} = n! / (n-r)! Hence,nPr= n! / (n-r)!
Example 1: There are 4 boxes. Find the total number of arrangements if we can arrange only 2 boxes at a time. Solution: Out of 4 boxes, we are arranging 2 at a time. So total number of arrangements possible is 4P2= 4! / (4-2)! = 4! / 2! = 4x3x2x1 / 2 1 = 12 Let us verify. Let us name the boxes A, B, C, D. Total number of arrangements possible are AB, BC, CD, BA, BC, BD, CA, CB, CD, DA, DB, DC. Permutations of n different things taken r at a time = nPr= n! / (n-r)!
Example 2: In the above example, what if all the 4 boxes are selected at a time? How many arrangements are possible then? Solution: Total no. of arrangements possible =4P4= 4! / (4-4)! = 4! / 0! = 4! = 4x3x2x1 = 24. Permutations of n different things taken all at a time = nPn= n!
Example 3: If out of the 4 boxes, one particular box should always be selected; then how many arrangements are possible if 3 boxes are selected at a time? Solution: Since one box should always be selected we have to select 3-1 boxes out of 4-1 boxes. This can be done in3P2= 3! / (3-2)! = 3! / 1! = 3x2x1 / 1 = 6 arrangements. With each of these 6 arrangements our preselected box can be arranged in 3 6 = 18 ways. Wondering how?
Let us name these boxes A, B, C and D and D has to be always present. So now A, B and C can be arranged as AB, AC, BA, BC, CA, CB. With AB, D can be arranged as DAB, ADB, ABD i.e. 3 ways. D can be arranged with the remaining 5 arrangements similarly. Hence in total there can be 18 arrangements. Permutations of n different things taken r at a time, when one particular thing always occurs = r.(n-1)P(r-1)
Example 4: How many arrangements are possible if out of the 4 boxes A, B, C and D one particular box D is never selected, taken 2 at a time? Solution: Since D is never to be selected, we have to take into account A, B and C. We can arrange A, B and C taken 2 at a time in3P2= 3! / (3-2)! = 3! / 1! = 3x2x1 / 1 = 6 ways. i.e. AB, AC, BA, BC, CA, CB. So when one particular item is never chosen, we just ignore it and treat the problem as if that particular item is not present in the total number of items. Permutations of n different things taken r at a time when a particular thing never occurs =(n-1)Pr.
Shortcut Tip: We know thatnPr= n! / (n-r)! Let us say we have to find out12P3. 12P3= 12! / (12-3)! = 12! / 9! = 12x11x10x ..x1 9x8x7x 1 = 12x11x10 =1320 Instead of writing out so much, the moment you see12P3you should know that you have to multiply 3 numbers. Starting from 12, we take in 3 numbers in the descending order and multiply them out. Learn to get into the habit of writing12P3=12x11x10 straightaway. This helps in faster calculation.
4. Special Cases of Permutations: Reap to Remember: With respect to fundamental principle of counting, and stands for multiplication & or stands for addition nPr= n!/ (n-r)! Permutations of n different things taken r at a time =nPr= n! / (n-r) Permutations of n different things taken all at a time =nPn= n! Permutations of n different things taken r at a time, when one particular thing always occurs = r.(n-1)P(r-1) Permutations of n different things taken r at a time when a particular thing never occurs =(n-1)Pr
Example: 5 In in how many ways can the letters of the word WATER be arranged so that we have a new pattern every time? Solution: This is permutation of n different things taken all at a time which is equal to n! Hence, total number of different arrangements possible is 5! =120. Another way to look at it is we have 5 places to be occupied by 5 different letters. The 1st place can be filled by any of the 5 letters, hence 5 ways. The 2nd place can be filled by any one of the remaining 4 letters as one letter has already been fixed at the first place, hence 4 ways. Similarly, the 3rd place can be filled in 3 ways and the 2nd in 2 ways. The 5th place can be filled in only one way as there is no choice but to fill it by the remaining 1 letter. So going by the product rule, this can be done in 5x4x3x2x1 = 120 ways.
Permutation of n things when some are identical or Permutation of n things not all different: What happens when we have to find out the number of permutations when certain items are identical? If 2 exactly similar red chairs(R1 & R2) and 1 black chair(B) are to be arranged, then please note that one cannot distinguish between the 2 red chairs. This is to say that there is no difference between R1 B R2 and R2 B R1 because they will both look the same as I cannot differentiate between R1 and R2 as they are exactly same. So the total no. of arrangements possible will be 3! / 2! = 3. They will be BRR RBR RRB. We have divided by 2! to take care of the two items that are same. If out of n things, p are exactly alike of one kind, q exactly alike of second kind and r exactly alike of third kind and the rest are all different, then the number of permutations of n things taken all at a time = n! / (p!q!r!)
Example 6: In how many ways can the letters of the word COMMITTEE can be arranged i. using all the letters ii. if all the vowels are together Solution: i. Total letters = 9 and identical letters are 2M 2T and 2E. So total no. of arrangements = 9! / 2!2!2! ii. Since all vowels must appear together we consider them as one unit. There are 4 vowels- O I E E. So now we have 5 letters. Out of these we have 2M and 2T. These 5 letters can be arranged in 5! / 2! 2! ways. In the group of 4 vowels, the 4 vowels can arrange themselves in 4!/2! ways. So total no. of words formed = 5!/2! 2! X 4!/2!
Permutations where repetitions are allowed: While dealing with letters and digits, you will often come across cases where repetition in permutation is allowed or not allowed. You have to be very careful as to what is asked for because the treatment for both the cases is absolutely different.
Example 7: How many numbers of 5 digits can be formed with the digits 0,1,2,3,4 i. if the digits cannot repeat themselves ii. if the digits can repeat themselves Solution: i. The 1st place (ten-thousandth place) can assume only non-zero digits. Hence it can be occupied in 4 ways. The 2nd place can be occupied by any of the remaining 4 digits, i.e. 4 ways. Similarly, the 3rd, 4th and 5th place in 3, 2 and 1 ways respectively. Total no. of numbers formed = 4x4x3x2x1 = 96
ii. The 1st place (ten-thousandth place) can assume only non-zero digits. Hence it can be occupied in 4 ways. Since repetition is allowed, the 2nd, 3rd, 4th and 5th places can all be filled in 5 ways each i.e. we have a choice of 5 digits (0,1,2,3,4) for each place. So total no. of numbers formed = 4x5x5x5x5 = 4 54=2500 The number of permutations of n different things taken r at a time, when each may be repeated any number of times in each arrangement is nr.
Example 8: How many different four letter words can be formed (the words need not be meaningful) using the letters of the word MEDITERRANEAN such that the first letter is E and the last letter is R? Solution: MEDITERRANEAN is 13-letter word. We have to make 4 letter words that start with an 'E' and end with 'R'. Therefore, we have to find two more letters from the remaining 11 letters. Of the 11 letters, there are 2 Ns, 2Es and 2As and one each of the remaining 5 letters. The second and third positions can either have two different letters or can have both as same letters. Case 1: When the two letters are different One has to choose two different letters from the 8 available different choices. This can be done in 8 * 7 = 56 ways. Case 2: When the two letters are same There are 3 options - the two letters can be Ns or Es or As. Therefore, 3 ways. Total number of possibilities = 56 + 3 = 59
Finding Rank of a Given Word: RANK OF A WORD IN DICTIONARY!!! Rank of a word is the position of that word, when we arrange the words formed by alphabets of that given word in dictionary order. Lets see an example. If we are to find the rank of the word RANK in the dictionary what does that mean? There are 4 alphabets in the word RANK so we can form 4! = 24 words by arranging them. This means that if we form words by permutation of the alphabets of the word RANK and form a dictionary of these words, at what position from the top will the word RANK lies.
Now to find the rank of any given word in dictionary (Without Repeating Alphabets) Example MOTHER 1. Arrange all the alphabets in alphabetical order like (E, H, M, O, R, T) 2. Now in dictionary words will appear in alphabetical order, so first words will appear starting alphabet E . When E is fixed at first position, rest 5 alphabets can be arranged in 5! = 120 ways. 3. Next starting alphabet will be H and again there will be 5! = 120 words starting with H . 4. Now starting with M , and next alphabet as E we will have 4!=24 words. 5. Similarly starting with M , and next alphabet as H we will have 4!=24 words.
6. Next will be starting with M, and next alphabet as O and next as E we ll have 3!=6 words. 7. Similarly starting with M , and next alphabet as O and next as ( H or R ) we ll have 3!*2=12 words. 8. Next will be starting with M , and next alphabet as O and next as T and next as E we ll have 2!=4 words. 9. Next will be starting with M , and next alphabet as O and next as T and next as H will have 2! = 4 words but the first word will be M>O>T>H>E>R which is the desired word. So the rank of word MOTHER in dictionary will be 5! + 5! + 4! +4! + 3! + 3! + 3! + 2! +1 which equals 309. So the word MOTHER will be at 309th position if we form the whole words that can be created using the letters of MOTHER arranged in dictionary order.
Example: INDIA (With repeating Alphabets) Alphabetical order -ADIIN Start with A, A = 4! / 2! = 12 (Coz there are 2 I s) D = 4! / 2! = 12 (Coz there are 2 I s) [I]A = 3! = 6 [I]D = 3! = 6 [I]I = 3! = 6 [IN]A = 2! =2 [IND]AI = 1 [IND]IA = 1. Summing it up gives you the rank 12 + 12 + 6 + 6 + 6 + 2 + 1 + 1 = 46.
Shortcut for finding Rank: (Without repetition) Take the Word SURYA A R S U Y // Alphabetical Order 1. 2*(4!) = 48// Search for S. Remove that word from the list and see how many letter before S? 2 letter. 2. 2*(3!) = 12 // Search for U. Remove that letter and count the letters before U now. Its 2. 3. 1*(2!) = 2 // Search for R. Remove that letter and count the letters before R. Its 1. 4. 1*(1!) = 1// Search for Y. Remove that letter and count the letter before Y. Its 1. 5. Add the whole numbers. and add 1 for last letter A. Sum: 48 + 12+ 2 + 1 + 1 = 64.
5. Geometrical arrangements: Circular permutation: Sitting in a circle is not the same as sitting in a straight line. A circle does not have any starting point or ending point. Thus in a circular permutation, one thing is kept fixed and the others are then arranged relative to this fixed item. Then it is treated like a linear arrangement. The number of circular permutations of n different things taken all at a time = (n-1)!
Fix any one as reference point, the remaining other n-1 things can be arranged in (n-1)! ways. What if we are taking into consideration beaded necklace or a garland wherein clockwise and anticlockwise arrangements are the same? We simply divide (n-1)! by 2 to take into account the two same clockwise and anticlockwise arrangements. If the clockwise and anticlockwise orders are not distinguishable, then the number of permutations = (n-1)! / 2
Arrangement around a regular polygon: If n people are to be arranged around a p sided regular polygon, such that each side of the polygon contains the same number of people, then the number of arrangements possible is n!/p. For example: 15 people are to be arranged around a pentagon shaped table having 3 people on each side of the table, number of arrangements will be 15!/5. Please note if the polygon is not regular, then the number of arrangements will be n! irrespective of the sides of the polygon.
Special case of arrangement around a rectangular table: Rectangle is a special case because though it is not a regular polygon, it is a symmetrical quadrilateral with opposite sides equal. So, if n people are to be arranged around a rectangular table, such that there are the same number of people on each of its 4 sides, then the total number of arrangements possible is n!/2. Here 2 signifies the degree of symmetry of the rectangle.
6. Combinations: Difference between Permutations and Combinations: Suppose there are 3 bags (A,B and C) in my home and I want to select any 2 out of them to take with me on my holiday. In how many ways can I make the selection? Clearly I select either AB or BC or AC i.e. 3 ways. An important point to note is that we are talking about selection and not order here. Obviously whether I select AB or BA makes no difference.
Let us take one more example: Suppose from a class of 10 students I have to select 3 students for a play, it is a case of Combinations. But, if I have to arrange 3 students in a line from a class of 10 students, it is a case of Permutations. I hope I have made it clear that in permutations (rearrangement) order matters but in combinations (selections) order does not matter. We are now in a position to define Combinations!!!
Definition of Combinations: Combinations is the selection of some or all of a total of n number of things. If out of n things we have to select r things (1 r n), then the number of combinations is denoted by nCr= n!/r!(n-r)! Combinations arrangements of the selected things. This explains division by r! which denotes the arrangement of the selected r things. does not deal with the
Important relation between Permutations and Combinations r selected things can be arranged in r! ways. So, r! x nCr=nPr or, nCr=nPr/ r! or nCr= n! / r! (n-r)!
Example 9: In a class there are 6 boys and 5 girls. In how many ways can a committee of 2 boys and 2 girls be formed? Solution: 2 boys can be selected out of 6 in6C2ways. 2 girls can be selected out of 5 in5C2ways. So the selection can be made in6C2x5C2ways. (Product Rule: and stands for multiplication)
Example 10: In a class there are 6 boys and 5 girls. A committee of 4 is to be selected such that it contains at least 1 boy and 1 girl. Solution: There are 3 different possibilities now- i. 1 boy and 3 girls ii. 2 boys and 2 girls iii. 3 boys and 1 girl In the 1st possibility, total number of combinations = 6C1x5C3 In the 2nd possibility, total number of combinations = 6C2x5C2 In the 3rd possibility, total number of combinations = 6C3x5C1 But only one of the above possibilities will occur; 1st OR 2nd OR 3rd. So the total number of required combinations is 6C1x5C3+ 6C2x5C2+6C3x5C1
Some Important Results on Combinations: nCr=nCn-r nC0=nCn= 1 nCr+nCr-1=n+1Cr IfnCp=nCq, then p = q or p + q = n (p,q W) (0 r n)
Restricted Combination: The number of combinations of n different things taken r at a time subject to restriction that p particular things - i) will never occur =n-pCr ii) will always occur =n-pCr-p Number of ways of selecting one or more things from a group of n distinct things =nC1+nC2+nC3+ + nCn= 2n 1 . Number of ways of selecting zero or more things from a group of n distinct things =nC0+nC1+nC2+nC3+ + nCn= 2n
7. Grouping and Distribution This is a very important concept of permutation and combination where some higher order fundamentals of permutation and combination is involved the reason for reserving this topic for the end.
What is the difference between grouping and distribution? To distribute something, first grouping is done. Only after you have made groups of some objects, you might want to distribute these groups in various places. For example, after you made groups of some toys, you might want to distribute these groups among some children. Or, after dividing some number of toffees into groups, you might want to distribute these groups into boxes. Just as the objects that we group can be similar or dissimilar, so can the places that we assign these groups to be similar or dissimilar.
While distributing groups, we need to keep one rule in mind: We permute the groups only if these places for distribution are dissimilar, otherwise not. Say, we have 2 items- X and Y and I have to split them into two groups. There is only one way of doing it X goes in one group and Y in the other. However, if I have to distribute among 2 people A and B, then these 2 groups can be permuted in 2! ways.
Division of dissimilar items into groups of EQUAL SIZE Let s take a very simple example. In how many ways can you divide 4 different things (say A, B, C and D) into two groups having two things each? You would like to say that we select two things out of the four and two would be left behind, i.e.4C2= 6 ways. But are there really 6 ways? Take a look. We can divide four things, A, B, C and D into two groups of two in the following ways: AB CD AC BD AD BC
You can keep trying but there is no fourth way to do it. So where have the remaining 3 ways calculated through 4C2= 6 disappear? If you look carefully, there was an overlap. When we select 2 things out of 4, we can do it in 6 ways AB, AC, AD, CD, BD and BC but when we select the first three groups, the last three get automatically selected without having to select them separately and vice- versa. So when we select AB, CD is automatically selected and vice-versa. .
This overlap will manifold itself if we increase the number of items further So be very careful not to apply the usual combinations formula whenever we have to divide into groups of equal size. However, if the groups contain unequal number of things, then our earlier method of using combinations formula for selection will be valid as will be discussed in the next section.
Let me now increase the objects to 5. How would you divide these 5 distinct (dissimilar) objects into groups of 2, 2 and 1? The single object can be chosen in5C1= 5 ways. The rest of the 4 objects can be divided into two equal groups in 3 ways as explained above. Therefore, total number of ways = 5 x 3 = 15. The number of ways in which mn different things can be DIVIDED equally into m groups, each group containing n things = (mn)!/(n!)mx 1/m! The number of ways in which mn different things can be DISTRIBUTED equally into m groups, each group containing n things = (mn)! / (n!)m Note: In the distribution, order is important hence the divisible things can be arranged in m! ways since things are divided into m groups.
Division of dissimilar items into groups of UNEQUAL SIZE Say we have k things and we have to divide them into 2 groups containing m and n things respectively such that m+n =k, then this can be done in k!/m!.n! ways. This is because m things can be selected out of k things inkCmways and when m things are taken, n things are left to form the other group of n things which can only be done in nCn=1 way. Hence the required number of ways iskCm=m+nCm= (m+n)!/(m+n-n)!.n! = k!/m!.n!.
We can extend the same concept for increased number of groups as long as the number of items in all the groups add up to the total i.e. n. The number of ways in which n distinct things can be DIVIDED into R unequal groups containing a1, a2, a3, , aR things (different number of things in each group and the groups are not distinct) =nCa1 (n-a1)Ca2 (n-a1-a2- .-a(r-1))CaR =n! / a1! a2! a3! .aR! (here a1 + a2 + a3 + + aR = n)
