| PolarSPARC |
Introduction to Permutations & Combinations
| Bhaskar S | 07/10/2015 |
Factorial
A Factorial of a number N, which is represented as N!, is defined as the product of all the numbers from 1 through N.
N! = 1 * 2 * 3 * .... * N
| Example-1 | What is the value for factorial 5 ? |
|---|---|
|
5! = 5 * 4 * 3 * 2 * 1 5! = 120 |
|
The Factorial of 0 (zero) is 1.
Permutations
A Permutation is the arrangement of elements from a set in an order.
Let us look at a few examples to understand the concept of Permutations.
| Example-2 | There are 3 people A, B, and C who run a race to win the 1st, 2nd, and 3rd prizes. What are the total no. of Permutations for the 1st, 2nd, and 3rd spots ? |
|---|---|
|
The 1st spot can be won by any of the 3 runners - A, B, C. If A wins the 1st spot, then the 2nd spot can be won by any of the remaining 2 runners - B, C. If B wins the 2nd spot, then C wins the 3rd spot. If A wins the 1st spot and C wins the 2nd spot, then B wins the 3rd spot. If B wins the 1st spot, then the 2nd spot can be won by any of the remaining 2 runners - A, C. If A wins the 2nd spot, then C wins the 3rd spot. If B wins the 1st spot and C wins the 2nd spot, then A wins the 3rd spot. If C wins the 1st spot, then the 2nd spot can be won by any of the remaining 2 runners - A, B. If A wins the 2nd spot, then B wins the 3rd spot. If C wins the 1st spot and B wins the 2nd spot, then A wins the 3rd spot. In total, we have 6 Permutations !!! |
|
Put in another way - the 1st spot can be claimed by any of the 3 runners. Once the 1st spot is chosen, the 2nd spot can be claimed by any of the 2 remaining runners. Once the 2nd spot is chosen, there is only 1 remaining runner and they claim the 3rd spot. So, mathematically, it is 3 * 2 * 1, which is nothing but 3! = 6.
In this example, we found the Permutation of 3 elements (A, B, C) taken 3 at a time (1st, 2nd, 3rd).
In general, the Permutations of N elements taken N at a time (represented as \(_{n}P_{n}\) or \(P_{n}^{n}\)) is defined as N!.
Now for an interesting example.
| Example-3 | In how many ways can the letters in the word APPROPRIATE be arranged ? |
|---|---|
|
If we stated that the Permutation of 11 letters from the given word taken 11 at a time is 11!, then we are WRONG !!! The above approach would have been correct if all the letters in the given word were different - but that is not the case. There are 2 letter A's, 3 letter P's, 2 letter R's, 1 letter O, 1 letter I, 1 letter T and 1 letter E. The correct way to compute the Permutations in this case is 11!/(2! * 3! * 2! * 1! * 1! * 1! * 1!) which would be = 1663200. |
|
In general, the Permutations of N elements taken N at a time, where A type of elements are alike, B type of elements are alike, C type of elements are alike, etc., is defined as N!/(A! * B! * C!).
| Example-4 | There are 5 people A, B, C, D, and E who run a race to win the 1st, 2nd, and 3rd prizes. What are the total no.of Permutations for the 1st, 2nd, and 3rd spots ? |
|---|---|
|
The 1st spot can be won by any of the 5 runners - A, B, C, D, E. If A wins the 1st spot, then the 2nd spot can be won by any of the remaining 4 runners - B, C, D, E. If B wins the 2nd spot, then the 3rd spot can be won by any of the remaining 3 runners - C, D, E. If A wins the 1st spot and B wins the 2nd spot, we have the following three outcomes: A, B, C A, B, D A, B, E If A wins the 1st spot and C wins the 2nd spot, we have the following three outcomes: A, C, B A, C, D A, C, E If A wins the 1st spot and D wins the 2nd spot, we have the following three outcomes: A, D, B A, D, C A, D, E If A wins the 1st spot and E wins the 2nd spot, we have the following three outcomes: A, E, B A, E, C A, E, D Following this approach, if B wins the 1st spot, we have the following twelve outcomes: B, A, C B, A, D B, A, E B, C, A B, C, D B, C, E B, D, A B, D, C B, D, E B, E, A B, E, C B, E, D Next, if C wins the 1st spot, we will have twelve outcomes (we will skip the Permutations for the sake of brevity). Next, if D wins the 1st spot, we will have twelve outcomes (we will skip the Permutations for the sake of brevity). Finally, if E wins the 1st spot, we will have twelve outcomes (we will skip the Permutations for the sake of brevity). In total, we have 12 + 12 + 12 + 12 + 12 = 60 Permutations !!! |
|
Put in another way - the 1st spot can be claimed by any of the 5 runners. Once the 1st spot is chosen, the 2nd spot can be claimed by any of the 4 remaining runners. Once the 2nd spot is chosen, the final 3rd spot can be claimed by any of the remaining 3 runners. So, mathematically, it is 5 * 4 * 3, which is = 60.
In this example, we found the Permutation of 5 elements (A, B, C, D, E) taken 3 at a time (1st, 2nd, 3rd).
In general, the Permutations of N elements taken R at a time (represented as \(_{n}P_{r}\) or \(P_{r}^{n}\)) is defined as N!/(N-R)!.
| Example-5 | How many 3-digit secret codes can be created such that no number (0 to 9) is repeated ? |
|---|---|
|
The 1st digit can be any of the 10 numbers (0 through 9). Once the 1st digit is chosen, that number cannot be used any more and we will have 9 remaining numbers to chose from. The 2nd digit can be any of the remaining 9 numbers. Once the 2nd digit is chosen, that number cannot be used any more and we will have 8 remaining numbers to chose from. The 3rd digit can be any of the remaining 8 numbers. So, the total number of 3-digit Permutations is 10 * 9 * 8, which is 720. |
|
In this example, we found the Permutation of 10 digits (0 through 9) taken 3 at a time with no repetition, which can also be computed using the formula N!/(N-R)!, where N = 10 and R = 3, i.e., 10!/(10-3)! = 10 * 9 * 8 = 720.
Now for an interesting twist to Example-5.
| Example-6 | How many 3-digit secret codes can be created where the numbers (0 to 9) can be repeated ? |
|---|---|
|
The 1st digit can be any of the 10 numbers (0 through 9). Once the 1st digit is chosen, for the 2nd digit we still have 10 digits to choose from since digits can be repeated. The 2nd digit can be any of the 10 numbers (0 through 9). Once the 2nd digit is chosen, for the 3rd digit we still have 10 digits to choose from since digits can be repeated. The 3rd digit can be any of the 10 numbers (0 through 9). So, the total number of 3-digit Permutations is 10 * 10 * 10, which is 1000. |
|
In general, the Permutations of N elements taken R at a time with repetitions is defined as \(N^R\).
Combinations
A Combination is the selection of elements from a set such that the order does not matter.
Let us look at a few examples to understand the concept of Combinations.
| Example-7 | There are 3 people A, B, and C who want to go to a particular movie but have only 2 tickets. What are the total no. of Combinations for picking two people for the movie ? |
|---|---|
|
We can pick A and B to go to the movie. Note that the order does not matter here - [A, B] is the same as [B, A] in this case. We can pick A and C to go to the movie. We can pick B and C to go to the movie. In total, we have 3 Combinations !!! |
|
Let us look at another example for Combinations.
| Example-8 | There are 5 people A, B, C, D, and E in a company from which to choose to go for a conference. Due to financial constraints only 3 people can go. What are the total no. of Combinations for picking three people for the conference ? |
|---|---|
|
The following are the different combinations: A, B, C A, B, D A, B, E A, C, D A, C, E A, D, E B, C, D B, C, E B, D, E B, E, D In total, we have 10 Combinations !!! |
|
In general, the Combinations of N elements taken R at a time (represented as \(_{n}C_{r}\) or \(C_{r}^{n}\)) is defined as N!/(N-R)!R!.
The fundamental difference between Permutations and Combinations is that ARRANGEMENT/ORDER matters in Permutations
Practice Problems
| Problem-1 | There are 35 students in a class. What is the least number of questions to choose so that each student gets the same set of questions but appears in a different order in their test paper ? |
|---|---|
|
This problem clearly indicates arrangement/order and hence is a Permutation problem. Let us start with 2 questions. This means we will have 2! = 2 * 1 = 2 arrangements. For 3 questions, we will have 3! = 3 * 2 * 1 = 6 arrangements. This is clearly not enough as we have 35 students in the class. Continuing, for 4 questions, we will have 4! = 4 * 3 * 2 * 1 = 24 arrangements. Still not enough. With 5 questions, we will have 5! = 5 * 4 * 3 * 2 * 1 = 120 arrangements. This is more than enough to cover the 35 students. So the least number of questions we need to choose so it is different for each student is 5. |
|
| Problem-2 | In how many ways can the letters of the word MATHEMATICS be arranged such that all the vowels in the word always appear together ? |
|---|---|
|
This problem clearly indicates arrangement and hence is a Permutation problem. The letters A, E, A, and I are all the vowels in the given word. If the always have to appear together, they can be logically treated as one letter AEAI. That said, we will have the letters M, T, H, M, T, C, S, and the logical letter AEAI. Also, we have 2 letter M's, 2 letter T's, 1 letter H, 1 letter C, 1 letter S, and 1 logical letter AEAI. Taking the hint from Example-3, the number of arrangements is 8!/(2! * 2! * 1! * 1! * 1! * 1!) = 10080 ways. The logical letter AEAI itself has 2 letter A's, 1 letter E, and 1 letter I. It can be arranged in 4!/(2! * 1! * 1!) = 12 ways. The total no. of ways in which the given words can be arranged to satisfy the constraints = 10080 * 12 = 120960. |
|
| Problem-3 | From a group of 6 men and 4 women in a department, 3 folks need to be selected for a training. In how many different ways can they be selected such that at least one woman is included ? |
|---|---|
|
This problem clearly indicates selection and hence is a Combination problem. The different selections could be as follows: 1 woman and 2 men, or 2 women and 1 man, or 3 women. This translates to: (\(C_{1}^{4}\) * \(C_{2}^{6}\)) + (\(C_{2}^{4}\) * \(C_{1}^{6}\)) + \(C_{3}^{4}\) = (4!/(3! * 1!) * 6!/(4! * 2!) + (4!/(2! * 2!) * 6!/(5! * 1!) + 4!/(1! * 3!) = (4 * 15) + (6 * 6) + 4 The total no. of ways in which the folks can be selected for the training 60 + 36 + 4 = 100. |
|
| Problem-4 | A box contains 3 Black balls, 4 Green balls, and 5 Red balls. In how many ways can we draw 3 balls from the box, such that it includes at least one Black ball ? |
|---|---|
|
This problem clearly indicates selection and hence is a Combination problem. The different selections could be as follows: 1 Black and 2 (Green or Red), or 2 Black and 1 (Green or Red), or 3 Black. There are totally 9 Green or Red balls. This translates to: (\(C_{1}^{3}\) * \(C_{2}^{9}\)) + (\(C_{2}^{3}\) * \(C_{1}^{9}\)) + \(C_{3}^{3}\) = (3!/(2! * 1!) * 9!/(7! * 2!) + (3!/(1! * 2!) * 9!/(8! * 1!) + 3!/(0! * 3!) = (3 * 36) + (3 * 9) + 1 The total no. of ways in which 3 balls can be selected with at least one Black ball is 108 + 27 + 1 = 136. |
|
| Problem-5 | In how many ways can 5 gifts be packed in 3 boxes, if any number of gifts can be packed in the 3 boxes ? |
|---|---|
|
This problem clearly indicates arrangement and hence is a Permutation problem. We can pack the first gift in any of the 3 boxes. This means we have 3 choices. The second gift can again be packed in any of the 3 boxes since a box can contain any number of gifts. Again we have 3 choices. Continuing this approach for the third, fourth and fifth gift, we will have 3 * 3 * 3 * 3 = 35. The total no. of ways in which we can pack the 5 gifts in the 3 boxes is 243. |
|