# Count necklaces with fixed substring

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?

• When you say $a_j$, do you refer to the lexicographically smallest representative of a necklace? Mar 29 '19 at 20:21
• 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)).
– Marc
Mar 29 '19 at 21:01
• Then this question is more about Lyndon words than necklaces. Mar 29 '19 at 22:42
• 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)$. Mar 30 '19 at 13:25