What Is N Factorial Used For?

Date: 08/29/2001 at 18:02:22
From: Stuart Reed
Subject: What is n factorial used for?

Can you please tell me what n! or n factorial is used for. I know what 
it is (5! is 120, because 1*2*3*4*5 = 120), but not what it is used 
for. I have heard that it is used in probability, but what for, and 
how? How does it work, and what are its uses?

Date: 08/30/2001 at 10:49:46
From: Doctor Ian
Subject: Re: What is n factorial used for?

Hi Stuart, 

The factorial function is useful in computing the number of 
combinations or permutations that can be constructed from a set of 
objects. You can read about these uses in our FAQ:

   Permutations and Combinations
   http://mathforum.org/dr.math/faq/faq.comb.perm.html   

Very briefly, here is the kind of problem that would give rise to the 
factorial function.  

Suppose you have three people (Alan, Bob, Cindy), and you want to know 
how many ways they can stand in line. For a small number like 3, the 
answer is easy to construct by trial and error:

  Alan, Bob, Cindy
  Alan, Cindy, Bob
  Bob, Alan, Cindy
  Bob, Cindy, Alan
  Cindy, Alan, Bob
  Cindy, Bob, Alan

But for larger numbers of people, it becomes very difficult to avoid 
duplicating some sequences, or skipping some by accident. 

With a little thought, we can see that if we have N people, then there 
are N choices for who might go into the first position:

  1. Alan
  2. Bob
  3. Cindy
  4. Diane
  
Having made that first choice, there are N-1 choices for who might go 
in the second position, for _each_ of the original choices:

  1. Alan   1. Bob
            2. Cindy
            3. Diane

  2. Bob    1. Alan
            2. Cindy
            3. Diane

  3. Cindy  1. Alan
            2. Bob
            3. Diane

  4. Diane  1. Alan
            2. Bob
            3. Cindy

And there are N-2 choices for who might go into the third position, 
again for _each_ of the previous sets of choices:

  1. Alan   1. Bob      1. Cindy
                        2. Diane

            2. Cindy    1. Bob
                        2. Diane

            3. Diane    1. Bob
                        2. Cindy

  2. Bob    1. Alan     etc.
            2. Cindy
            3. Diane

  3. Cindy  1. Alan
            2. Bob
            3. Diane

  4. Diane  1. Alan
            2. Bob
            3. Cindy

I'll leave the rest of the chart for you to fill in, if you wish. 

Note that the final number of possible orderings of N objects will be

        ways to 
        make the 
        next choice
        |
        v
  N * (N-1) * (N-2) * ... * 1

  ^                         ^
  |                         |
  ways to                   ways to
  make the                  make the
  first choice              final choice

which is exactly the factorial function. 

When dealing with combinations and permutations (and, by extension, 
when dealing with probabilities), this kind of reasoning comes up over 
and over again, which is why the factorial function is so important. 

Does this help? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/