When I first learned factorials, they just gave me a formula and some practice problems. It didn’t make any sense, and it felt like it sort of just fell from the sky. It wasn’t clear why I should care about factorials or even what they’re doing. It wasn’t until later in college that I really saw how powerful and interesting they are: factorials are a central workhorse of combinatorics (the math of counting things) and consequently a common offender in probability. I wanted to walk through the main inspiration for factorials: counting arrangements.
Factorial: counting arrangements
So—how do you count up the number of possible arrangements of n objects? Well…let’s play around a little, and see if we notice some patterns. To make our lives easier, let’s label our objects with letters a, b, c, …
Case: n = 1
How many ways can we arrange one object, a? 1 arrangement: just set down a, and you’re done.
Case: n = 2
Now, what about two objects, a and b?
a b b a
So, we listed all our new arrangements by taking each old arrangement (in this case, there was only one) and inserting b wherever we see an opening namely, before a and after a. Now we have
2 · (# arrangements for a) = 2 arrangements:
Case: n = 3
Now, this is where it starts to get interesting. As we increase the number of objects, we should think about nice ways to list the number of arrangements, otherwise we’ll have a mess on our hands. Specifically, we should try to find an algorithmic way to write new arrangements. But how? Hmmm…
a b c b a c
a c b b c a
c a b c b a
See that? We took advantage of our old list of arrangements for two letters to create our new list! We took each arrangement, ab and ba, and for each of them, considered each possible place we could insert our new letter c. So we now have
3 · (# arrangements for a, b) = 6 arrangements.
Case: n = 4
So—let’s apply that strategy again!
a b c d b a c d
a b d c b a d c
a d b c b d a c
d a b c d b a c
a c b d b c a d
a c d b b c d a
a d c b b d c a
d a c b d b c a
c a b d c b a d
c a d b c b d a
c d a b c d b a
d c a b d c b a
So now, we can see that adding in another letter d gives us 4 arrangements for each arrangement of 3 letters we had before. Thus, we now have
4 · (# arrangements for a, b, c) = 24 arrangements for 4 letters.
The rest of the cases: recursion
We now see the pattern for counting the number of arrangements of n objects—simply multiply n by the number of arrangements for n – 1 objects. So, if we chose a convenient notation to say something like this:
n! = # arrangements of n objects
Then, we turn our observation into an equation:
n! = n · (n-1)!
And suddenly, since we know that:
1! = 1
…we can calculate the number of arrangements for any positive integer n, just by starting at 1 and repeatedly plugging into our equation! This type of formula, one that tells you the next member of a sequence based off of previous members, is called recursive.
And just like that…we now have a mathematical idea that is interesting enough to earn its own definition.
The factorial of a nonnegative number n, denoted n!, is given by
n! = n · (n-1) · (n-2) · … · (3) · (2) · (1)
As a special case, we define 0! = 1.
For example, 4! = 4 · 3 · 2 · 1 = 24, and 5! = 5 · 4 · 3 · 2 · 1 = 120. As we saw above, n factorial counts the number of arrangements of n distinct objects. This definition is driven by the recursive equation we wrote earlier, combined with the choice 1! = 1. We decided to define 0! = 1 because it’s computationally convenient and there’s exactly one way to arrange nothing. The computationally convenient part will become more evident when I write about permutations and combinations next time, which totally rest upon factorials.
Did you notice that the definition makes no mention whatsoever of counting objects? Why not? When writing definitions, mathematicians like to keep it as bare bones as possible. The idea is to build up our theory from the simplest, cleanest tools we can, so we can really strike the heart of why something is true. The interpretations of these tools are of great importance, guiding our use of and breathing life into the definitions, but when we want to prove something, we want precision tools, not blunt clubs.
What’s more, this minimalism in our tools gives us flexibility that isn’t bound by interpretation, opening our minds to perhaps deeper interpretations or surprising connections. For instance, factorials are of interest in number theory, largely because they have nice divisibility properties (e.g. the product of any k consecutive integers must be divisible by k!). These sorts of unexpected connections are a large part of why I love mathematics—it feels like you’re discovering secrets of the universe!
Food: pasta night with my family in Italy! Panchetta, sun dried tomato, parmesan, basil, and most importantly, fresh pasta. Really simple, and absolutely delicious—great ingredients rarely end up anything besides tasty. Photo credit to my delightful sister Madison.
Leave a Reply