On Stirling’s approximationI wasn’t too happy with the , and I wanted to know a better approximation, at least asymptotically.
In Mathematica, I started by calculating thatso is a -good estimate. Next, thus The term hiding in the is not insignificant, but it is the case that for all , This error goes to less than for .
Anyway, going back to the Wikipedia article I noticed the “simple bound” , which as it turns out is from raising 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 elements isWe can identify as being the number of bits to record the permutation in a naive way, which is to write down the list . The rest is a mysterious correction. Maybe it is something like, in reality, the th number in the list only needs bits since numbers are already excluded. Half the numbers use all bits, a quarter can get away with bits, an eighth use bits, and so on. In the ideal case where is a power of two , this gives an upper bound of . This gets partly the way to , 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 points are at the top of the page and 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 . This gives a silly bound on the number of bits to store a permutation, which is .