2016/05/11 by Karhumäki, Juhani, Puzynina, Svetlana, Rao, Michaël +1 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1605.03319
Two words u and v are k-abelian equivalent if, for each word x of length at most k, x occurs equally many times as a factor in both u and v. The notion of k-abelian equivalence is an intermediate notion between the abelian equivalence and the equality of words. In this paper, we study the equivalence classes induced by the k-abelian equivalence, mainly focusing on the cardinalities of the classes. In particular, we are interested in the number of singleton k-abelian classes, i.e., classes containing only one element. We find a connection between the singleton classes and cycle decompositions of the de Bruijn graph. We show that the number of classes of words of length n containing one single element is of order \mathcal O(nNm(k-1)-1), where Nm(l) = \tfrac1l∑d| l φ(d)ml/d is the number of necklaces of length l over an m-ary alphabet. We conjecture that the upper bound is sharp. We also remark that, for k even and m = 2, the lower bound Ω(nNm(k-1)-1) follows from an old conjecture on the existence of Gray codes for necklaces of odd length. We verify this conjecture for necklaces of length up to 15.