Cardinality of Balls in Permutation Spaces

MaRDI QIDQ6239990zbMATH OpenFDO

Authors Liviu P. Dinu, Catalin Zara

Publication date 28 February 2013

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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.

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)