{
  "id": "1605.03319",
  "version": "v1",
  "published": "2016-05-11T08:08:46.000Z",
  "updated": "2016-05-11T08:08:46.000Z",
  "title": "On cardinalities of $k$-abelian equivalence classes",
  "authors": [
    "Juhani Karhumäki",
    "Svetlana Puzynina",
    "Michaël Rao",
    "Markus A. Whiteland"
  ],
  "comment": "21 pages, 4 figures, 2 tables",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "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(n^{N_m(k-1)-1})$, where $N_m(l) = \\tfrac{1}{l}\\sum_{d\\mid l} \\varphi(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 $\\Omega(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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-11T08:08:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "abelian equivalence classes",
      "cardinalities",
      "conjecture",
      "lower bound",
      "upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}