6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – darij grinberg Dec 2 '17 at 4:34
  • $\begingroup$ Maybe by using Burnside's lemma (math.stackexchange.com/q/75428) ? $\endgroup$ – Jean Marie Dec 2 '17 at 22:40
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ He wants an intuition, though, which I'd interpret as something that doesn't involve solving a different problem as a stepping stone :) $\endgroup$ – darij grinberg Dec 3 '17 at 8:24
  • $\begingroup$ @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. $\endgroup$ – reuns Dec 3 '17 at 8:28
  • $\begingroup$ 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 $\endgroup$ – reuns Dec 3 '17 at 8:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Eyob Tsegaye Dec 4 '17 at 15:52
  • 1
    $\begingroup$ @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. $\endgroup$ – reuns Dec 4 '17 at 15:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.