Permutations and Combinations is considered by some students as one of the toughest topics primarily because each problem that they encounter is different, requires the application of one’s reasoning skills and doesn’t fit into a small framework of generalizations and formulae, like other topics in mathematics. Also, the concepts covered in this particular topic is widely used to solve problems in another important topic namely probability. Students can definitely expect a couple of questions from probability in most of the management entrance exams because probability is one of the areas of significant importance in an MBA course.
Fundamental rule of counting
The entire science of permutations & combinations is based on the fundamental principle of counting and hence it is very important that we understand the principle thoroughly before proceeding to define permutations and combinations.
Let us take the example of tossing a coin thrice. Each toss results in one of two possible outcomes: heads or tails. For each possible outcome of the first toss, there are two possible outcomes of the second toss. So after the second toss, there are in all four possible outcomes (2×2=4). For each of the four possible outcomes of the first and second tosses, there are two possible outcomes of the third toss. So after the third toss, there are in all eight possible outcomes (2×2×2=8).
Fundamental rule of counting generalizes the special case we just saw with the help of the above example. If an event or a trial has ‘m’ outcomes and for every outcome of the previous event, a second event has ‘n’ outcomes, then the number of different ways by which both events can be conducted will be the product of m and n.
Hence, the number of ways in which two operations can be performed together = m x n. This is a very important principle which forms the foundation for permutations and combinations.
Permutations can also be termed as ordered choices or arrangements. Hence, each of the arrangements that can be made by selecting ‘r’ things out of ‘n’ things can be termed as a permutation. In permutations, the order in which the items are arranged is very important.
Suppose we are given a collection of five distinct items. How many ways are there of ordering three of them? We can think of this as a sequence of three choices, each of which results in the selection of one of the remaining things. For the first choice, there are five possible outcomes. For the second choice, there will be four possible outcomes because one item has already been chosen. We don’t know what the possible outcomes are because they depend on the outcome of the first selection, but regardless of which item was picked first, four items remain as possibilities for the second choice. Similarly, three items will remain as possible third choices.
By the Fundamental Rule of Counting, the total number of possible sequences of choices is 5×4×3 = 60 sequences. Each sequence is called a permutation of the five items taken 3 things at a time. A point to be noted here is that though the 3 items selected out of 5 might remain the same, they can still be arranged in 6 ways amongst themselves namely abc, acb, bac, cab, cba and bca, if the items are assumed as a, b and c. Hence, the order in which the items are arranged also gains significance in the case of permutations.
The number of permutations of ‘n’ things taken ‘r’ at a time is denoted by the notation nPr. To derive a formula for permutations, we need to revisit the fundamental principle of counting. By the Fundamental Rule of Counting, in ordering n things, there are n choices for the first, (n-1) choices for the second, etc., so the total number of ways of ordering a total of n things is n × (n-1) × (n-2) × . . . 3 × 2 × 1. This product, n × (n-1) × (n-2) × . . . 3 × 2 × 1, is written as n!, and is pronounced “n factorial.” (By convention, 0! = 1) This is when we are trying to arrange all ‘n’ things.
More generally, suppose we wanted to arrange only r of n things in some order. There are n choices for the first item, (n-1) choices for the second item, and so on, down to (n - r + 1) choices for the rth item. By the fundamental rule of counting nPr , the total number of permutations (orderings) of r out of n things, is:
Note that in all the cases discussed above, each item has been considered distinct and unique. If the items are not distinct, then the number of permutations might change. This case will be discussed in the later stages of the chapter.
Combinations can also be termed as selections. Hence, each of the selection of ‘r’ items made out of a set of ‘n’ items is called a combination. In combinations, the order in which items are arranged is not important.
Suppose there are 20 students in a class and we need to select one pair of students from the 20 students for a scholarship. In this case, the order of the students in the pair is not important as they will anyway be given the same scholarship. Hence, this will be a combination problem. Compare this with selection of 2 students, first will be given 100% scholarship and second will be given 50%. Now, the order of the selected students becomes important since that will determine the amount of scholarship and hence, it will be a permutation problem.
Now, to solve the above problem, we need to go back to the fundamental principle of counting. Now, the student for the first scholarship slot can be selected in 20 ways and for the next slot in 19 ways, since one student is already selected. Hence, the total number of ways will be 20 x 19 = 380 ways but we are double counting each pair in this case because the order in which they are selected is not significant in this case. That is, let’s assume that ‘a’ and ‘b’ are two out of the twenty students. Now, in the 380 ways mentioned above, the selection of these two students has been counted twice as (a, b) and (b, a). Hence, to remove this irregularity, we need to divide the number by 2 in order to get the correct number of combinations. Hence, the total number of ways in which they can be selected is 380/2 which is equal to 190. This is also called the number of combinations of 20 students taken 2 at a time.
Extending the above problem, if we are to select 3 students from the 20 for a scholarship, we can count them in 20P3 ways but we need to remove the duplication caused because of arrangement since each group selected will be arranged in 3! ways. Hence, the number of combinations will be 20P3 / 3!
To generalize it, number of combinations of ‘n’ things taken ‘r’ at a time can be given as,
Note that in all the cases discussed above, each item has been considered distinct and unique. If the items are not distinct, then the number of combinations might change.
Since the order of selecting the items is not important in combinations, when one is selecting ‘r’ items out of a group of ‘n’ items, the number of ways of doing that will be the same as selecting ‘n-r’ items from that group of ‘n’ items. For example, when I need to select two people out of say a group of 5 nominees for a particular award, the number of ways in which I can select 2 nominees for the award is going to be the same as the number of ways in which I can reject 3 nominees. That is, whenever I have 2 selections for the awards, I also have 3 rejections for the same.
This property can be put in mathematical language as follows: