Arranging and Choosing

Defining Terms

In the previous post, Down for the Count, we started a series on counting principles. We looked at the multiplication and addition principles of counting and I promised that, in this post, we would look at permutations and combinations, as well as the relationship between combinations and the binomial coefficients. So, what do these strange words mean?

A permutation is an arrangement. Hence, if I have three objects, A, B, and C, I could arrange them as ABC, ACB, BAC, BCA, CAB, and CBA. Each of these, while containing each of the objects, represents a different ordering of the object and, hence, a different permutation. Now, suppose I have to choose two out of the three objects. I could choose A followed by B or B followed by A. But in both cases I have chosen A and B. What is end up with, in other words, does not depend, in this case, on the order in which I chose the objects. Both of them represent the same combination of A and B. Hence, if the order is important, we call it a permutation. And if order is unimportant, we call it a combination.

The term ‘binomial coefficient’ is a little more difficult to explain. Consider the expression a + b. Since there are two terms, a and b, this expression is called a binomial. Now, consider the expression (a + b)ⁿ. We know that this means the expression a + b is multiplied by itself n times. For example, (a + b)² = a² + 2ab + b². The coefficients of the terms are 1, 2, and 1. Since these are obtained by expanding the power of the binomial, they are called ‘binomial coefficients’. Similarly, the binomial coefficients of (a + b)³ are 1, 3, 3, and 1, while those of (a + b)⁴ are 1, 4, 6, 4, and 1.

Enumerating Permutations

Suppose I have two distinct objects, A and B. I need to place them in some order. I can choose either A or B to occupy the first position. Hence, for the first position, I have 2 options to choose from. Once I do this, I am left with the second object and am forced to place it in the second position. This means that I have 2 × 1 = 2 ways of arranging A and B, namely AB or BA.

Now, if I have three objects A, B, and C, I have 3 options for the first position. Once I have placed that object, I am left with 2 objects, which can be arranged, as we have seen in the previous paragraph, in 2 ways. Since I have to arrange all three objects, I use the multiplication principle and conclude that there are 3 × (2 × 1) = 6 ways of arranging A, B, and C. These have already been listed earlier.

Now, if I have four objects A, B, C, and D, I have 4 options for the first position. Once I have placed that object, I am left with 3 objects, which can be arranged, as we have just seen, in 6 ways. Against, using the multiplication principle, we can conclude that there are 4 × (3 × 2 × 1) = 24 ways of arranging A, B, C, and D. These are ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, and DCBA.

We can see that, if we proceed this way, the number of ways of arranging 5 objects would be 5 × 4 × 3 × 2 × 1 = 120 ways. We can generalize this and conclude that, given n distinct objects, the number of ways of permuting all of them would be

Now, suppose we do not wish to arrange all the objects, but only r of the n available objects. We can obtain the following table.

The first row in red contains the position numbers. The second row indicates the number of options available for that position. Note that the third row is simply the sum of the items in the preceding two rows, which all happen to be n + 1. It follows then that the number of ways of permuting r out of n items is

This is a cumbersome formula. However, we can make it simpler as follows

We can use this formula quite easily now. For example, if we wish to arrange 9 out of 15 distinct objects, then we number of permutations is

The answer of 1,816,214,000 should also give a reason why, in many cases, we simply prefer to write it in short form as ¹⁵P₉. The large numbers are due to the fact that the factorial (n!) grows at a remarkably fast pace. The table below gives a comparison of the growth of various common functions.

As can be seen, after a relatively slow start, the factorial function just balloons up. It will eventually grow faster than any exponential function because, for any function y = a^x, for values of n > a, the multipliers for n! will be greater than the multipliers for a^x, which is a. As the table above shows, 25! > 10²⁵. If we had 25 distinct objects and wish to arrange all of them, we would have 15 septillion, 511 sextillion, 210 quintillion, 43 quadrillion, 330, trillion, 985 billion, 984 million arrangements. Just to give you an idea of how large this number is, if you started at the big bang, forming one arrangement every 1 second for the 14 billion years of the life of the universe so far, you would need more than 35 million such universes before you were able to finish every arrangement!

Enumerating Combinations

Anyway, there are times when the order of objects does not matter. For example, if we are selecting a 3-member committee from person A, B, C, D, and E, it does not matter if we chose them in the order DBE or BED, etc. Only the final members selected would matter. Now, recall that permuting 3 out of 5 objects can be done in ⁵P₃ ways. However, this represents all the permutations of the three objects selected. Hence, for the set {B, E, D} we have 3! ways of permuting them (i.e. BED, BDE, DBE, DEB, EBD, and EDB), all of which constitute the same selection of the set {B, E, D}. In other words, if we are only concerned about the objects selected and not the order in which they are selected, then ⁵P₃ represents an ‘over counting’ by a factor of 3!. This means that the number of ways of selecting 3 objects from 5 objects would be

We can extend this to a more general case. Given n distinct objects, we can arrange r of them in ⁿP_r ways. However, the r objects can be permuted among themselves in r! ways, all of which represent the same selection. Hence, ⁿP_r represents an ‘over counting’ by a factor of r!. This gives the number of ways of selecting r out of n distinct objects to be

Now, we can see that, given n objects to choose from, we can choose anywhere from 0 of the objects to all of the objects. However, if we put r = 0 or r = n in the above formula, we get

However, common sense tells us that there is only 1 way to choose none or all the n objects. Because of this 0! is defined to be equal to 1.

Now, if we tabulated the values of ⁿC_r, we would get a table as follows.

The Binomial Coefficients and Pascal’s Triangle

We can also prepare the first 8 rows of Pascal’s triangle and obtain

We can see that the values of ⁿC_r match the elements of the r^th row of Pascal’s triangle. Why is this?

Consider the expression (a + b)ⁿ. As mentioned earlier, when we expand this, we are multiplying a + b by itself n times. So we have

where there are n sets of parentheses. Now, to complete the multiplication, we need to multiply each element from each set of parentheses by each element in every other set of parentheses. When we get to a particular binomial, we have to decide whether to choose a or to choose b. We cannot choose both, nor can we choose neither. In the end, we will multiply n elements, one from each set of parentheses. Hence, the power of every such product will be n, distributed between the power of a and the power of b. Hence, if the power of a is r, the power of b will be n – r, yielding terms that have a^rb^{n – r}. However, this means that we have to choose r sets of parentheses to contribute the a, thereby making the other n – r sets of parentheses to contribute the b. Hence, we have to ask, “In how many ways can we choose r sets of parentheses out of n?” Since this is obviously ⁿC_r, we can see why these combination values show up as the binomial coefficients. But why do they show up in Pascal’s triangle?

Psacal’s triangle begins with the top row containing two ‘1’s. Each subsequent row is built by starting and ending with a ‘1’ and obtaining the middle values by adding the two elements above it in the previous row. Hence, the second row starts and ends with ‘1’, with the middle ‘2’ being the sum of ‘1’ and ‘1’ from the first row, giving 1 2 1. The third row starts and ends with ‘1’, with the middle values of ‘3’ being the sum of 1 and 2 and the sum of 2 and 1 respectively, giving 1 3 3 1.

We can see how this happens. We can write

Now, to get the term with a^rb^{n – r}, we need to either select a from the first parentheses and the a^{r – 1}b^{n – r} term from the second parentheses or select b from the first parentheses and the a^rb^{n – r – 1} term from the second parentheses. However, both a^{r – 1}b^{n – r} and a^rb^{n – r – 1} are terms from the (n – 1)^th row of Pascal’s triangle, that is the preceding row.

Moreover, the term with a^{r – 1}b^{n – r} is the r^th element of the (n – 1)^th row, while the term with a^rb^{n – r – 1} is the (r + 1)^th element of the (n – 1)^th row. And the term with a^rb^{n – r} is the (r + 1)^th element of the n^th row.

But this means that the (r + 1)^th element of the n^th row is the sum of the r^th element of the (n – 1)^th row and the (r + 1)^th element of the (n – 1)^th row, which is exactly how each subsequent row of Pascal’s triangle is built. We can put this in terms of combinations and write

Since the above equation relating binomial coefficients indicates the way the elements of Pascal’s triangle are obtained, it is clear why the two are identical.

Making it Count

So far we have learned how to determine the number of permutations of r out of n distinct objects as well as the number of combinations of r out of n distinct objects. We have also seen how the binomial coefficients relate to the elements of Pascal’s triangle. We could have proved the final relation using algebra as below.

However, the algebra does not give us any special insight, which is what we need. We did get some insight when we showed why Pascal’s triangle has elements that are the same as the binomial coefficients and when we showed why the binomial coefficients show how Pascal’s triangle is built up. But we have only just started our journey of learning how to count.

In this post, we have considered permutations and combinations of distinct objects in a row. What if some of the objects are not distinct? What if the objects are not in a row, but in a circle? What if we have some restrictions, like two objects cannot be placed side by side or that two objects must always be placed side by side? How do we manage to use the basic counting principles to determine how to proceed counting in these cases? We will turn to that in the next post. Till then, permute your life to make every moment count.