# Bijective proof of weak form of Stirling's approximation

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

-
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. –  Wadim Zudilin Aug 2 '10 at 5:31
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. –  Per Vognsen Aug 2 '10 at 5:39
For a stronger lower bound which implies yours, see mathoverflow.net/questions/27912/… . –  Wadim Zudilin Aug 2 '10 at 5:40
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. –  Per Vognsen Aug 2 '10 at 5:56
Btw, as to elementary forms of the Stirling inequality, note also $e^n\geq \frac{n^n}{n!}$ from the exponential series. –  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.
Beautiful. Thanks! This also works in the odd $n$ case by fixing the median element. –  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...