50 Chapter 5

5.6 Permutations and combinations

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 acb bac bca cab cba

More generally, mathematicians define that a permutation of a set is a one-to-one cor-

respondence 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.

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

0! = 1

(n + 1)! = (n + 1) · 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 42. For any integer n ≥ 0, the number of permutations of n objects is the facto-

rial 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 have n + 1 objects a

1

, a

2

, ..., a

n

, a

n+1

to be rearranged, let us first rearrange the first n

objects a

1

,...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.