Bounds on the Size of Balls over Permutations with the Infinity Metric

We study the size (or volume) of balls in the metric space of permutations, S-n, under the infinity metric. We focus on the regime of balls with radius r = rho.(n-1), rho is an element of [0, 1], i.e., a radius that is a constant fraction of the maximum possible distance. We provide new bounds on the size of such balls. These bounds reduce the asymptotic gap between the upper and lower bound to at most 0.06 bits per symbol.