Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG
HOME > PAST ISSUE > May-June 2007 > Article Detail

COMPUTING SCIENCE

Fat Tails

Sometimes the average is anything but average

Brian Hayes

Facts About Factorials

It all begins with the factorial function, a familiar item of furniture in several areas of mathematics, including combinatorics and probability theory. The factorial of a positive whole number n is the product of all the integers from 1 through n inclusive. For example, the factorial of 6 is 1×2×3×4×5×6=720.

The standard notation for the factorial of n is "n!". This use of the exclamation point was introduced in 1808 by Christian Kramp, a mathematician from Strasbourg. Not everyone is enthusiastic about it. Augustus De Morgan, an eminent British mathematician and logician, complained in 1842 that the exclamation points give "the appearance of expressing surprise and admiration that 2, 3, 4, &c. should be found in mathematical results."

One common application of the factorial function is in counting permutations, or rearrangements of things. If six people are sitting down to dinner, the number of ways they can arrange themselves at the table is 6!. It's easy to see why: The first person can choose any of the six chairs, the next person has five places available, and so on until the sixth diner is forced to take whatever seat remains.

The factorial function is notorious for its rapid rate of growth: 10! is already in the millions, and 100! is a number with 158 decimal digits. As n increases, n! grows faster than any polynomial function of n, such as n 2 or n 3, or any simple exponential function, such as 2 n or e n . Indeed you can choose any constant k, and make it as large as you please, and there will still be some value of n beyond which n! exceeds both n k and k n . (On the other hand, n! grows slower than n n .)

The steep increase in the magnitude of n! becomes an awkward annoyance when you want to explore factorials computationally. A programming language that packs integers into 32 binary digits cannot reach beyond 12!, and even 64-bit arithmetic runs out of room at 20!. To go further requires a language or a program library capable of handling arbitrarily large integers.

In spite of this inconvenience, the factorial function is an old favorite in computer science as well as in mathematics. Often it is the first example mentioned when introducing the concept of recursion, as in this procedure definition:

define f!(n)
  if n=1
    then return 1
    else return n*f!(n-1)

One way to understand this definition is to put yourself in the place of the procedure: You are the factorial oracle, and when someone gives you an n, you must respond with n!. Your task is easy if n happens to be 1, since calculating 1! doesn't take much effort. If n is greater than 1, you may not know the answer directly, but you do know how to find it: just get the factorial of n–1 and then multiply the result by n. Where do you find the factorial of n–1? Simple: Ask yourself—you're the oracle!

This self-referential style of thinking is something of an acquired taste. For those who prefer looping to recursions, here is another definition of the factorial:

define f!(n)
  product:=1
  for x in n downto 1
    product:=product * x
  return product

In this case it's made explicit that we are counting down from n to 1, multiplying as we go. Of course we could just as easily count up from 1 to n; the commutative law guarantees that the result will be the same. Indeed, we could arrange the n numbers in any of n! permutations. All the arrangements are mathematically equivalent, although some ways of organizing the computation are more efficient than others.








comments powered by Disqus
 

EMAIL TO A FRIEND :

Of Possible Interest

Feature Article: The Statistical Crisis in Science

Computing Science: Clarity in Climate Modeling

Technologue: Weighing the Kilogram

 

Other Related Links

A Tale of Tails

Subscribe to American Scientist