3
$\begingroup$

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?

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.