|Journal of Integer Sequences, Vol. 20 (2017), Article 17.10.7|
Vadim E. Levit
Department of Computer Sciences
Borough of Manhattan Community College
The City University of New York
Department of Mathematics
a1a2 ... an-1 an = aπ1 aπ2 ... aπn-1 aπn
as π varies over all the permutations in Sn. The probability
Prπ(G) = Pr(a1a2 ... an-1 an = aπ1 aπ2 ... aπn-1 aπn)
is identical to Pr1ω(G), with
ω = a1a2 ... an-1 an aπ1-1 aπ2-1 ... aπn-1-1 aπn-1
which was defined and studied by Das and Nath. The notion of commutativity degree, or the probability of a permutation equality a1 a2 = a2 a1, for which n = 2 and π = ⟨ 2 1 ⟩, was introduced and assessed by Erdős and Turan in 1968 and by Gustafson in 1973. Gustafson established a relation between the probability of a1, a2 ∈ G commuting and the number of conjugacy classes in G. In this work we define several other parameters, which depend only on a certain interplay between the conjugacy classes of G, and compute probabilities of permutation equalities in terms of these parameters. It turns out that for a permutation π, the probability of its permutation equality depends only on the number c(Gr(π)) of alternating cycles in the cycle graph Gr(π) of π. The cycle graph of a permutation was introduced by Bafna and Pevzner, and the number of alternating cycles in it was introduced by Hultman. Hultman numbers are the numbers of different permutations with the same number of alternating cycles in their cycle graphs. We show that the spectrum of probabilities of permutation equalities in a generic finite group, as π varies over all the permutations in Sn, corresponds to partitioning n! as the sum of the corresponding Hultman numbers.
(Concerned with sequence
Received December 17 2015; revised versions received March 29 2017; October 31 2017. Published in Journal of Integer Sequences, November 22 2017.