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

bijectiveproof?! 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