4
$\begingroup$

I consider k-ary strings of the form $a_1 \cdots a_n$ where $a_i \in \{0,\ldots,k-1\}$ for $1\le i \le n$. A necklace is the lexicographically smallest representative of an equivalence class where two strings are said to be equivalent if one is a rotation of the other (wiki). The number of all necklaces can be counted using Polya's enumeration theorem.

Now, let $1 \le j \le n$ be fixed. What is the number of necklaces with the additional constraint $a_j = k-1$? Is there a closed form expression for this number?

$\endgroup$
4
  • $\begingroup$ When you say $a_j$, do you refer to the lexicographically smallest representative of a necklace? $\endgroup$ Mar 29 '19 at 20:21
  • $\begingroup$ Yes exactly. E.g., for $j=1$ there is only one representative while for $j=n$ there are as many as there are prenecklaces of size $n-1$ (The latter follows from, e.g. theorem 2.1 in Journal of Algorithms 37, 267 (2000)). $\endgroup$
    – Marc
    Mar 29 '19 at 21:01
  • 1
    $\begingroup$ Then this question is more about Lyndon words than necklaces. $\endgroup$ Mar 29 '19 at 22:42
  • 1
    $\begingroup$ Let $L(n,t)$ be the number of Lyndon words of length $n$ with $k-1$ at position $t+1$. You essentially ask for the number $\sum_{d|n} L(d,(j-1)\bmod d)$. $\endgroup$ Mar 30 '19 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.