Intuition Behind Necklace Formula

Wikipedia and Wolfram MathWorld say that the formula for the number of distinct $k$-ary necklaces of length $n$ is:

$$N_k(n) = \frac{1}{n}\sum_{d|n} {\phi(d)k^{n/d}}$$

What is the intuition behind this formula?

• Nice question! I've been dealing with this formula for some 10 years, and still I've never asked myself if there is a bijective proof (after multiplication by $n$ on both sides). The standard proof goes via the Möbius-function formula for the aperiodic necklaces, so there are minus signs floating in. (Something with the Burrows-Wheeler algorithm, or its friend the Gessel-Reutenauer algorithm perhaps?) Dec 2 '17 at 4:34
• Maybe by using Burnside's lemma (math.stackexchange.com/q/75428) ? Dec 2 '17 at 22:40

Use the commutativity of Dirichlet convolution

$$n N_k(n)= \sum_{d |n} k^{n/d} \phi(d) = \sum_{d |n} k^{n/d} \sum_{l | d} \mu(l) \frac{d}{l} =\sum_{d |n} \frac{n}{d} \sum_{l | d} \mu(l) k^{d/l}$$

where

• $k^n$ is the number of $n$-periodic $k$-ary sequences

• $f_k(n)=\sum_{l | n} \mu(l) k^{n/l}$ (Möbius inversion) is the number of periodic $k$-ary sequences whose least period is $n$

• $\frac{1}{n} f_k(n)$ is the number of $k$-ary sequences whose least period is $n$ and quotiented by the shift equivalence

• $\sum_{d | n} \frac{f_k(d)}{d}$ is the number of $k$-ary sequences whose period $| n$ and quotiented by the shift equivalence, ie. the number of necklaces of length $n$.

• He wants an intuition, though, which I'd interpret as something that doesn't involve solving a different problem as a stepping stone :) Dec 3 '17 at 8:24
• @darijgrinberg ?? This is the intuition behind the formula : we are counting the number of periodic sequences of some given least period. If you have a better idea, show us. Dec 3 '17 at 8:28
• Or if you prefer, I don't agree $\frac{1}{n}\sum_{d | n} k^{n/d} \phi(d)$ is the necklace formula, IMO it is $N_k(n ) = \sum_{d | n} \frac{f_k(d)}{d}$ where $f_k(n) = \sum_{d | n} \mu(d) k^{n/d}$. @darijgrinberg Dec 3 '17 at 8:35
• Great answer and thanks for the response, but I'm really looking for an interpretation of the formula itself without manipulating it. You give an interpretation for another formula which you show is equivalent to the one in question, but I'm looking for a direct interpretation of that formula. Dec 4 '17 at 15:52
• @EyobTsegaye This is the interpretation : $\frac{1}{n}\sum_{d | n} k^{n/d} \phi(d)$ is an obfuscated version of $\sum_{d |n} \frac{1}{d} \sum_{l | d} \mu(l) k^{d/l}$, which is easily understood. I really doubt you'll find something clearer. Dec 4 '17 at 15:56