Cardinality of Balls in Permutation Spaces

For a right invariant distance on a permutation space $S_n$ we give a sufficient condition for the cardinality of a ball of radius $R$ to grow polynomially in $n$ for fixed $R$. For the distance ${\mathrm{\ell }}_1$ we show that for an integer $k$ the cardinality of a sphere of radius $2k$ in $S_n$ (for $n \geqslant k$)isapolynomialofdegree$k$in$n$ and determine the high degree terms of this polynomial.