TCS Journal 2017 Journal Article
On cardinalities of k-abelian equivalence classes
- Juhani Karhumäki
- Svetlana Puzynina
- Michaël Rao
- Markus A. Whiteland
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 O ( n N m ( k − 1 ) − 1 ), where N m ( l ) = 1 l ∑ d | l φ ( d ) m l / 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 Ω ( n N m ( 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.