We introduce and study k-commuting permutations. One of our main results is a characterization of permutations that k-commute with a given permutation. Using this characterization, we obtain formulas for the number of permutations that k-commute with a permutation [Formula: see text], for some cycle types of [Formula: see text]. Our enumerative results are related with integer sequences in "The On-line Encyclopedia of Integer Sequences", and in some cases provide new interpretations for such sequences.
Keywords: Commutation relation; Enumeration; Hamming metric; Symmetric group.