The Fundamental Theorem of Arithmetic

We started a series on counting principles earlier this year. We first considered the most basic principles, namely the multiplication and addition principles. Then we looked at how permutations differ from combinations, considering some basic patterns of both including the elements of Pascal’s triangle. Next, we turned our attention to permutations of special kinds, including circular permutations and permutations of non-distinct objects. Then last week we considered combinatorial arguments and binomial identities. We are now poised to consider some ideas related to factors of numbers. I had thought I would be able to include the technique of partitions also in this post. However, I will tackle that in the next post.

In an earlier post we had looked at the ideas related to factors of numbers. But that was many months ago. So let us start here as though we are addressing these issues for the first time. We begin with the observation that every natural number, except 1, is either a prime number or a composite number. As a reminder, a prime number is one whose factors are only 1 and itself. A number that has a factor other than 1 and itself is said to be a composite number. While it would seem that 1 satisfies the condition for being a prime number, 1 is not considered to be prime. Why is this the case?

The fundamental theorem of arithmetic states that every natural number greater than 1 is either a prime number or can be expressed as a unique product of prime numbers, disregarding the order of the primes. We must admit that this theorem, like many in mathematics, is a kind of after-thought. It was introduced specifically to exclude 1 from the set of primes. And this is because including 1 in the set of primes creates more problems than it solves. This is because 1 is the multiplicative identity element. That is, the product of any number and 1 is the number itself. This means that, if we allow 1 to be defined as a prime number, we could write

Hence, any idea of a unique prime factorization would go into the gutter! However, nothing is gained by defining 1 to be a prime number. Hence, we exclude 1 from the set of primes. What this means is that every natural number greater than 1 can be written with a unique prime factorization, disregarding the order of the primes. For example,

Since multiplication is commutative, the order in which we multiply the prime numbers does not matter.

Number of Factors of N

Let us consider, for example, the number 450. We can determine the factors by using a method like that indicated in the diagram at the start of this post. However, for large numbers this may be an onerous task. However, we can resort to prime factorization and write 450 as

We can see that there are 5 prime factors with two of them being repeated twice. Hence, from what we have learned earlier, there are

ways of permuting these prime factors. However, all of them give the product of 450. Hence, if we disregard the order in which we multiply the prime factors, the prime factorization of 450 is unique and can be written as

Let us consider the factors of 450. They are 1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225, and 450. Hence, 450 has 18 distinct factors. Some of them are odd, like 1, 3, 5, 9, 15, 25, 45, 75, and 225. The others are even, like 2, 6, 10, 18, 30, 50, 90, 150, and 450. We can see that there are 9 factors that are odd and 9 that are even. That is curious because 9 + 9 = 18. Perhaps there is something here.

Let us consider the other prime factors. There are factors that are not divisible by 3, such as 1, 2, 5, 10, 25, and 50. There are factors that are divisible by 3 but not divisible by 9, such as 3, 6, 15, 30, 75, and 150. And there are factors that are divisible by 9, such as 9, 18, 45, 90, 225, and 450. We can see that there are 6 of each such factors and 6 + 6 + 6 = 18. In a similar way, the factors not divisible by 5 are 1, 2, 3, 6, 9, and 18. The factors divisible by 5 but not by 25 are 5, 10, 15, 30, 45, and 90. And the factors divisible by 25 are 25, 50, 75, 150, 225, and 450. Once again, there are 6 of each and 6 + 6 + 6 = 18. Surely there is some significance to this. Perhaps we can get a pattern by considering a number with fewer distinct factors.

Let us consider the number 18. It has 6 distinct factors, namely 1, 2, 3, 6, 9, and 18. Of these, 3 are odd, namely 1, 3, and 9, and 3 are even, namely 2, 6 and 18. Also 2 are not divisible by 3, namely 1 and 2, 2 are divisible by 3, but not by 9, namely 3 and 6, and 2 are divisible by 9, namely 9 and 18. We will now invoke the fact that 1 is the multiplicative identity element and that, for any natural number n, n⁰ = 1. Since the prime factorization of 18 is 2¹3², any factor of 6 can have as its factors 2⁰, giving an odd number, or 2¹, giving an even number. In a similar way, any factor of 18 can have as its factor 3⁰, giving a number not divisible by 3, or 3¹, giving a number divisible by 3, but not by 9, or 3², giving a number divisible by 9. In other words, there. So, since we had 2¹ in the prime factorization of 18, there are 1 + 1 = 2 ways of including 2 in the factor, either exclude it, giving an odd number, or include it, giving an even number. And since we had 3² in the prime factorization of 19, there are 2 + 1 = 3 ways of including 3 in the factor, exclude it completely, giving a number not divisible by 3, include only one 3, giving a number divisible by 3 but not by 9, or include both 3s, giving a number divisible by 9.

Let us see if we can generalize this result. Suppose we have the number N. Suppose its prime factorizations is

Then, the number of distinct factors of N will be

Let us put this to the test. For 18 = 2¹3², p₁ = 2, p₂ = 3, a₁ = 1, and a₂ = 2. According to the result, the number of factors should be (1 + 1)(2 + 1) = 6, which is correct. For 450 = 2¹3²5², p₁ = 2, p₂ = 3, p₃ = 5, a₁ = 1, a₂ = 2, and a₃ = 2. According to the result, the number of factors should be (1 + 1)(2 + 1)(2 + 1) = 18, which is correct.

Sum of Factors of N

Now, let us try to find the sum of the factors of a natural number. Consider the number 18. The sum of its factors will be 1 + 2 + 3 + 6 + 9 + 18 = 39. For the number 450, the sum of the factors is 1 + 2 + 3 + 5 + 6 + 9 + 10 + 15 + 18 + 25 + 30 + 45 + 50 + 75 + 90 + 150 + 225 + 450 = 1209. If we attempt to factorize 39 we get 39 = 3 × 13. Similarly 3 × 13 × 31. The repetition of the 3 and 13 seems interesting.

Let us consider another number, say 6, which has a prime factorization of 2¹3¹. The factors are 1, 2, 3 and 6, which add up to 12, which in turn can be written as 3 × 4. Similarly, the factors of 15, which has a prime factorization of 3¹5¹, are 1, 3, 5, and 15, which add up to 24, which is 4 × 6. Also, the factors of 30, which has a prime factorization of 2¹3¹5¹, are 1, 2, 3, 5, 6, 10, 15, and 30, which add up to 72, which is 3 × 4 × 6. We can see that, when 2¹ appears in the prime factorization, the sum of the factors has 3 as a factor. Similarly, when 3¹ appears in the prime factorization, the sum of the factors has 4 as a factor. And when 5¹ appears in the prime factorization, the sum of the factors has 6 as a factor.

Now let us consider some other examples. These are summarized in the table below.

The results are also color coded. 2¹ links with 3, 2² links with 7, 3¹ links with 4, 3² links with 13, 5¹ links with 6, 5² links with 31, and 7¹ links with 8. Of course, if you are familiar with series of powers of natural numbers, you will recognize that

Hence, it seem as though, for a number like, say 42, the sum of the factors can be written as

We can see how this makes sense. The final expression involving a product of three terms can be expanded as follows:

We can, therefore, reach a generalization as follows for any natural number, N. Suppose the prime factorization of N is

Then the sum of the factors of N will be

Consider the number 12,600 = 2³3²5²7¹. According to the result we have just obtained, the sum of all the factors should be (1 + 2 + 3 + 4 + 5)(1 + 3 + 9)(1 + 5 + 25)(1 + 7) =48,360. This is confirmed here. Of course, we could use the previous result to determine that 12,600 has (3 + 1)(2 + 1)(2 + 1)(1 + 1) = 72 factors.

Using the two results we have obtained we can determine how many factors a number has and the sum of those factors without determining what those factors are. So, for example, if we are given the number 174,636,000 = 2⁵3⁴5³7²11¹, we can determine that it has (5 + 1)(4 + 1)(3 + 1)(2 + 1)(1 + 1) = 720 factors, the sum of which is (1 + 2 + 4 + 8 + 16 + 32)(1 + 3 + 9 + 27 + 81)(1 + 5 + 25 + 125)(1 + 7 + 49)(1 + 11) = 813,404,592. We can observe that the terms in each set of parentheses form a geometric sequence with first term 1, which can easily be summed using the formula

In other words, even with extremely large numbers, we can obtain the number of factors and the sum of factors with a few lines of code in a computer.

Looking Ahead

What we have seen in this post is a way of determining the number of factors of a number and the sum of its factors without having to find all the factors. We do need to determine the prime factorization of the number However, this is a straightforward process. Now, we used the fundamental theorem of arithmetic to help us determine both the number of factors and the sum of the factors. While this may not be a theorem that is explicitly named when we are in school, it is something that we use regularly after learning division and factorization. Hence, we used some relatively simple mathematics that we learned in elementary school to unravel the question of the number and sum of factors. While some of the formalism and symbols used might be beyond what a student in elementary can understand, the arithmetic behind it is something that elementary students can understand. This is especially so if we demonstrate how, while expanding the expression for the sum of factors, we need to choose one term from each set of parentheses without repetition.

In the next post, we will tackle the technique of partitioning. In order to set up the post, I will leave you with a question. Given that x, y, and z are natural numbers, how many solutions exist to the equation x + y + z = 100?

Recapitulation

In this post we continue with the series on Counting Principles. Whereas we devoted the previous post to permutations of special kinds, we will turn our attention today to the matter of combinations. In Arranging and Choosing we saw that the binomial coefficients are related to the elements of Pascal’s triangle. We saw that the process of expanding an expression like (a + b)ⁿ involves multiplying a + b by itself n times. This involves choosing either a or b from each factor. We were, therefore, able to show that the (r + 1)^th element of the n^th row of Pascal’s triangle 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. In symbolic notation,

While we proved this result with algebra, I claimed that the algebraic method, involving pure brute force of algebraic manipulation, did not yield any particular insight. However, we proved the above result using

and arguing from how a particular element on the left side is obtained by adding two terms on the right side. This sort of argumentation does not use algebra. However, the argument in Arranging and Choosing is not technically what is called a ‘combinatorial argument’. So, what is a combinatorial argument? Let us learn with a few examples.

Combinatorial Arguments

Example 1

We begin with the same result we proved earlier. Suppose we have n distinct items and we wish to choose r out of them. This can obviously be done in ⁿC_r ways. Now, let us focus on one particular item (say A) out of the n items. The group of r items that are selected either contains A or does not contain A. If the selection contains A, then we have to choose r – 1 more items from the remaining n – 1 items, which can be done in ^{n – 1}C_{r – 1} ways. If the selection does not contain A, then we still have to choose r items from the remaining n – 1 items, which can be done in ^{n – 1}C_r ways. Since the selections that contain A and do not contain A are mutually exclusive (meaning they have no common members) and exhaustive (meaning that there are no other possibilities), it follows that

As an example, suppose we have to choose 6 items out of 20. This can be done in ²⁰C₆ = 38,760 ways. Now, if one of the items is A, then the selection either contains A or does not contain A. If it contains A, then we have to select 5 more items from the remaining 19 items, which can be done in ¹⁹C₅ = 11,628 ways. If it does not contain A, then we have to select 6 items from the remaining 19 items, which can be done in ¹⁹C₆ = 27,132 ways. It is easy to check that 11,628 + 27,132 = 38,760. This is an example of the addition principle that we dealt with in Down for the Count.

Example 2

Let us consider another result, namely

We proceed as follows. Suppose we have n items and we have to select r of them for some purpose. This obviously can be done in ⁿC_r ways. However, by selecting the r items for the purpose, we automatically create a selection of the remaining n – r items not for that purpose – that is for some other purpose. Selecting n – r items for some other purpose can obviously be done in ⁿC_{n – r} ways. Since the selection of r items automatically creates a selection of the remaining n – r items, the number of ways must be equal. Hence, ⁿC_r = ⁿC_{n – r} .

Example 3

Now let us try to prove

We proceed as follows. Suppose we have n items from which we have to select r items. This can be done in ⁿC_r ways. Now suppose we select k items from the r. This can be done in ^rC_k ways. The two selections can obviously be done in ⁿC_r ^rC_k ways. But we can make these selections in a different way. Let us first select the k items from the original n items. This can be done in ⁿC_k ways. Now we have to select r – k items from the remaining n – k items, which can be done in ^{n – k}C_{r – k} ways. The two selections can obviously be done in ⁿC_k ^{n – k}C_{r – k} ways. Since in both cases we end up with r – k items for one purpose and k items for a second purpose, the number of ways must be the same. Hence, ⁿC_r ^rC_k = ⁿC_k ^{n – k}C_{r – k}.

An example of this last result is as follows. Suppose we have a class of 30 students. We need to select a committee of 7 members within which we select a sub-committee of 3 members. Then we can first select the entire committee, which can be done in ³⁰C₇ = 2,035,800 ways. Then we select the sub-committee, which can be done in ⁷C₃ = 35 ways. This gives a total of 2,035,800 × 35 = 71,253,000 ways. Alternately, we select the sub-committee first, which can be done in ³⁰C₃ = 4,060 ways. Now we have to choose the remaining 4 members of the committee from the remaining 27 students, which can be done in ²⁷C₄ = 17,550 ways. This gives a total of 4,060 × 17,550 = 71,253,000 ways. This is an example of the multiplication principle that we dealt with in Down for the Count.

Binomial Identities

Having considered some combinatorial arguments, we turn our attention to the binomial coefficients themselves. Since there is a pattern leading from one row to the next, there must be some relationships that hold among these coefficients. For simplicity in proposing and proving these relationships, let us take a = 1 and b = x in the expansion of (a + b)ⁿ, which becomes (1 + x)ⁿ.

Example 1

Using the normal binomial expansion we obtain

If we substitute x = 1 in the above we get

We can verify this by considering a few rows of Pascal’s triangle. For example

We can see that the identity holds true for the first 5 values of n.

Example 2

Now, if we substitute x = -1 in the expansion of (1 + x)ⁿ, we will get

We can verify this for the first few rows of Pascal’s triangle. For example

Again, we can see that the identity holds true for the first 5 values of n.

Example 3

We can even use differentiation to obtain various results. For example, consider the expansion

If we differentiate both sides with respect to x we will get

Now, if we substitute x = 1 in the above equation, we will get

Again, we can verify this for the first few rows of Pascal’s triangle. For example

Once again, we have seen that the derived identity holds for the first 5 values of n.

Example 4

We can carry the idea of differentiation further as follows. We know that

If we multiply both sides by x we will get

Now, if we differentiate with respect to x we will get

Once again, we can verify this for the first few rows of Pascal’s triangle. For example

So, we have verified the result for the first 3 rows of Pascal’s triangle.

Parting Shot

What we have seen in this post is that we can use logical arguments to obtain relationships between binomial coefficients. We can also use simple algebra and calculus to obtain other relationships. As seen in the last example, we can multiple (1 + x)ⁿ by other terms to obtain further identities. The results are quite obviously endless. For example, I leave the reader to attempt to prove that

Perhaps a hint would help. Consider the expansion of

If you wish to check the proof, click here.

Our study of counting principles is not over, though. There is much more left to go. In the next post, we will consider how to obtain the number of divisors and sum of the divisors of any natural number without actually listing the divisors or counting them. And we will consider the technique of partitions. Till then, the ball is in your court.

Refresher

Two weeks back, we started a new series on Counting Principles. In Down for the Count we looked the the basic multiplication and addition principles of counting. In Arranging and Choosing we introduced the ideas of permutations and combinations. In this post, we will consider circular permutations and permutations with restrictions.

Circular Permutations

When we introduced permutations, even though we did not mention it explicitly, the implicit understanding was that we were arranging the objects in a row. In fact, this is not necessarily the case. However, if we are able to call one position the ‘first’ position and another the ‘second’, etc., then what we have, in effect, is a row of positions since we can place the positions in a row according to their ‘number’.

Now, if we arrange the positions in a circle, what we lose is the ability to name a position as genuinely ‘first’. As the legendary round table of Arthur asserted, there is no ‘first’ in such a seating arrangement. Since there is no head, there is no primacy given to any particular position. We are only left with the relative positions and can say, “Person A is seated to the right of person B” or “Person B is seated to the left of person A.”

Now suppose there are 5 distinct objects that need to be permuted and placed in a circle. Two of the permutations are ABCDE and BCDEA. These are shown below

Since no position is a ‘starting’ positions or ‘first’ position, the two linear permutations above represent the same circular permutation, with A→B→C→D→E→A, being the progression if we went clockwise around the circle. We can easily see that the permutations CDEAB, DEABC, and EABCD represent the same circular permutation. Hence, there are 5 linear permutations that represent the same circular permutation. This simply represents having 5 options for the top position.

If we generalize this to n objects, we can see that we will have n linear permutations that represent the same circular permutation. Now, n objects can be permuted in n! ways, as we saw in the previous post. This means that n objects can be permuted in a circle in

We can extend this further to permuting r out of n objects. We know that r out of n objects can be permuted in ⁿP_r ways. However, for each set of r objects, there will be r linear permutations that represent the same circular permutation. This means that r out of n objects can be permuted in

Permutations of Non-Distinct Objects

Now suppose we do not have distinct objects. Rather, there are some objects that are identical. Let us consider a small set to get started. Now, instead of 5 distinct objects, let us consider 5 objects, 2 of which are identical. Hence, we could consider the set to be A, A, B, C, D. Note that the two ‘A’s are identical. Hence, it is impossible to distinguish between them. However, for the sake of this illustration, let us use subscripts to indicate patterns. So the two ‘A’s are A₁ and A₂.

Now, it is clear that the patterns A₁A₂BCD and A₂A₁BCD will be indistinguishable since both will appear as AABCD. In other words, there are 2 patterns that are indistinguishable from each other. In a similar way, BA₁CA₂D and BA₂CA₁D will appear as BACAD. What this means is that, no matter where we place the two ‘A’s, there will be two permutations that will be indistinguishable from each other.

What happens if there are 3 identical objects (e.g. AAABC)? Well, we can see that the patterns A₁A₂A₃BC, A₁A₃A₂BC, A₂A₁A₃BC, A₂A₃A₁BC, A₃A₁A₂BC, and A₃A₂A₁BC will all appear as AAABC. Hence, there are 6 permutations that will be indistinguishable.

We can see that, if there are p objects that are identical, then there will be p! permutations that will be indistinguishable, all of which represent permutations in which the identical objects occupy the same positions in the pattern. Hence, if there are n objects, p of which are identical, they can be permuted in

We can extend this to multiple kinds of identical objects. Suppose we have n objects with p₁ of one kind, p₂ of a second kind, etc. up to p_k of a k^th kind. Then the number of permutations will be

Let’s apply this. Let’s say I have 50 tiles, 4 of which are blue, 5 of which are red, and 10 of which are green, all others being distinct. Then then number of permutations will be

That’s 2.91… septendecillion permutations! I bet you learned a new word here!

Permutations with Restrictions

We can also consider a different kind of permutation in which we have some restrictions. For example, suppose we have 5 distinct objects (e.g. A, B, C, D, and E), which have to be arranged such that two of them, say A and B, have to be adjacent to each other. To find the number of permutations, we consider the group formed by A and B to be a distinct group, say X. Then, we have 4 distinct objects, C, D, E and X, which need to be permuted. This can obviously be done in 4! = 24 ways. However, the objects A and B can be permuted among themselves in 2! = 2 ways. For example, the permutation CXDE can be CABDE or CBADE. Hence, the total number of permutations is 4! × 2! = 24 × 2 = 48.

We can generalize this. Suppose we have n distinct objects, p of which need to be placed in a group and arranged among themselves. Hence, there are n – p distinct objects which have no restrictions. Then the number of distinct objects will be n – p + 1, including the group with p objects, which can be permuted in (n – p +1)! ways. However, the p objects can be permuted among themselves in p! ways. Hence, the total number of permutations will be (n – p + 1)! × p!.

Let’s consider an example. Suppose there is a group of 20 people, 5 of whom must be seated together. Then then number of permutations will be

Of course, we can extend this further. Suppose there are n distinct objects that need to be arranged such that a group of p₁ objects need to be together, another group of p₂ objects need to be together, and so on till a group of p_k objects need to be together. Note that each group will count as 1 object. Hence, the effective number of objects, including distinct objects and groups, which need to be permuted will be

Hence, the number of permutations, including the permutations within the groups, will be

Let’s try this out. Suppose there are 50 seats in a bus and 50 passengers. Among the passengers are a family of 5, a couple, and a group of 11 friends. If the groups have to sit together, the number of permutations will be

That’s 98.99… quindecillion permutations!

Looking Ahead

In this post we have looked art some different kinds of permutations, where the objects are arranged in a circle or where some of the objects are identical or where some distinct objects need to be kept together. Of course, there are cases where we may need to ensure some objects are not placed together, as in the case of rivals or bitter enemies. This is a much more complex situation than simply keeping a group together. So we will look into that in a post much later. However, in the next post, we will turn our attention to combinations and look at what are known as combinatorial arguments, which will help us to derive identities using the binomial coefficients solely through logical argumentation rather than through algebraic manipulation. Auf wiedersehen!

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.

What Are Counting Principles?

Counting is something that we learn from a very young age, either in the informal environment at home or in the formal environment of school. It forms the basis of all the mathematics we learn through our lives. All the basic mathematical operations (addition, subtraction, multiplication, division, and exponentiation) can be explained in terms of counting. Hence, it is often the case that, when students reach high school, after probably 10 years of formal mathematics, they are surprised when they see a chapter in their book with the title “Counting Principles”. They may think, “What principles might this involve? How much more is there to counting? Didn’t we put the issue of counting behind us when we learned how to perform the operations?”

What the student does not realize is that what she has learned so far are ‘recipes’ for performing the mathematical operations. That is, she has been given some idea of what the operations involve. However, the main focus would have been on how to perform the operations not on why certain operations are needed to be performed. For example, if you were given 3 ⊗ 7, where ⊗ indicates some mathematical operation, what would the result be? 3 + 7 gives us 10, 3 – 7 would yield -4, 3 × 7 is 21, 3 ÷ 7 would be 0.428571…, and 3⁷ is 2187. While the student would easily be able to determine each of these five answers, which operation should she use in a given context? This is where the idea of the counting principles comes in. These principles tell us which operations are to be used in a given context.

The Multiplication and Addition Principles

As an example, suppose a restaurant offers a 3-course lunch with 3 options of starters, 5 of main courses, and 2 of desserts. How many different selections of lunch can a customer make? Or if you have a choice of a room from 3 hotels, one of which has 20 rooms, the second 30 rooms, and the third 50 rooms, how many choices of rooms do you have? How do the 3, 5, and 2 in the first situation relate to each other. How do the 20, 30, and 50 in the second situation relate to each other? There needs to be some principles on the basis of which the student would decide how to find the answer to each of the situations. What are these principles?

Today, we are starting a new series on counting principles. We will start with some basic ideas and work ourselves to more complex ideas. At the end we will answer the following question: “For a theatre production of a play there are n characters, each of which requires an understudy. If any of the actors and understudies can play all the parts and if the main actor must have more years of experience than the understudy, in how many ways can main actors and understudy actors be assigned?”

As promised, let us begin with the two earlier examples, which are relatively easy. Suppose we label the starters as A, B, and C, the main courses as P, Q, R, S, and T, and the desserts as Y, and Z. The possible choices are listed below:

In the above, each row represents a different choice of starter. The colors differentiate the main courses. Finally, the dessert choice is differentiated between normal and italicized fonts. We can see that there are 40 possible selections because 4 × 5 × 2 = 40. But the reason we multiply is that the customer has to choose a starter and a main course and a dessert.

In the case of the hotels, we cannot multiply because the person can only occupy one room. Hence, he must choose to go to either hotel A, where he has a choice of 20 rooms, or hotel B, where he has a choice of 30 rooms, or hotel C, where he has a choice of 50 rooms, yielding a total of 20 + 30 + 50 = 100 choices.

The situation with the lunch choices is one in which we use what is known as the multiplication principle, while the case with the hotel rooms uses the addition principle.

The multiplication principle states that, if there are m ways of doing one thing and n ways of doing a second thing, then the number of ways of doing both things is m × n. The addition principles states that, if there are m ways of doing one thing and n ways of doing a second thing, then the number of ways of doing either thing is m + n.

Since the lunch menu required a choice of starter and main course and dessert, the multiplication principle was applicable. And since the hotel room required a choice of only one of the three hotels, the addition principle was applicable.

Your Turn

Why don’t you try the questions below?

1. A football squad consists of 3 goalkeepers and 5 strikers. In how many ways can the coach choose 1 goalkeeper and 1 striker?
2. A library allows members to borrow two books at a time. The library has 15 books by Jeffrey Archer and 23 books by Paulo Coelho. In how many ways can a member borrow 1 book by each author?
3. There are 5 apples and 7 oranges in a fruit basket. In how many ways can a person choose either an apple or an orange?
4. A student has 3 colleges to choose from. The first college has 3 programs, the second has 5 and the third has 6. Assuming that the programs are full-time programs, in how many ways can she choose a program?
5. A library allows members to borrow only one book at a time. The library has 15 books by Jeffrey Archer and 23 books by Paulo Coelho. In how many ways can a member borrow a book by either author?
6. Three cities A,B, and C are connected by 4 roads between A and B, 5 between B and C, and 6 between C and A. In how many ways can a round trip be made?

How did you fare with the above questions? The answers are 15, 345, 12, 14, 38, and 720. Many students get the first 5 but stumble on the last one. The answer I have given is correct. It is 720. If you wish to check the solution, click here.

Checking Out

As we continue with the series, we will see that there are many ways to put these two basic counting principles together. We will learn about permutations and combinations in the next post as well as the relation of the latter to Pascal’s triangle. We will also learn about how permutations and combinations relate to each other. We will also see why the combinations show up as the coefficients of the binomial expansion. Till then, let everything count.