13
$\begingroup$

I know that the Fibonacci sequence can be described via the Binet's formula.

However, I was wondering if there was a similar formula for $n!$.

Is this possible? If not, why not?

  • 7
    $\Gamma(n+1)$... does it count? :p2010-07-21
  • 4
    It would be interesting to see an answer that does not involve integration.2010-07-21
  • 6
    Why do you not consider "n!" a closed form? :-)2010-07-28
  • 0
    @ShreevatsaR: Well, because the n! is formally defined as $n!=\prod_{k=1}^n k$, which is not closed form. http://en.wikipedia.org/wiki/Closed-form_expression `an expression is said to be a closed-form expression if, and only if, it can be expressed analytically in terms of a bounded number of certain "well-known" functions.`2010-07-29
  • 4
    @John Gietzen: Yes I know, but the point is, "n!" *is* usually considered among the "well-known" functions (and integrals often aren't!): it's conventional to say that you have a closed form solution even when it includes binomial coefficients $n \choose k$. Of course, the meaning of "closed form" always depends on which functions you include among "well-known", but I find the choice of omitting n! unconventional, hence the previous question with a smiley.2010-07-29
  • 0
    I have retagged the question because you are looking for efficient algorithms - not a "closed form". I hope you update the question too.2010-09-11

4 Answers 4

10

If you're willing to accept an integral as an answer, then $n! = \int_0^\infty t^n e^{-t} \: dt$.

  • 1
    for reference: http://en.wikipedia.org/wiki/Gamma_function2010-07-21
  • 0
    Really, I'm looking for something whose complexity to calculate is better than $O\left( n\right)$2010-07-21
  • 1
    @Akhil, log(n!) is not in O(n) -- [look at the graphs for the "derivative" of log(n!)](http://dl.dropbox.com/u/1164414/SO/derivative%20of%20log%28fac%20n%29.gif), that's all but flat in areas of interest.2010-07-21
  • 0
    @John, I assume you mean better than O(n) multiplications. The trivial lower bound is O(n log n) see comment above. If you need a way to calculate factorials, factor n!, and then multiply is generally better than the native method. See here http://www.luschny.de/math/factorial/FastFactorialFunctions.htm2010-07-21
  • 0
    @Mgccl, indeed I did. I guess I was just assuming that multiplications on a modern PC is a single clock cycle. That breaks down when dealing with large enough factorials that it would matter, tho.2010-07-21
  • 0
    @Akhil @Mgccl: If you are defining multiplication to be one operation, then how many bits the answer is proportional to is irrelevant; a straightforward n! calculation requires at least n k-bit multiplications. The OP is asking if it can be done better than that.2010-07-21
  • 0
    OK, fair enough -- apologies for the silliness.2010-07-21
  • 0
    This is indeed the only possible correct answer, apparently: (from Wikipedia) `There is, in fact, no such simple solution for factorials; any combination of sums, products, powers, exponential functions, or logarithms with a fixed number of terms will not suffice to express $n!$.`2010-07-22
  • 0
    Wikipedia does not cite a source for that claim2010-07-22
  • 0
    @BlueRaja: The proof is left to the reader.2010-07-23
  • 6
    This answer, while chosen as best, is hardly satisfying.2010-07-23
  • 0
    I know it's unsatisfying.2010-07-24
  • 1
    @John Gietzen: Nice quote. But, as all computer scientists know, "any combination of sums, products, powers, exponential functions, or logarithms with a fixed number of terms will not suffice to express $n$," either! (In our usual number systems, the number of terms needed to express a positive integer $n$ is asymptotically $\log(n)$.)2010-09-09
7

The relative error of Stirling's approximation gets arbitrarily small as n gets larger.

$$n!\sim\sqrt{2\pi n} \left(\frac{n}{e}\right)^n$$

However, it is only an approximation, not a closed-form of $n!$

  • 1
    @Harry: What makes you think he *purposely* misspelled it?2010-07-21
  • 0
    @Daniel: Because he did it right after linking a page!2010-07-21
6

Contrast these two methods for calculating n!:

  • Counting permutations of a n-element set one-by-one (this is what n! counts), vs.
  • Multiplying together the numbers 1,2,...,n.

Therefore n! represents an amazingly efficient method for counting permutations! So I think (and I don't think I'm the only one) that n! should probably be considered a closed form (unless you have some other clear definition of what constitutes a "closed" form).

For further reading, I recommend: H. S. Wilf, What is an answer?, Amer. Math. Monthly, 89 (1982), pp. 289–292, DOI: 10.2307/2321713, JSTOR.

  • 3
    For the interested: http://www.jstor.org/stable/23217132010-09-09
2

This is a riff on some of the comments about what might constitute an "answer" and what "closed form" might mean: although it's somewhat facetious, it's intended to prompt thoughts about these issues.

Our base-10 number system interprets a string ${a_n}{a_{n-1}} \cdots {a_0}$ as the sum $\sum_{i=0}^{n} a_i 10^i $ (which can be, and is, computed recursively as $a_0 + 10 \left( a_1 + 10 \left( \cdots + 10 a_n \right) \cdots \right)$). If you take the former to be an acceptable "closed form" representation, then why not use a slight modification of this number system? Specifically, interpret the same string as equal to $a_0 + 2 \left( a_1 + 3 \left( \cdots + (n+1) a_n \right) \cdots \right)$ and require that $0 \le a_0 \le 1, 0 \le a_1 \le 2, \ldots, 0 \le a_n \le n$. In this "factorial" number system, $n! = 10 \cdots 0$ is represented as a simple $n$-digit string: it's "closed"!