6
$\begingroup$

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

$\endgroup$
5
  • $\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$ Aug 2, 2010 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$ Aug 2, 2010 at 5:39
  • $\begingroup$ For a stronger lower bound which implies yours, see mathoverflow.net/questions/27912/… . $\endgroup$ Aug 2, 2010 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$ Aug 2, 2010 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$ Aug 2, 2010 at 8:00

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Beautiful. Thanks! This also works in the odd $n$ case by fixing the median element. $\endgroup$ Aug 2, 2010 at 8:57
2
$\begingroup$

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...

$\endgroup$
2
  • $\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$ Aug 2, 2010 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$ Aug 2, 2010 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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