Cardinality of Balls in Permutation Spaces

arXiv1303.0016MaRDI QIDQ6239990FDOQ6239990

Authors: Liviu P. Dinu, Catalin Zara 

Publication date: 28 February 2013

Abstract: 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 $el{l}_1$ we show that for an integer $k$ the cardinality of a sphere of radius $2k$ in $S_n$ (for $ngeqslantk$) is a polynomial of degree $k$ in $n$ and determine the high degree terms of this polynomial.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

This page was built for publication: Cardinality of Balls in Permutation Spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239990)