# Is there a closed-form equation for $n!$? If not, why not?

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?

-
$\Gamma(n+1)$... does it count? :p – kennytm Jul 21 '10 at 19:22
It would be interesting to see an answer that does not involve integration. – Justin L. Jul 21 '10 at 22:04
Why do you not consider "n!" a closed form? :-) – ShreevatsaR Jul 28 '10 at 22:40
@ShreevatsaR: Well, because the n! is formally defined as $n!=\prod_{k=1}^n k$, which is not closed form. 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. – John Gietzen Jul 29 '10 at 13:50
@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. – ShreevatsaR Jul 29 '10 at 14:10

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

-
for reference: en.wikipedia.org/wiki/Gamma_function – balpha Jul 21 '10 at 19:38
Really, I'm looking for something whose complexity to calculate is better than $O\left( n\right)$ – John Gietzen Jul 21 '10 at 19:38
@Akhil, log(n!) is not in O(n) -- look at the graphs for the "derivative" of log(n!), that's all but flat in areas of interest. – badp Jul 21 '10 at 21:00
This answer, while chosen as best, is hardly satisfying. – Justin L. Jul 23 '10 at 22:05
@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)$.) – whuber Sep 9 '10 at 18:02

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!$

-
@Harry: What makes you think he purposely misspelled it? – Daniel Egeberg Jul 21 '10 at 19:43
Whoops, mah bad – BlueRaja - Danny Pflughoeft Jul 21 '10 at 20:01
@Daniel: Because he did it right after linking a page! – user126 Jul 21 '10 at 21:54

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.

-
For the interested: jstor.org/stable/2321713 – J. M. Sep 9 '10 at 12:59

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"!

-