Show
In this article you’ll learn about Permutation and Combination problems: Definition, formulas, solved examples and a quiz with practice questions. PermutationsDefinition
For example: The different ways in which the alphabets A, B and C can be grouped together, taken all at a time, are ABC, ACB, BCA, CBA, CAB, BAC. Note that ABC and CBA are not same as the order of arrangement is different. The same rule applies while solving any problem in Permutations. The number of ways in which n things can be arranged, taken all at a time, nPn = n!, called ‘n factorial.’ Factorial FormulaFactorial of a number n is defined as the product of all the numbers from n to 1. For example, the factorial of 5, 5! = 5*4*3*2*1 = 120. Therefore, the number of ways in which the 3 letters can be arranged, taken all a time, is 3! = 3*2*1 = 6 ways. Number of permutations of n things, taken r at a time, denoted by: For example: The different ways in which the 3 letters, taken 2 at a time, can be arranged is 3!/(3-2)! = 3!/1! = 6 ways. Important Permutation Formulas1! = 1 0! = 1 Let us take a look at some examples: Problem 1: Find the number of words, with or without meaning, that can be formed with the letters of the word ‘CHAIR’. Solution: ‘CHAIR’ contains 5 letters. Therefore, the number of words that can be formed with these 5 letters = 5! = 5*4*3*2*1 = 120. Solution: The word ‘INDIA’ contains 5 letters and ‘I’ comes twice. When a letter occurs more than once in a word, we divide the factorial of the number of all letters in the word by the number of occurrences of each letter. Therefore, the number of words formed by ‘INDIA’ = 5!/2! = 60. Solution: The word ‘SWIMMING contains 8 letters. Of which, I occurs twice and M occurs twice. Therefore, the number of words formed by this word = 8! / (2!*2!) = 10080. Solution: The word ‘SUPER’ contains 5 letters. In order to find the number of permutations that can be formed where the two vowels U and E come together. In these cases, we group the letters that should come together and consider that group as one letter. So, the letters are S,P,R, (UE). Now the number of words are 4. Therefore, the number of ways in which 4 letters can be arranged is 4! In U and E, the number of ways in which U and E can be arranged is 2! Hence, the total number of ways in which the letters of the ‘SUPER’ can be arranged such that vowels are always together are 4! * 2! = 48 ways. Solution: The word ‘BUTTER’ contains 6 letters. The letters U and E should always come together. So the letters are B, T, T, R, (UE). Number of ways in which the letters above can be arranged = 5!/2! = 60 (since the letter ‘T’ is repeated twice). Number of ways in which U and E can be arranged = 2! = 2 ways Therefore, total number of permutations possible = 60*2 = 120 ways. Problem 6: Find the number of permutations of the letters of the word ‘REMAINS’ such that the vowels always occur in odd places. Solution: The word ‘REMAINS’ has 7 letters. There are 4 consonants and 3 vowels in it. Writing in the following way makes it easier to solve these type of questions. (1) (2) (3) (4) (5) (6) (7) No. of ways 3 vowels can occur in 4 different places = 4P3 = 24 ways. After 3 vowels take 3 places, no. of ways 4 consonants can take 4 places = 4P4 = 4! = 24 ways. Therefore, total number of permutations possible = 24*24 = 576 ways. CombinationsThe different selections possible from a collection of items are called combinations. For example: The different selections possible from the alphabets A, B, C, taken 2 at a time, are AB, BC and CA. It does not matter whether we select A after B or B after A. The order of selection is not important in combinations. To find the number of combinations possible from a given group of items n, taken r at a time, the formula, denoted by nCr is nCr = n! / [r! * (n-r)!] For example, verifying the above example, the different selections possible from the alphabets A, B, C, taken two at a time are 3C2 = 3! / (2! * (3-2)!) = 3 possible selections (i.e., AB, BC, CA)Important Combination formulasnCn = 1 nC0 = 1 nC1 = n nCr = nC(n-r) The number of selections possible with A, B, C, taken all at a time is 3C3 = 1 (i.e. ABC) Solved examples of CombinationLet us take a look at some examples to understand how Combinations work: Solution: No. of ways 1 man can be selected from a group of 3 men = 3C1 = 3! / 1!*(3-1)! = 3 ways. No. of ways 3 women can be selected from a group of 4 women = 4C3 = 4! / (3!*1!) = 4 ways. Problem 2: Among a set of 5 black balls and 3 red balls, how many selections of 5 balls can be made such that at least 3 of them are black balls. Solution: Selecting at least 3 black balls from a set of 5 black balls in a total selection of 5 balls can be 3 B and 2 R 4 B and 1 R and 5 B and 0 R balls. Therefore, our solution expression looks like this. Solution: If a number is divisible by 10, its units place should contain a 0. After 0 is placed in the units place, the tens place can be filled with any of the other 5 digits. Selecting one digit out of 5 digits can be done in 5C1 = 5 ways. After filling the tens place, we are left with 4 digits. Selecting 1 digit out of 4 digits can be done in 4C1 = 4 ways. After filling the hundreds place, the thousands place can be filled in 3C1 = 3 ways. Therefore, the total combinations possible = 5*4*3 = 60. Permutations and Combinations QuizTry these practice problems. Problem 1: Click here
Solve the following. i) 30P2 A. 870, 435 B. 435, 870 C. 870, 470 D. 435, 835 Answer 1: Click here
A Explanation: 30P2 = 30! / 28! = 30*29*28! / 28! = 30*29 = 870 30C2 = 30! / (2!*28!) = 435 Problem 2: Click here
How many different possible permutations can be made from the word ‘BULLET’ such that the vowels are never together? A. 360 B. 120 C. 480 D. 240 Answer 2: Click here
D. Explanation: The word ‘BULLET’ contains 6 letters of which 1 letter occurs twice = 6! / 2! = 360 No. of permutations possible with vowels always together = 5! * 2! / 2! = 120 No. of permutations possible with vowels never together = 360-120 = 240 Problem 3: Click here
In how many ways can a selection of 3 men and 2 women can be made from a group of 5 men and 5 women ? A. 10 B. 20 C. 30 D. 100 Answer 3: Click here
D. Explanation: 5C3 * 5C2 = 100 In this section you will learn to In this section we will address the following two problems.
The first problem comes under the category of Circular Permutations, and the second under Permutations with Similar Elements.
Suppose we have three people named A, B, and C. We have already determined that they can be seated in a straight line in 3! or 6 ways. Our next problem is to see how many ways these people can be seated in a circle. We draw a diagram. It happens that there are only two ways we can seat three people in a circle, relative to each other’s positions. This kind of permutation is called a circular permutation. In such cases, no matter where the first person sits, the permutation is not affected. Each person can shift as many places as they like, and the permutation will not be changed. We are interested in the position of each person in relation to the others. Imagine the people on a merry-go-round; the rotation of the permutation does not generate a new permutation. So in circular permutations, the first person is considered a place holder, and where he sits does not matter.
The number of permutations of \(n\) elements in a circle is \((n-1)!\)
In how many different ways can five people be seated at a circular table? Solution We have already determined that the first person is just a place holder. Therefore, there is only one choice for the first spot. We have So the answer is 24.
In how many ways can four couples be seated at a round table if the men and women want to sit alternately? Solution We again emphasize that the first person can sit anywhere without affecting the permutation. So there is only one choice for the first spot. Suppose a man sat down first. The chair next to it must belong to a woman, and there are 4 choices. The next chair belongs to a man, so there are three choices and so on. We list the choices below. So the answer is 144.
Let us determine the number of distinguishable permutations of the letters ELEMENT. Suppose we make all the letters different by labeling the letters as follows. \[E_1LE_2ME_3NT \nonumber\] Since all the letters are now different, there are 7! different permutations. Let us now look at one such permutation, say \[LE_1ME_2NE_3T \nonumber\] Suppose we form new permutations from this arrangement by only moving the E's. Clearly, there are 3! or 6 such arrangements. We list them below. \begin{aligned} &\mathrm{LE}_{1} \mathrm{ME}_{2} \mathrm{NE}_{3} \\ &\mathrm{LE}_{1} \mathrm{ME}_{3} \mathrm{NE}_{2} \\ &\mathrm{LE}_{2} \mathrm{ME}_{1} \mathrm{NE}_{3} \mathrm{T} \\ &\mathrm{LE}_{2} \mathrm{ME}_{3} \mathrm{NE}_{1} \mathrm{T} \\ &\mathrm{LE}_{3} \mathrm{ME}_{2} \mathrm{NE}_{1} \mathrm{T} \\ & \mathrm{LE}_{3} \mathrm{ME}_{I} \mathrm{NE}_{2} \mathrm{T} \end{aligned} Because the E's are not different, there is only one arrangement LEMENET and not six. This is true for every permutation. Let us suppose there are n different permutations of the letters ELEMENT. Then there are \(n \cdot 3!\) permutations of the letters \(E_1LE_2ME_3NT\). But we know there are 7! permutations of the letters \(E_1LE_2ME_3NT\). Therefore, \(n \cdot 3! = 7!\) Or \(n = \frac{7!}{3!}\). This gives us the method we are looking for.
The number of permutations of n elements taken \(n\) at a time, with \(r_1\) elements of one kind, \(r_2\) elements of another kind, and so on, is \[\frac{n !}{r_{1} ! r_{2} ! \ldots r_{k} !} \]
Find the number of different permutations of the letters of the word MISSISSIPPI. Solution The word MISSISSIPPI has 11 letters. If the letters were all different there would have been 11! different permutations. But MISSISSIPPI has 4 S's, 4 I's, and 2 P's that are alike. So the answer is \(\frac{11!}{4!4!2!} = 34,650\).
If a coin is tossed six times, how many different outcomes consisting of 4 heads and 2 tails are there? Solution Again, we have permutations with similar elements. We are looking for permutations for the letters HHHHTT. The answer is \(\frac{6!}{4!2!} = 15\).
In how many different ways can 4 nickels, 3 dimes, and 2 quarters be arranged in a row? Solution Assuming that all nickels are similar, all dimes are similar, and all quarters are similar, we have permutations with similar elements. Therefore, the answer is \[\frac{9 !}{4 ! 3 ! 2 !}=1260 \nonumber\]
A stock broker wants to assign 20 new clients equally to 4 of its salespeople. In how many different ways can this be done? Solution This means that each sales person gets 5 clients. The problem can be thought of as an ordered partitions problem. In that case, using the formula we get \[\frac{20 !}{5 ! 5 ! 5 ! 5 !}=11,732,745,024 \nonumber\]
A shopping mall has a straight row of 5 flagpoles at its main entrance plaza. It has 3 identical green flags and 2 identical yellow flags. How many distinct arrangements of flags on the flagpoles are possible? Solution The problem can be thought of as distinct permutations of the letters GGGYY; that is arrangements of 5 letters, where 3 letters are similar, and the remaining 2 letters are similar: \[ \frac{5 !}{3 ! 2 !} = 10 \nonumber\] Just to provide a little more insight into the solution, we list all 10 distinct permutations: GGGYY, GGYGY, GGYYG, GYGGY, GYGYG, GYYGG, YGGGY, YGGYG, YGYGY, YYGGG We summarize.
1. Circular Permutations The number of permutations of n elements in a circle is \[(n -1)! \nonumber\] 2. Permutations with Similar Elements The number of permutations of n elements taken n at a time, with \(r_1\) elements of one kind, \(r_2\) elements of another kind, and so on, such that \(\mathrm{n}=\mathrm{r}_{1}+\mathrm{r}_{2}+\ldots+\mathrm{r}_{\mathrm{k}}\) is \[\frac{n !}{r_{1} ! r_{2} ! \dots r_{k} !} \nonumber\] This is also referred to as ordered partitions. |