5 ms·

Defining zero factorial

35 points by tacon 12y ago

sukilot 12y ago
0! Is whatever makes sense in context, like any other defintion. Arguing about what it should be "in general" is treating math like reality television, and it makes you dumber. O! Isn't a big controversy, but the idiocy surrounding O^0 (which is usefully different in combinatorics vs in analysis) is mind-boggling.
- anderskaseorg 12y ago
  Defining 0^0 = 1 is just as important in analysis as it is in combinatorics, even though analysis texts aren’t always clear that they’re making use of this fact. • If p(x) = ∑[n=0..∞] a_n x^n is a power series, then p(0) = a_0 is its constant term, but it makes no sense to write this unless 0^0 = 1. • The power rule d/dx [x^n] = n x^(n−1) holds for n = 1 and x = 0, but this requires 0^0 = 1. The reason that some people believe it’s important to undefine 0^0 in analysis is that the limiting expression lim[x → a] f(x)^g(x) does not necessarily exist when lim[x → a] f(x) = lim[x → a] g(x) = 0. But all this means is that we have to draw a distinction between the _value_ 0^0, which equals 1, and the indeterminate _limiting form_ 0^0, which is an abbreviation for the above type of limit. It is not uncommon for values to evaluate differently from the corresponding limiting forms. For example, the value floor(0) equals 0, but the limiting form floor(0) is indeterminate. It may seem surprising that such a discrepancy arises for exponentiation, but all it means is that exponentiation is discontinuous at (0, 0), as it must be. (Note however that the above limit _does_ exist with mild conditions on f and g: if f, g are complex analytic functions with f not identically zero, then the limit equals 1.) See also Donald Knuth’s _Two notes on notation_: http://arxiv.org/abs/math/9205211 http://arxiv.org/abs/math/9205211.
  - altrego99 12y ago
    Defining 0^0=1 has issues. Example: a(n)=1/exp(n), b(n)=1/n. Then both a and b converge to 0, but a^b is always exp(-1) (and hence does not converge to 1).
    - anderskaseorg 12y ago
      What you have shown is that the _limiting form_ 0^0 is not always equal to 1. The _value_ 0^0 is still equal to 1. Similarly, floor(−1/n) converges to −1, which tells us that the _limiting form_ floor(0) is not always equal to 0; but the _value_ floor(0) is still equal to 0. Nobody uses this to argue that the value of floor(0) should be undefined or context-dependent.
      - altrego99 12y ago
        Because floor is a discontinuous function. But you are right, what I meant is there is no way to define 0^0 maintaining continuity of the power function. Why is this important? Because power is a continuous function otherwise.
        anderskaseorg 12y ago
        Similarly, there is no way to define floor(n) for integers n maintaining continuity of the floor function, even though floor is a continuous function otherwise. We still define floor(n) = n because the meaning of the floor function is more important than its continuity. And so it is with exponentiation at (0, 0).
Flockster 12y ago
In school it was explained through combinatorics, where the factorial among others tells, in how many ways you can order your set. And an empty set has just one, but it has one, order in which it can be arranged. Now that I am writing this, I'm losing confidence, that this explanation is mathematically correct..
- johndcook 12y ago
  That is the usual explanation, but I don't think that helps much since counting the number of ways to arrange nothing is confusing!
  - ThrustVectoring 12y ago
    Not as confusing as you'd think, though, if you invoke the rule of product. The number of ways to do A and then B is the number of ways to do A times the number of ways to do B. The number of ways to do nothing and then A should be the same as the number of ways to do A. This implies that the number of ways to do nothing is the multiplicative identity, one.
jameshart 12y ago
Isn't it just a special case of the idea that the product of an empty sequence is 1?
- johndcook 12y ago
  Almost, but not quite. You could say "n! is the product of the natural numbers <= n." By this definition 0! is an empty product because there are no natural numbers <= 0. 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.
  - itsjareds 12y ago
    Could you then modify the definition to "for all n >= 0, n! is the product of natural numbers <= n"? That sounds kind of like the definition "f(0) = 1; f(n) = (n-1)! * n, n > 0".
  - matchu 12y ago
    That's just because we need to define the set more gracefully: "n! is the product of the first n natural numbers". The negative factorial issue arises from a slightly awkward specification of the set, not from jameshart's core idea.
  - rbehrends 12y ago
    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.)
  - 12y ago
hirak99 12y ago
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't fit, we would still be free to define 0! as 1 as a convention. But the fact that everything fits, makes it a useful definition - prevents you from checking a lot of edge cases, eliminating the need of many ``if (k==0) ...`` from codes.
- miningold 12y ago
  For a second there it looked like you were saying that (n-1) does not equal n!/n.
  - evanb 12y ago
    The way I know P!=NP is that N=(P-1)! Of course P=NP if P=0 or N=1. So who knows. :)
- sergeio 12y ago
  By that logic, (-1)! = 0!/0 = 1/0 = infinity, no?
  - thaumasiotes 12y ago
    Well, nobody has ever said that 1/0 will get you infinity, because it won't. Interpreted directly, it's an illegal operation, and there is no result because the computation is impossible. Sure enough, the gamma function doesn't exist at nonpositive integers. But wait! If you interpret 1/0 in a limit sense... there is no result, because there's no constraint that the neighborhood of 0 is entirely positive or entirely negative (obviously, the neighborhood of 1 is entirely positive). You'd only get an answer of "infinity" if you were limiting a function like "1 / 0^2". Sure enough, we see that the gamma function has no limit at the nonpositive integers, always approaching positive infinity from one side and negative infinity from the other side. So the factorial of a negative integer doesn't exist. What point are you trying to make?
pervycreeper 12y ago
See also Emil Artin's elegant pamphlet, "The Gamma Function".
- rspeer 12y ago
  It's awesome and weird that there's a consistent and useful function that lets you define an equivalent to (-1/2)! -- and that what you get is the square root of pi.
  - SamReidHughes 12y ago
    Of course it has pi in it. Otherwise it'd have to have e in it.
  - mturmon 12y ago
    I agree. The Stirling formula is another place where the square root of pi pops out from factorials.
gorhill 12y ago
I thought this video explained it very well: https://www.youtube.com/watch?v=Mfk_L4Nx2ZI https://www.youtube.com/watch?v=Mfk_L4Nx2ZI
deleted 12y ago
[deleted]
strategy 12y ago
For fun you can try out non-integral factorial values. For example, type in (1/2)! into WolframAlpha or Google, and you'll find the answer is the square root of pi over 2. This is due to the gamma function extension: https://www.youtube.com/watch?v=QhDDpSju3uY https://www.youtube.com/watch?v=QhDDpSju3uY
Houshalter 12y ago
I tried to fit a simpler function to the (logarithm of) factorial function with symbolic regression: http://i.imgur.com/9UJCDxT.png?1 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.
- jakeogh 12y ago
  Interesting! What software is that?
  - Houshalter 12y ago
    It's Eureqa: http://www.nutonian.com/products/eureqa/ http://www.nutonian.com/products/eureqa/ which is fantastic for what it does.
rbehrends 12y ago
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.

35 points by tacon 12y ago

0! Is whatever makes sense in context, like any other defintion. Arguing about what it should be "in general" is treating math like reality television, and it makes you dumber. O! Isn't a big controversy, but the idiocy surrounding O^0 (which is usefully different in combinatorics vs in analysis) is mind-boggling.

anderskaseorg 12y ago
Defining 0^0 = 1 is just as important in analysis as it is in combinatorics, even though analysis texts aren’t always clear that they’re making use of this fact. • If p(x) = ∑[n=0..∞] a_n x^n is a power series, then p(0) = a_0 is its constant term, but it makes no sense to write this unless 0^0 = 1. • The power rule d/dx [x^n] = n x^(n−1) holds for n = 1 and x = 0, but this requires 0^0 = 1. The reason that some people believe it’s important to undefine 0^0 in analysis is that the limiting expression lim[x → a] f(x)^g(x) does not necessarily exist when lim[x → a] f(x) = lim[x → a] g(x) = 0. But all this means is that we have to draw a distinction between the _value_ 0^0, which equals 1, and the indeterminate _limiting form_ 0^0, which is an abbreviation for the above type of limit. It is not uncommon for values to evaluate differently from the corresponding limiting forms. For example, the value floor(0) equals 0, but the limiting form floor(0) is indeterminate. It may seem surprising that such a discrepancy arises for exponentiation, but all it means is that exponentiation is discontinuous at (0, 0), as it must be. (Note however that the above limit _does_ exist with mild conditions on f and g: if f, g are complex analytic functions with f not identically zero, then the limit equals 1.) See also Donald Knuth’s _Two notes on notation_: http://arxiv.org/abs/math/9205211 http://arxiv.org/abs/math/9205211.
- altrego99 12y ago
  Defining 0^0=1 has issues. Example: a(n)=1/exp(n), b(n)=1/n. Then both a and b converge to 0, but a^b is always exp(-1) (and hence does not converge to 1).
  - anderskaseorg 12y ago
    What you have shown is that the _limiting form_ 0^0 is not always equal to 1. The _value_ 0^0 is still equal to 1. Similarly, floor(−1/n) converges to −1, which tells us that the _limiting form_ floor(0) is not always equal to 0; but the _value_ floor(0) is still equal to 0. Nobody uses this to argue that the value of floor(0) should be undefined or context-dependent.
    - altrego99 12y ago
      Because floor is a discontinuous function. But you are right, what I meant is there is no way to define 0^0 maintaining continuity of the power function. Why is this important? Because power is a continuous function otherwise.
      - anderskaseorg 12y ago
        Similarly, there is no way to define floor(n) for integers n maintaining continuity of the floor function, even though floor is a continuous function otherwise. We still define floor(n) = n because the meaning of the floor function is more important than its continuity. And so it is with exponentiation at (0, 0).

Flockster 12y ago

In school it was explained through combinatorics, where the factorial among others tells, in how many ways you can order your set. And an empty set has just one, but it has one, order in which it can be arranged. Now that I am writing this, I'm losing confidence, that this explanation is mathematically correct..

johndcook 12y ago
That is the usual explanation, but I don't think that helps much since counting the number of ways to arrange nothing is confusing!
- ThrustVectoring 12y ago
  Not as confusing as you'd think, though, if you invoke the rule of product. The number of ways to do A and then B is the number of ways to do A times the number of ways to do B. The number of ways to do nothing and then A should be the same as the number of ways to do A. This implies that the number of ways to do nothing is the multiplicative identity, one.

jameshart 12y ago

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

johndcook 12y ago
Almost, but not quite. You could say "n! is the product of the natural numbers <= n." By this definition 0! is an empty product because there are no natural numbers <= 0. 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.
- itsjareds 12y ago
  Could you then modify the definition to "for all n >= 0, n! is the product of natural numbers <= n"? That sounds kind of like the definition "f(0) = 1; f(n) = (n-1)! * n, n > 0".
- matchu 12y ago
  That's just because we need to define the set more gracefully: "n! is the product of the first n natural numbers". The negative factorial issue arises from a slightly awkward specification of the set, not from jameshart's core idea.
- rbehrends 12y ago
  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.)
- 12y ago

hirak99 12y ago

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't fit, we would still be free to define 0! as 1 as a convention. But the fact that everything fits, makes it a useful definition - prevents you from checking a lot of edge cases, eliminating the need of many ``if (k==0) ...`` from codes.

miningold 12y ago
For a second there it looked like you were saying that (n-1) does not equal n!/n.
- evanb 12y ago
  The way I know P!=NP is that N=(P-1)! Of course P=NP if P=0 or N=1. So who knows. :)
sergeio 12y ago
By that logic, (-1)! = 0!/0 = 1/0 = infinity, no?
- thaumasiotes 12y ago
  Well, nobody has ever said that 1/0 will get you infinity, because it won't. Interpreted directly, it's an illegal operation, and there is no result because the computation is impossible. Sure enough, the gamma function doesn't exist at nonpositive integers. But wait! If you interpret 1/0 in a limit sense... there is no result, because there's no constraint that the neighborhood of 0 is entirely positive or entirely negative (obviously, the neighborhood of 1 is entirely positive). You'd only get an answer of "infinity" if you were limiting a function like "1 / 0^2". Sure enough, we see that the gamma function has no limit at the nonpositive integers, always approaching positive infinity from one side and negative infinity from the other side. So the factorial of a negative integer doesn't exist. What point are you trying to make?

pervycreeper 12y ago

See also Emil Artin's elegant pamphlet, "The Gamma Function".

rspeer 12y ago
It's awesome and weird that there's a consistent and useful function that lets you define an equivalent to (-1/2)! -- and that what you get is the square root of pi.
- SamReidHughes 12y ago
  Of course it has pi in it. Otherwise it'd have to have e in it.
- mturmon 12y ago
  I agree. The Stirling formula is another place where the square root of pi pops out from factorials.

gorhill 12y ago

I thought this video explained it very well: https://www.youtube.com/watch?v=Mfk_L4Nx2ZI https://www.youtube.com/watch?v=Mfk_L4Nx2ZI

deleted 12y ago

[deleted]

strategy 12y ago

For fun you can try out non-integral factorial values. For example, type in (1/2)! into WolframAlpha or Google, and you'll find the answer is the square root of pi over 2. This is due to the gamma function extension: https://www.youtube.com/watch?v=QhDDpSju3uY https://www.youtube.com/watch?v=QhDDpSju3uY

Houshalter 12y ago

I tried to fit a simpler function to the (logarithm of) factorial function with symbolic regression: http://i.imgur.com/9UJCDxT.png?1 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.

jakeogh 12y ago
Interesting! What software is that?
- Houshalter 12y ago
  It's Eureqa: http://www.nutonian.com/products/eureqa/ http://www.nutonian.com/products/eureqa/ which is fantastic for what it does.

rbehrends 12y ago

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.