Blocks in cycles and k-commuting permutations

Abstract

Let $k$ be a nonnegative integer, and let $\alpha$ and $\beta$ be two permutations of $n$ symbols. We say that $\alpha$ and $\beta$ $k$-commute if $H(\alpha \beta ,\beta \alpha )=k$, where $H$ denotes the Hamming metric between permutations. In this paper, we consider the problem of finding the permutations that $k$-commute with a given permutation. Our main result is a characterization of permutations that $k$-commute with a given permutation $\beta$ in terms of blocks in cycles in the decomposition of $\beta$ as a product of disjoint cycles. Using this characterization, we provide formulas for the number of permutations that $k$-commute with a transposition, a fixed-point free involution and an $n$-cycle, for any $k$. Also, we determine the number of permutations that $k$-commute with any given permutation, for $k\le 4$.

25 pages. v3 is a major revision

References in corpus (6)

• Almost commuting permutations are near commuting permutations
• Almost commuting matrices with respect to normalized Hilbert-Schmidt norm
• A Hilbert-Schmidt analog of Huaxin Lin's Theorem
• Convex Structures Revisited
• Blocks in cycles and k-commuting permutations
• Polynomial sequences on quadratic curves

Cited by in corpus (4)

• Convex Structures Revisited
• Blocks in cycles and k-commuting permutations
• On simultaneous conjugation of permutations
• Integer sequences and k-commuting permutations