16
$\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?

$\endgroup$
7
  • 7
    $\begingroup$ $\Gamma(n+1)$... does it count? :p $\endgroup$
    – kennytm
    Commented Jul 21, 2010 at 19:22
  • 4
    $\begingroup$ It would be interesting to see an answer that does not involve integration. $\endgroup$
    – Justin L.
    Commented Jul 21, 2010 at 22:04
  • 6
    $\begingroup$ Why do you not consider "n!" a closed form? :-) $\endgroup$
    – ShreevatsaR
    Commented Jul 28, 2010 at 22:40
  • 1
    $\begingroup$ @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. $\endgroup$
    – John Gietzen
    Commented Jul 29, 2010 at 13:50
  • 4
    $\begingroup$ @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. $\endgroup$
    – ShreevatsaR
    Commented Jul 29, 2010 at 14:10

4 Answers 4

Reset to default
16
$\begingroup$

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

$\endgroup$
13
  • 1
    $\begingroup$ for reference: en.wikipedia.org/wiki/Gamma_function $\endgroup$
    – balpha ♦
    Commented Jul 21, 2010 at 19:38
  • 1
    $\begingroup$ Really, I'm looking for something whose complexity to calculate is better than $O\left( n\right)$ $\endgroup$
    – John Gietzen
    Commented Jul 21, 2010 at 19:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – badp
    Commented Jul 21, 2010 at 21:00
  • 7
    $\begingroup$ This answer, while chosen as best, is hardly satisfying. $\endgroup$
    – Justin L.
    Commented Jul 23, 2010 at 22:05
  • 1
    $\begingroup$ @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)$.) $\endgroup$
    – whuber
    Commented Sep 9, 2010 at 18:02
11
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ @Harry: What makes you think he purposely misspelled it? $\endgroup$
    – Daniel Egeberg
    Commented Jul 21, 2010 at 19:43
  • $\begingroup$ @Daniel: Because he did it right after linking a page! $\endgroup$
    – user126
    Commented Jul 21, 2010 at 21:54
8
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ For the interested: jstor.org/stable/2321713 $\endgroup$
    – J. M. ain't a mathematician
    Commented Sep 9, 2010 at 12:59
  • $\begingroup$ Article behind paywall. $\endgroup$
    – Albert Renshaw
    Commented Jan 24, 2020 at 4:46
  • $\begingroup$ @AlbertRenshaw Pure, unadulterated, raw information usually is. Despite the fact its inherent to the universe, anyone could conceivably discover the laws... someone in academia (where peer review is supposedly important and vital) tries to horde the information from others. Inexplicable and anti-intellectual $\endgroup$
    – CogitoErgoCogitoSum
    Commented Aug 29, 2020 at 17:31
4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .