On Stirling’s approximation

When thinking about optimal codes for knot diagrams, I wanted a good approximation for ${\log }_2(n!)$. A natural thing to reach for is Stirling’s approximation, and the Wikipedia article helpfully gives

$$\ln n!=n\ln n-n+O\left(\ln n\right).$$ I wasn’t too happy with the $O\left(\ln n\right)$, and I wanted to know a better approximation, at least asymptotically.

In Mathematica, I started by calculating that

$$\underset{n\to \infty }{lim}\frac{\ln n!-(n\ln n-n)}{\ln n}=\frac{1}{2},$$ so $n\ln n-n+\frac{1}{2}\ln n$ is a $o\left(\ln n\right)$-good estimate. Next, $$\underset{n\to \infty }{lim}\frac{\ln n!-(n\ln n-n+\frac{1}{2}\ln n)}{1}=\frac{1}{2}\ln \left(2\pi \right),$$ thus $$\ln n!=n\ln n-n+\frac{1}{2}\ln n+\frac{1}{2}\ln \left(2\pi \right)+o\left(1\right).$$ The term hiding in the $o\left(1\right)$ is not insignificant, but it is the case that for all $n\ge 1$, $$\ln n!-(n\ln n-n+\frac{1}{2}\ln n+\frac{1}{2}\ln (2\pi \left)\right)\le \mathrm{0.0811.}$$ This error goes to less than $0.01$ for $n\ge 9$.

Anyway, going back to the Wikipedia article I noticed the “simple bound” $\sqrt{2\pi }{n}^{n+\frac{1}{2}}{e}^{-n}\le n!$, which as it turns out is from raising $e$ to the power of the above estimate. It is good to know that this simple bound is actually quite close.

Going back to the motivation, the number bits to optimally record a permutation of $n$ elements is

$${\log }_{2}n!=n{\log }_{2}n-(\ln 2{)}^{-1}n+\frac{1}{2}{\log }_{2}n+{\log }_2\sqrt{2\pi }+o(1).$$ We can identify $n{\log }_{2}n$ as being the number of bits to record the permutation $\sigma$ in a naive way, which is to write down the list $\sigma \left(1\right),\sigma \left(2\right),\dots ,\sigma \left(n\right)$. The rest is a mysterious correction. Maybe it is something like, in reality, the $i$th number in the list only needs ${\log }_2(n-i+1)$ bits since $i-1$ numbers are already excluded. Half the numbers use all $m={\log }_2\left(n\right)$ bits, a quarter can get away with $m-1$ bits, an eighth use $m-2$ bits, and so on. In the ideal case where $n$ is a power of two $2^m$, this gives an upper bound of $n{\log }_{2}n-n+1$. This gets partly the way to $(\ln 2{)}^{-1}$, but it is not all the way there.

Warning: the next section doesn’t really go anywhere.

Transposition decompositions. Every permutation is a product of permutations. My favorite way of seeing this is to draw a permutation as a diagram, where $2n$ points are at the top of the page and $2n$ points are at the bottom of the page, and there are lines connecting the top to the bottom, and they possibly intersect. If you straighten out the lines as much as possible and then make sure there are no triple points, this gives the decomposition as transpositions.

Every line can intersect every other line in the worst case, so an upper bound for the number of transpositions is $\frac{1}{2}n(n-1)$. This gives a silly bound on the number of bits to store a permutation, which is $\frac{1}{2}n(n-1){\log }_2(n-1)$.