Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Defining zero factorial

johndcook.com

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Defining zero factorial

#31

Post by cbd1984 »

hirak99 wrote: post #7

How would you find (n-1)! given n!? (Think for a moment before moving on.) Dividing by n of course, (n-1)!=n!/n. This immediately extends the notion of factorials backwards to 0!=1!/1. It's only a matter of checking to see which factorial-dependent formula (usually arising in context of combinatorics, or gamma function) fits - and it turns out (luckily) that everything fits. Edit: Even if it tuned out some things don…

> How would you find (n-1)! given n!?

If you want to think a little more:

You are given a value v, which you are told is n! for some n, which you are not told. Find a general algorithm to produce (n-1)!.

I have an algorithm which, I fear, may not have the most efficient running time.

Re: Defining zero factorial

#32

Post by Houshalter »

jakeogh wrote: post #30
Houshalter wrote: post #28

I tried to fit a simpler function to the (logarithm of) factorial function with symbolic regression: http://i.imgur.com/9UJCDxT.png?1 They all seem to fit it fairly well, and they all suggest that 0! should be close to one. This is hardly rigorous mathematics, but I find it interesting that it should converge to the same prediction, when I gave it no bias that it should be that way.

Interesting! What software is that?

It's Eureqa: http://www.nutonian.com/products/eureqa/ which is fantastic for what it does.

Re: Defining zero factorial

#33

Post by rbehrends »

The much simpler answer is that this is the special case of the empty product being 1 (or more precisely, the neutral element of the monoid on which your multiplication operates).

The empty product is 1 so that $\prod_{x \in S \setminus T}x\prod_{x \in T}x = \prod_{x \in S}x$ holds for all $T \subseteq S$.

It's the exact same reason why the empty sum is zero (zero being the neutral element of a monoid using additive notation).

n! is commonly defined as the product of all positive integers less than or equal to n. For n = 0, this is the product of the empty set.

Re: Defining zero factorial

#34

Post by panic »

cbd1984 wrote: post #31
hirak99 wrote: post #7

How would you find (n-1)! given n!? (Think for a moment before moving on.) Dividing by n of course, (n-1)!=n!/n. This immediately extends the notion of factorials backwards to 0!=1!/1. It's only a matter of checking to see which factorial-dependent formula (usually arising in context of combinatorics, or gamma function) fits - and it turns out (luckily) that everything fits. Edit: Even if it tuned out some things don…

> How would you find (n-1)! given n!? If you want to think a little more: You are given a value v, which you are told is n! for some n, which you are not told. Find a general algorithm to produce (n-1)!. I have an algorithm which, I fear, may not have the most efficient running time.

If you have n! in binary, count the number of zeros at the end of its binary expansion and call this count k. The number k+1 approximates n relatively closely (the error n-k is the number of ones in n's binary expansion—see http://www.cut-the-knot.org/blue/LegendresTheorem.shtml).

Re: Defining zero factorial

#35

Post by rbehrends »

johndcook wrote: post #6
jameshart wrote: post #5

Isn't it just a special case of the idea that the product of an empty sequence is 1?

Almost, but not quite. You could say "n! is the product of the natural numbers However, this same reasoning would say (-1)! = 1, (-2)! = 1, etc. And while you could define negative factorials that way, it's better in practice to leave negative factorials undefined.

This is really a different issue. You'd be extending the domain of factorial beyond what it's traditionally been used for (same as if you extended it to include other numbers outside the natural). That you can do it for some sets (gamma function) doesn't matter, because it also stands on its own. And if you extend it, it's not the factorial function anymore, which is defined to have the non-negative integers as its domain.

But conceptually the primary use case in combinatorics is for permutations, i.e. $n!=|S_n|$, which only makes sense for $n \ge 0$. You could even make an argument for n!= because $|S_0|$ should be 1 on its own (because there's exactly one permutation of the empty set) without saying that it makes formulas easier. (This, I note again, matters regardless of what the gamma function does.)

Re: Defining zero factorial

#36

Post by jameshart »

johndcook wrote: post #6
jameshart wrote: post #5

Isn't it just a special case of the idea that the product of an empty sequence is 1?

Almost, but not quite. You could say "n! is the product of the natural numbers However, this same reasoning would say (-1)! = 1, (-2)! = 1, etc. And while you could define negative factorials that way, it's better in practice to leave negative factorials undefined.

That same reasoning would also say that π! is 6, which is not really a useful result, so we are probably best looking for a different definition.

There's also some controversy about whether "there are no natural numbers <= 0"...

Post reply on HN