There are short and sweet proofs of various forms of Stirling's approximation. But even the sweetest among them don't instill the same conviction in the reader as a direct bijective proof.

Computer scientists can often get away with a very weak form of Stirling's approximation:

$$(n/2)^{n/2} \leq n! \leq n^n$$

From this follows

$$(n/2)\ log(n) - (n/2)\ log(2) \leq log(n!) \leq n\ log(n)$$

and therefore $log(n!) = \Theta(n\ log(n))$. This is sufficient to establish the lower bound on comparison-based sorting algorithms and many other asymptotic bounds.

Does anyone know a natural bijective proof of $(n/2)^{n/2} \leq n! \leq n^n$?

  • $\begingroup$ Why it's important to have a bijective proof?! I would be very happy to hear some motivation. Any way, if you wish to have some combinatorics involved, you should clarify how to interpret $(n/2)^{n/2}$ for $n$ odd. $\endgroup$ – Wadim Zudilin Aug 2 '10 at 5:31
  • $\begingroup$ For $n$ even, $n/2$ of the factors of $n!$ are at least $n/2$. So, the natural interpretation for $n$ odd is to round down $n/2$. But I would be happy with a bijective proof that only directly encompasses the even case. As for why I want a bijective proof? The usual reason of wanting to see the underlying combinatorial structure. $\endgroup$ – Per Vognsen Aug 2 '10 at 5:39
  • $\begingroup$ For a stronger lower bound which implies yours, see mathoverflow.net/questions/27912/… . $\endgroup$ – Wadim Zudilin Aug 2 '10 at 5:40
  • 1
    $\begingroup$ By the way, maybe I should mention my original intuition that the lower bound should have something to do with the existence of fixed-point-free involutions on sets of even cardinality. $\endgroup$ – Per Vognsen Aug 2 '10 at 5:56
  • $\begingroup$ Btw, as to elementary forms of the Stirling inequality, note also $e^n\geq \frac{n^n}{n!}$ from the exponential series. $\endgroup$ – Pietro Majer Aug 2 '10 at 8:00

Think of all maps from the first $n/2$ elements of {$1,...,n$} to the last $n/2$. Say, let $a_1< \ldots < a_k \to z$. Make a cycle $a_1 \to a_2 \to \ldots \to a_k \to z \to a_1$. Do this for all $z$. The details are straightforward. This proves the lower bound.

  • $\begingroup$ Beautiful. Thanks! This also works in the odd $n$ case by fixing the median element. $\endgroup$ – Per Vognsen Aug 2 '10 at 8:57

n! counts one-to-one functions from {1,2,...,n} to itself while $n^n$ counts all such functions. For a bijective proof of the lower bound one would likely want n=2m, Then the lower number is the $m^m$ functions g from {1,...,m} to itself . I thought I had an easy bijection to a class of partial one-to-one functions but the on I had isn't right...

  • $\begingroup$ Yeah, the upper bound poses no problem. I too have had a couple of false starts on a bijective proof of the lower bound, so I'm sympathetic to your mistake. :) $\endgroup$ – Per Vognsen Aug 2 '10 at 5:19
  • $\begingroup$ OK, its not so pretty but one-to-one functions from {1,...,m} to {1,...,n} number n*(n-1)*...*(m+1) and all m terms are greater than m. So take any of the m^m functions g from {1..m} to itself and make a function f by assigning in turn f(1),f(2),... where f(i) is the g(i)th in order from the things not already assigned. $\endgroup$ – Aaron Meyerowitz Aug 2 '10 at 5:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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