Sunday, January 15, 2012

Fun with Factorials

Edit (1/17/12): Due to a sharp-eyed reader, I've rewritten this post after some reflection to better show what's going on. I thought I was proving that \(0!=1\), when what I'm really doing is showing how defining \(0!=1\) is internally self-consistent with everything else about the factorial function.

Let's talk about the factorial function today. Factorials are a part of mathematics that show up in certain areas of calculus, but are simple enough to understand without it. Factorials are represented (somewhat unusually if you haven't seen it before) by the exclamation mark, like so: n! (Pronounced "n-factorial", not "n!" with a little exclamatory flourish when you say it, although you can do so mentally if you like to spice up your mathematics a bit.) A function just means that it takes an input (in this case, a non-negative integer) and produces an output (also an integer).

There is a formal way to define the factorial function, but we'll start with the "shortcut" way. For any (non-negative) integer n, the factorial is simply the product of the integer times each integer less than it. Thus \[2!=2\times1=2\]\[3!=3\times2\times1=6\] \[4!=4\times3\times2\times1=24\]\[\vdots\]\[8!=8\times7\times\dotsm\times2\times1=40,320\]\[9!=9\times8\times\dotsm\times2\times1=362,880\]\[\vdots\]
You may be wondering where this factorial function shows up in real life. It actually makes an appearance in a fairly mundane setting, namely, the number of ways you can arrange a set number of things into distinct patterns. Basically, if you n objects there are n! ways to arrange them. For instance, if you have two objects 'X' and 'Y', there are two ways you can arrange them (as 'XY' or 'YX'), which equals 2!. If you have 'X', 'Y', and 'Z', you can arrange them six ways, as so:
'XYZ', 'XZY', 'YXZ', 'YZX', 'ZXY', 'ZYX'
which equals 3!. This idea of arranging things in a set is important, and we'll come back to it in a bit.

By now you've probably noticed a pattern with the results of the factorial function. The factorial of an integer is the product of the integer itself, times the factorial of the next smallest integer, for instance \(4!=4\times3!=4\times6=24.\ \) We can write this formally as:
\[n!=n\cdot(n-1)!\tag{1}\]
The factorial function is what's formally known as a recursive function, which means that each value is obtained by knowing a previous value. This is the exact opposite of the shortcut I gave above because it starts from small values and works up successively instead of working from the "top down", so to speak. If you follow this chain of reasoning, however, you'll realize that we need to know a value to start the whole recursive line off in the first place. In fact, we need two values, because of the presence of both \(n\) and \(n-1\) in equation (1) above.

Thus in practice, the factorial function can be completely described by equation (1) and two initial values, which for various reasons we choose to be the values of \(0!\) and \(1!\). In a sense we can define these initial values to be anything we want, but there's a catch: we want the factorial function to line up with what I mentioned before about arranging items. What values do we need to choose for \(0!\) and \(1!\) to make that happen?

It's probably not to hard to see that we should choose \(1!=1\). That makes sense, both in light of the shortcut I gave above (\(2!=2\times1\), so \(1!=1\) sounds good), and because if you have one item, you can really only arrange it one way.

The value of \(0!\), however, is a bit more tricky. How many ways can you arrange zero items? Is the question even well-defined? And more importantly, zero times anything is zero, so the value of \(0!\) can't be zero. You'll notice that in the shortcut method I used above, I didn't go all the way to zero, because doing that would result in zero for everything.  Instead, the value is chosen to be 1, so that \(0!=1\).

You might be wondering how this makes any sense, as I first did back in second semester calculus. While I could maybe buy the argument that zero items can be arranged one way, it still seems kind of nebulous. Is there anyway to show that choosing \(0!=1\) is consistent with what I said above about the factorial funtion?

As it turns out, there is. Let's start by taking another look the definition I gave above in equation (1): \(n!=n\cdot(n-1!).\) We can rearrange this by dividing by n on both sides to get \[(n-1)!=\frac{n!}{n}\tag{2}\]
Now, let's substitute \(n=1\) and see what we get.
\begin{align}
 (n-1)!&=\frac{n!}{n}\\
(1-1)!&=\frac{1!}{1}\\
0!&=\frac{1}{1}=1
\end{align}
Upon reflection I now hesitate to call this a proof, and consider it more of a demonstration of the internal self-consistency of choosing \(0!\) to be 1. The point is, having defined the values of \(0!\) and \(1!\) we can now go about using equation (1) to work our way up from zero:
\[0!=1\]\[1!=1\times0!=1\times1=1\]\[2!=2\times1!=2\times1=2\]\[3!=3\times2!=3\times2=6\]\[4!=4\times3!=4\times6=24\]\[\vdots\]
And now you know about the factorial function.

5 comments:

  1. Here's what I don't get: How exactly is 1 x 0 = 1? This seems unlikely.

    ReplyDelete
  2. You mean "1!"? It all depends on the recursive formula I gave. In that case 1!=1 x 0! = 1 x 1 = 1.

    In a sense, because of the recursive nature of the definition, it all depends on defining 0! = 1. But that definition works, as I showed above. Think of it another way: n! is the number of ways to order n items. How many ways can you order 0 item? Just one. Does that make sense?

    ReplyDelete
  3. You wrote, "It's simple enough to see that 1! = 1 x 0 = 1". I don't see it.

    I understand n! as ways of ordering n terms, but I'm not convinced that the recursion formula extends below 1. 2! = 2 x 1, but 1! = 1 x 0? I think that putting it as ways of ordering n terms is better, because then 2! = 2 x 1 x 1, and 1! = 1 x 1. Of course, you can extend the x 1 x 1 infinitely back, but you obviously get the same result. 0! is peculiar to me at least. It is peculiar because of the idea of ordering 0 items. How many ways can you arrange 0 items? What does it even mean to arrange 0 items? The formula legitimately derives that 0! = 1 because the formula is for n >= 1, but it is still very strange to say you can arrange zero items 1 way. I suppose by default that is true, but arranging zero items 1 way is not the same as arranging 2 items 2 ways. I suppose that I see a qualitative difference in the usage of the word "arrange" or "order". You can arrange A and B as either AB or BA, but how do you arrange absolutely nothing? Seems very Zen.

    ReplyDelete
  4. Ahh, you're right, I do have a typo in the part you quoted. Unfortunately I don't remember what it should have said to be correct at the moment. I think I'll go through and rewrite this post tomorrow when I'm more lucid, since, upon reflection, it's not really a proof that 0!=1 so much as it is a proof that defining 0! to be 1 makes the factorial function consistent. The recursion formula requires n and n-1, so we define 0! and 1! to be 1, and the rest follows from that. But yeah, it doesn't really prove anything fundamental in the way that we can prove 2+2=4.

    In the same vein, I see your point about arranging zero things. Personally I could see arguments for either an infinite number of ways or zero ways. Again, it's basically a consequence of defining 0! to be 1.

    ReplyDelete
  5. Ok, I've rewritten it to hopefully better reflect reality. Let me know if you catch any other errors!

    ReplyDelete

Think I said something interesting or insightful? Let me know what you thought! Or even just drop in and say "hi" once in a while - I always enjoy reading comments.