Is $n! = o(n^n)$? Intuitively, it seems that $n! = o(n^n)$. We can associate each value in the factorial with a single $n$ to divide by, so $\lim_{n \rightarrow \infty} \frac{n!}{n^n}$ seems to be $0$.
However, I think I have encountered a contradiction. It turns out that $\log(n!) = \Theta(n\log{n})$ (which we can show with Stirling's approximation) or $\log(n!) = \Theta(\log{n^n})$. The log function is strictly increasing, so we can just remove them, so that means that $n! = \Theta(n^n)$, which goes against my earlier hunch of $n! = o(n^n)$.
I must be missing something, right?
 A: $${n!\over n^n}={1\cdot 2\cdots n\over n\cdot n\cdots n}\leq {1\over n}.$$
A: Just because the log function is strictly increasing doesn't mean it preserves asymptotics! For a simple example of this, note that $\log(3^n)=\frac{\log 3}{\log 2}\log(2^n)$, and so $\log(3^n)$ is $\Theta(2^n)$. However, $3^n$ is clearly not $\Theta(2^n)$. 
Essentially, if $\log f(n)$ is $\Theta(\log(g(n))$, that means $f(n)/g(n)$ is exponential or smaller.
A: Let 
$$u_n=\frac{n!}{n^n}$$
then 
$$\frac{u_{n+1}}{u_n}=\left(1+\frac 1 n\right)^{-n}\to e^{-1}<1$$
so by ratio test the series $\sum u_n$ is convergent so $u_n\to0$ and the desired result follows.
A: Hint: Stirling's approximation states that
$$ n! \operatorname*{\sim}_{n\to\infty} \frac{1}{\sqrt{2\pi n}}\frac{n^n}{e^n}$$
so $\frac{n!}{n^n}\xrightarrow[n\to\infty0]{} 0$. Your problem is that you cannot take the exponential of equivalents. For instance, take $f(n)=n$, $g(n)=n+\sqrt(n)$. Clearly, $f(n)\sim g(n)$, yet
$$ e^{g(n)} = e^{n+\sqrt{n}} = e^{f(n)}e^{\sqrt n} = \omega\left(e^{f(n)}\right)$$
A: If you take the log of Stirling's formula, you get
$$\log(n!) \approx n\log n - n + \tfrac{1}{2}\log n + \tfrac{1}{2}\log 2\pi$$
You are keeping only the leading term, $n\log n$, in your question. If you take the difference of the logs (to get handle on the ratio of the original quantities), you get
$$\log(n!)-\log(n^n)\approx -n + \text{ lower order terms}$$
Note that as $n\rightarrow\infty$, this does indeed tend to $-\infty$. So the original ratio tends to 0.
