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?

  • 0
    I have retagged the questio$n$ because you are looking for efficient algorith$m$s - $n$ot 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
    @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!$

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