Primitive binary necklaces

Solution 1:

The number of primitive strings of length $n$, call it $p_n$, is easy to get. The total number of length $n$ strings made of $s$ symbols is just $s^n$. All strings are made of repeats of some primitive string (in case it is primitive, it is one repeat). So: $$ s^n = \sum_{d \mid n} p_d $$ and Möbius inversion gives: $$ p_n = \sum_{d \mid n} \mu(n/d) s^d $$ Now each primitive necklace (i.e., cycle) can be cut at $n$ places to get different primitive strings, so the number of primitive necklaces is just: $$ c_n = \frac{1}{n} \sum_{d \mid n} \mu(n/d) s^d $$

Solution 2:

I would like to add some linked material from the OEIS to this thread in order to facilitate further exploration of this problem. (The amount of material at the OEIS indicates that this problem has interested many combinatorics enthusiasts.) We show how to count primitive necklaces of at most $N$ colors. Recall that the Polya Enumeration Theorem tells us that the total number of necklaces (rotational symmetry only) on at most $N$ colors is given by the substituted cycle index of the cyclic group $$Z(C_n) = \frac{1}{n}\sum_{d|n} \varphi(d) a_d^{n/d}$$ which is, supposing there are $N$ colors, $$q_n = Z(C_n)(c_1+c_2+\cdots+c_N)_{c_1=c_2=\cdots=c_N=1} \\= \left. \frac{1}{n}\sum_{d|n} \varphi(d) (c_1^d+c_2^d+\cdots+c_N^d)^{n/d} \right|_{c_1=c_2=\cdots=c_N=1} = \frac{1}{n}\sum_{d|n} \varphi(d) N^{n/d}.$$ Let the number of primitive necklaces be $p_n$, then it is perfectly straightforward to show that $$\sum_{d|n} p_d = q_n.$$ Apply Moebius inversion to this to obtain $$p_n = \sum_{d|n} \frac{\mu(n/d)}{d} \left(\sum_{f|d} \varphi(f) N^{d/f}\right).$$

Here is the Maple code to compute this function.

with(numtheory);

p := proc(n, N)
local d, f, res;
    res := 0;
    for d in numtheory:-divisors(n) do for f in numtheory:-divisors(d) do
            res := res + numtheory:-mobius(n/d)*numtheory:-phi(f)*N^(d/f)/d
        end do
    end do;
    res
end proc

This gives for two colors ($N=2$) the sequence $$2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182,\ldots$$ which is OEIS A001037.

For three colors ($N=3$) we get the sequence $$3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880, 16104, 44220, 122640, 341484, 956576,\ldots$$ which is OEIS A027376.

Finally for four colors ($N=4$) we get the sequence $$4, 6, 20, 60, 204, 670, 2340, 8160, 29120, 104754, 381300, 1397740, 5162220,\ldots$$ which is OEIS A027377.

Addendum. According to the OEIS, the above formula for $p_n$ simplifies to $$p_n = \frac{1}{n}\sum_{d|n} \mu(d) N^{n/d}.$$

The simplification of the above goes like this.

Start with $$p_n = \sum_{d|n} \frac{\mu(n/d)}{d} \left(\sum_{f|d} \varphi(f) N^{d/f}\right).$$

Re-index setting $d/f=q$ so that $d=fq$ to obtain $$p_n = \sum_{q|n} N^q \sum_{f|n/q} \frac{\mu(n/f/q)}{fq} \varphi(f).$$

This is $$p_n = \frac{1}{n} \sum_{q|n} N^q \sum_{f|n/q} \frac{\mu(n/f/q)}{fq/n} \varphi(f).$$ Putting $m= n/q$ the inner sum becomes $$\sum_{f|m} \mu(m/f) \times m/f \times \varphi(f).$$

This is a convolution of multiplicative functions so we only need to verify it for prime powers $m = p^v.$ This gives two terms namely for $f = p^v$ and $f = p^{v-1}$, which for $v\ge 2$ contribute $$1 \times 1 \times \varphi(p^v) - 1 \times p \times \varphi(p^{v-1}) = p^v - p^{v-1} - p (p^{v-1} - p^{v-2}) = 0.$$ For $v=1$ we get $$1 \times 1 \times \varphi(p) - 1 \times p \times \varphi(1) = p-1 - p = -1.$$ Finally for $m=1$ we get $1.$ This shows that (using the convolution being multiplicative) $$\sum_{f|m} \mu(m/f) \times m/f \times \varphi(f) = \mu(m)$$ and we finally have $$p_n = \frac{1}{n} \sum_{q|n} N^q \mu(n/q).$$