Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 9 down vote favorite
1

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?

share|improve this question
6  
$\Gamma(n+1)$... does it count? :p – KennyTM Jul 21 '10 at 19:22
3  
It would be interesting to see an answer that does not involve integration. – Justin L. Jul 21 '10 at 22:04
3  
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
2  
@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
show 1 more comment

4 Answers

up vote 6 down vote accepted

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

share|improve this answer
1  
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
1  
@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
6  
This answer, while chosen as best, is hardly satisfying. – Justin L. Jul 23 '10 at 22:05
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)$.) – whuber Sep 9 '10 at 18:02
show 8 more comments
up vote 6 down vote

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

(picture)

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

share|improve this answer
1  
@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
up vote 5 down vote

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.

share|improve this answer
2  
For the interested: jstor.org/stable/2321713 – J. M. Sep 9 '10 at 12:59
up vote 1 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.