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



Bijective proof of weak form of Stirling's approximation
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. 


