On Stirling’s approximation

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

lnn!=nlnnn+O(lnn). I wasn’t too happy with the O(lnn), and I wanted to know a better approximation, at least asymptotically.

In Mathematica, I started by calculating that

limnlnn!(nlnnn)lnn=12, so nlnnn+12lnn is a o(lnn)-good estimate. Next, limnlnn!(nlnnn+12lnn)1=12ln(2π), thus lnn!=nlnnn+12lnn+12ln(2π)+o(1). The term hiding in the o(1) is not insignificant, but it is the case that for all n1, lnn!(nlnnn+12lnn+12ln(2π))0.0811. This error goes to less than 0.01 for n9.

Anyway, going back to the Wikipedia article I noticed the “simple bound” 2πnn+12enn!, 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

log2n!=nlog2n(ln2)1n+12log2n+log22π+o(1). We can identify nlog2n as being the number of bits to record the permutation σ in a naive way, which is to write down the list σ(1),σ(2),,σ(n). The rest is a mysterious correction. Maybe it is something like, in reality, the ith number in the list only needs log2(ni+1) bits since i1 numbers are already excluded. Half the numbers use all m=log2(n) bits, a quarter can get away with m1 bits, an eighth use m2 bits, and so on. In the ideal case where n is a power of two 2m, this gives an upper bound of nlog2nn+1. This gets partly the way to (ln2)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 12n(n1). This gives a silly bound on the number of bits to store a permutation, which is 12n(n1)log2(n1).