Permutations and combinations

A selection from Proof and the Art of Mathematics

A permutation of a list of objects is a rearrangement of those same objects into a different order. For example, there are six permutations of a list of three objects:

\(abc\quad acb\quad bac\quad bca\quad cab\quad cba\)

More generally, mathematicians define that a permutation of a set is a one-to-one correspondence of the set with itself. In the case of a finite set, the permutations in effect describe all the different ways that we might enumerate the elements of the set.

This is an excerpt from chapter 5 of my book Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing for aspiring mathematicians who want to learn how to write proofs, in the context of interesting mathematical statements having interesting elementary proofs.

Proof and the Art of Mathematics has recently been awarded the 2024 Daniel Solow Author’s Award by the Mathematical Association of America, awarded for outstanding and impactful contributions to mathematics education.

For any natural number n, we define the factorial number n! by recursion:

\(0! = 1\)

\((n + 1)! = (n + 1) \cdot n!\)

In this way, one can see that n! is simply the product of all the numbers from n down to 1, as in 5! = 5⋅4⋅3⋅2⋅1 = 120.

Theorem. For any integer n ≥ 0, the number of permutations of n objects is the factorial n!.

Proof: We prove the theorem by common induction. The statement is true when n = 0, since there is exactly one arrangement of zero objects, the empty arrangement. If the reader finds it confusing to consider permutations of the empty set, it may help to observe that the theorem is also true when n = 1, since there is exactly one way to permute one object also, and 1! = 1.

Now, suppose by induction that the theorem is true for a number n, and consider n + 1. If we have n + 1 objects

\(a_1, a_2, \ldots, a_n, a_{n+1}\)

to be rearranged, let us first rearrange the first n objects

\(a_1, \ldots, a_n.\)

By the induction hypothesis, there are n! many ways to do that. Next, we place the final object a_n+1​ into the list. But where? There are precisely n + 1 many slots into which it might be placed: before all them, between two of them, or after all of them. Every rearrangement of the n + 1 objects can be realized by first rearranging the first n objects and then placing the final object into one of the slots. So we will have (n + 1)⋅n! many rearrangements of n + 1 objects, and this is precisely (n + 1)!, as desired. So by induction, the theorem is true for all numbers n. □

Why did we define 0! = 1? Does that seem unnatural? Students sometimes suggest or expect that 0! should be 0. Would that be a good idea? As mathematicians, we are free to define our functions however we want. Which definition is best?

Notice that if we set 0! to be 0, then it would break the identity (n + 1)! = (n + 1)⋅n! in the case n = 0; we might have to start adding exceptions to our theorems on account of this. Indeed, the previous theorem itself provides a very good reason to define 0! = 1, since as we observed, there is exactly one arrangement of the empty set, the empty arrangement. For this reason, among others, mathematicians have agreed that it is best to define 0! = 1.

For integers 0 ≤ k ≤ n, we define

\({n \choose k},\)

pronounced, “n choose k,” as the number of ways to choose k items from a set of n items, disregarding the order.

Theorem. The number of ways to choose k items from a set of n items, for 0 ≤ k ≤ n, is given by the formula

\({n \choose k} = \frac{n!}{k!(n - k)!}.\)

We shall give several proofs.

First proof: Consider the following process: enumerate all n items, and then take just the first k in that enumeration. We will often get the same set of k elements, so there is considerable multiple counting in this process. But how much? The number of enumerations of n objects is precisely n!, by the previous theorem. For a given enumeration of the objects, there are k! many permutations of the first k elements of it, and (n - k)! many permutations of the other elements. So there are k!(n - k)! many ways to permute the elements in the enumeration, while having the same first k elements. So this is the factor that we have double counted by, and so the number of ways to choose k elements from n is precisely

\(\frac{n!}{k!(n - k)!},\)

as desired. □

The second proof will make use of the following lemma:

Lemma:

\({n + 1 \choose k + 1} = {n \choose k} + {n \choose k + 1}.\)

Proof: Consider a set A with n + 1 objects, and we wish to count the number of ways of choosing k + 1 objects from A. Fix a particular element a ∈ A. Now, some of the size-(k + 1) subsets of A have the element a, and some may not. There are exactly

\({n \choose k}\)

many size-(k + 1) subsets of A that have the element a, since once you choose a, then you must choose k additional elements from A∖{a}, a set of size n. Similarly, there are exactly

\({n \choose k + 1}\)

many ways to choose k + 1 elements from A without using the element a, since in this case one is really choosing from amongst the other n elements. So the total number of ways of choosing k + 1 elements from A is the sum of these two, and we have proved the lemma. □

Second proof: We prove the theorem by induction on n. If n = 0, then also k = 0, and it is easy to verify that there is exactly one way to choose nothing from nothing, so

\({0 \choose 0} = 1,\)

which fits the formula

\(\frac{0!}{0! \cdot 0!},\)

and so the anchor case is proved. Suppose now that the formula is correct for a number n, using any k, and consider the next number, n + 1. Since again there is only one way to choose nothing from an n element set, we see that

\({n + 1 \choose 0} = 1,\)

which is equal to

\(\frac{n!}{0!\cdot n!},\)

verifying the theorem in this case. Next, we consider

\({n + 1 \choose k + 1}.\)

By lemma 1, this is equal to

\({n \choose k} + {n \choose k + 1}.\)

By the induction hypothesis, we know that

\({n \choose k} = \frac{n!}{k!(n - k)!}\)

and

\({n \choose k + 1} = \frac{n!}{(k + 1)!(n - (k + 1))!}.\)

Putting all of this together, we may now compute

\(\begin{split} {n+1\choose k+1} &= {n\choose k}+{n\choose k+1}\\ &= \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-(k+1))!} \\ &= \frac{n!(k+1)+n!(n-k)}{(k+1)!(n-k)!}\\ &= \frac{n!(k+1+n-k)}{(k+1)!(n-k)!}\\ &= \frac{n!(n+1)}{(k+1)!(n-k)!}\\ &= \frac{(n+1)!}{(k+1)!((n+1)-(k+1))!}. \end{split} \)

This verifies the required instance of the theorem, and so we have proved it by induction for all natural numbers. □

Continue reading more about this and many other topics in Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing for aspiring mathematicians who want to learn how to write proofs.

For more math and philosophy of math content, subscribe to Infinitely More, where I make fresh posts weekly.