The factorial: not an excited number.

mgfact
The factorial of a number is what you get when you multiply that number and those smaller than it (down to one) together. That means that five factorial is 5x4x3x2x1=120. The mathematical notation for factorial is to use an exclamation point: 5!=120. Occupy Math was teaching a course that used factorials to count things and one of the sharper students kept getting problems wrong. Occupy Math wrote “5” on the board and asked “what number is that?” The student replied “five”. Occupy Math added an exclamation point to get “5!” and again asked the student what the number was. The student replied “FIVE!” This was a third-year university student — hence this educational post. This week’s Occupy Math looks at what factorials do (e.g.: they count things). Factorials also provide an example of something that grows faster than exponentially.

The factorial is only defined for positive whole numbers and zero. The value of zero factorial is one (Occupy Math explains why below). Let’s start with the question “How many ways are there to line up 4 students?” Occupy Math will give these students the rather terse names A, B, C, and D and simply list all the possible lines. That gives us:

students

Check for yourself that there are no more ways to line up these students. Occupy Math has presented these 24 ways to line up four students in four groups of six. Each group starts with one letter and, after that, the rest of the group of six contains all ways to line up the three remaining students. The other cool fact is that 4!=24. In fact, factorials exactly count the number of different ways to line people up.

Of course, Occupy Math is just claiming that this is true based on one, possibly coincidental, example. Looking closely at this example, 3!=6 so the “pick a student and then line up the remaining three students in all possible ways” notion is a second example that agrees with Occupy Math’s claim. In general, the algorithm for finding all the ways to line up the students is this. Pick a first student – then there is a group of lines where that student is at the head. Within that group, list all the ways to line up the remaining students. If there are n students then the total number of lineups is n (the number of different choices for a first student) times the number of ways to line up the remaining students. If you line up all the students this means you are multiplying the number of students by that number minus one, then that number minus two, and so on. You stop at one because there is (clearly) only one way to line up one student.

This gives us the mathematician’s definition of n! as follows:

n!=n x (n-1)!

Let’s compute five factorial this way — remember that “!” is a mathematical symbol, not punctuation. “5!” is “5×4!” is “5x4x3!” is “5x4x3x2!” is “5x4x3x2x1!” is “5x4x3x2x1” is “120”. This is an example of a recursive definition that explains something in terms of itself — but itself at a smaller size. If you follow all the way to the first case, 1!=1, then this is a perfectly good definition. It looks circular, but it is not, because the size of the instance of the thing you’re working on shrinks. It is important to know where this self-shrinking definition ends, e.g. at “one factorial is one”.

How can you grow faster than exponentially?

When we have an exponential function it looks like 25=2x2x2x2x2. In English, two to the fifth is two times itself five times. Five factorial, compared with two to the fifth is 1x2x3x4x5. It is also five numbers multiplied together, but they are not all 2. Three of them are bigger than two. That is the trick. If we were looking at eight to the nth power, then we would multiply 8 by itself n times. If n is much bigger than eight, then n! is computed by multiplying seven things smaller than eight, one thing equal to eight, and a lot of things bigger than eight. It does not matter what number you take as the base constant of the exponential — the factorial eventually starts growing faster than the base of the exponential and the advantage of the terms multiplied to make the factorial only increases as n increases.

What do factorials count?

We already know that factorials count the number of ways that students can be lined up. A order for a set of objects is called a permutation of the objects. To rephrase the “lining up” result: the number of permutations of a set of n objects is n! That’s already interesting, but let’s build on it.

Suppose you have a club with ten members. How many ways are there to choose a president, vice president, and treasurer? There are ten choices for president, nine remaining choices for vice president, and once those two are chosen, eight remaining choices for treasurer. The total is 10x9x8=720 choices. This is the first part of a factorial. In fact 10x9x8=10!/7! What happens is that you divide out the (irrelevant) way to order the seven people not chosen for an office. This sort of counting problem is also called a permutation — but an incomplete one.

What about zero factorial being one?

Suppose we are adding up a list of numbers. We can do this by starting with zero and then adding the numbers in the list one at a time to a running total. Starting with zero seems a bit eccentric, except that it tells us what happens if we add a list of no numbers at all: we get zero. A lemonade stand with no sales has made zero money, so there is a real world example that shows this makes sense. Now suppose we are multiplying a list of numbers in a similar fashion. If we start with zero, we stay there: starting with one will give us the correct result. This is why the product of an empty list of numbers is one (which is what zero factorial is). Why zero and one for addition and multiplication? Zero is the number you can add to another number without changing it; one is the number you can multiply by another number without changing it. There is another way to see that 0!=1. Remember that factorials count the number of orders you can put a group in? Well, there is one way to order a group with no-one in it.

Occupy Math has gone fairly deep into the ocean of math in this post — partly in hopes of letting a future student avoid being laughed at by his peers when he says “FIVE!” instead of “a hundred and twenty”. Another important point is that there are a whole lot of different problems that start with “how many …” and factorials are key to solving many of these problems. The field of math concerned with this sort of counting is called enumerative combinatorics and Occupy Math has taught both university and graduate courses in the subject. The results can get really weird. Occupy Math will now troll you with a strange example: the number of ways a tournament can have a completely unambiguous result (no A beats B, B beats C, C beats A) is equal to the number of ways to assign negative one colors to the teams so that no two teams that play one another are the same color. The really hard part of this is finding a situation in which “negative one colors” makes sense. Occupy Math promises the situation exists and will look at this in a future post.

Another important point is that when you are doing probability, the way to compute the odds of something happening is to first compute the number of ways the thing you’re interested in could happen and then divide by the number of ways anything at all can happen. The discipline of counting things (enumerative combinatorics) is one of the foundations of probability. Even in this abstract realm, things that come up in the world are present. Do you have a topic to suggest? Please comment or tweet!

I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s