MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 2010 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 2010 at 5:39
For a stronger lower bound which implies yours, see mathoverflow.net/questions/27912/… . – Wadim Zudilin Aug 2 2010 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 2010 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 2010 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 2010 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...

-
 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. :) – Per Vognsen Aug 2 2010 at 5:19 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. – Aaron Meyerowitz Aug 2 2010 at 5:32