# Why does $n!$ grow faster than $2^{n \log n}$

According to Wolfram Alpha the following holds: $$\lim_{n \rightarrow \infty} \frac{n!}{2^{n \log_2 n}} = \infty$$

However, by the following argumentation I would expect the limit to approach 0 (or at least not infinity).

• $n!$ counts the number of permutations of $n$ elements, that is $|S_n| = n!$
• $S_n$ is a subset of the set of all functions with the signature $f : [n] \rightarrow [n]$
• We can give a one-to-one correspondence between every function $f : [n] \rightarrow [n]$ and the set of all $n \log_2 n$ long bitstrings
• There exist $2^{n \log_2 n}$ different bitstrings of length $n \log_2 n$
• Therefore for all $n$ it must hold that $$n! \leq 2^{n \log_2 n}$$

From the last point it directly follows that the above limit shouldn't exceed 1.

Where is the flaw in this argumentation?

• You asked WA about $n!/2^{n \log n}$, not $n!/2^{n \log_2 n}$, hence WA is right. – Did May 6 '14 at 15:55

## 2 Answers

You are correct. $$2^{n\log_2 n}=n^n \ge n!$$

However what you entered into alpha was $$2^{n\ln n}=2^{n\ln 2 \log_2 n}=n^{n\ln 2}=(n^n)^{\ln 2}$$

More info. By Stirling's approximation, $$\lim_{n\to \infty} \frac{n!e^n}{\sqrt{2\pi n}n^n}=1$$ In other words, $$n!\sim \frac{\sqrt{2\pi n}n^n}{e^n}$$ Hence $$\frac{n!}{(n^n)^\alpha}\sim \frac{\sqrt{2\pi n}}{e^n}(n^n)^{1-\alpha}$$ This limit (as $n\to \infty$) is $\infty$ for $\alpha<1$, and $0$ for $\alpha\ge 1$. In the case in question $\alpha=\ln 2\approx 0.69$.

Note that wolfram alpha assumes base $e$. Your reasoning is correct. Note that $$2^{n\log_{2}n}=2{log_2{n^n}=n^n}$$

Try this and WA replies correctly. Just don't question WA.