How do you prove that $n^n$ is $O(n!^2)$? It seems obvious that:
$$n^n \in O(n!^2)$$
But I can't seem to find a good way to prove it.
 A: Use a multiplicative variant of Gauss's trick:
$$
(n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots
                ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1)
                \ge n^n
$$
A: This also follows straightforwardly from the simple inequality
$$
e\bigg(\frac{n}{e}\bigg)^n  \le n!,
$$
which can be found here (Wikipedia).
Elaborating: From this inequality it follows in particular that
$$
n!n! \ge \frac{{n^n n^n }}{{e^n e^n }} = \bigg(\frac{n}{{e^2 }}\bigg)^n n^n ,
$$
hence
$$
n^n  \le \bigg(\frac{{e^2 }}{n}\bigg)^n n!n!,
$$
showing moreover that $n^n \in o(n!^2)$.
EDIT: Here (Math Central, Problem of the Month 100, December 2010) you can find five different proofs of the inequality $(n!)^2  > n^n $, for all $n \geq 3$ or $n \geq 8$.
EDIT: Actually, for the above proof it suffices to use the inequality $n! > (\frac{n}{e})^n$  (cf. the comments below), which is trivial noting that 
$$
e^n  = \sum\limits_{k = 0}^\infty  {\frac{{n^k }}{{k!}}}  > \frac{{n^n }}{{n!}}.
$$
A: Group factors $k$ and $n-k$. When is their product bigger than $n$?
