How can we have a circular sequence of $0$s and $1$s of length $d$ that are not periodic?

Question

From: A Course in Combinatorics by van Lint / Wilson

$M(d)$ is the number of circular sequences of length $d$ that are not periodic. How is this possible?

If $d=1$, then the sequence $1$ is periodic. It has period $1$.

If $d=2$, then $11$, $10$, $01$, $00$ are all periodic with period either $1$ or $2$.

In general, every finite sequence of $0$s and $1$s will have at least period $1$.

Can someone explain this example?

(Theorem 10.4 is Mobius Inversion)

Answer 1

The point of circular series isn't that these are actually on a cycle, but that they're symmetric under this rotation. Everything, were it actually repeated on a cycle would be periodic, since the cycle is. What's called periodic here is anything which has a periodicity just within the string itself.

So, the non-periodic cycles of the first few sizes are:

1: 0, 1

2: 01

3: 001, 011,

4: 0001, 0011, 0111,

5: 00001, 00011, 00111, 01111, 01010, 10101

6: 000001, 000011, 000111, 001111, 011111, 010011, 010111, 001011, 101011

Two examples of periodic sequences are 0101, 101101. Note that these sequences only exist at a length which divides n (and so exist if and only if n is composite)

We can verify that this is correct from the equation given $$\frac{1}n \sum_{d|n} \mu(d) 2^{n/d}$$

Evaluated at 1,2,3,4,5,6 we have respectively

$M(1) = 2^1$

$M(2) = \frac{2^2 - 2^1}2 = 1$

$M(3) = \frac{2^3 -2^1}{3} = 2$

$M(4) = \frac{2^4 - 2^2 + 0\cdot 2^1}{4} = 3$

$M(5) = \frac{2^5 - 2^1}{5} = 6$

$M(6) = \frac{2^6 - 2^3 - 2^2 + 2^1}{6} = 9$

Answer 2

From what I understand, they mean that the sequence doesn't have a period smaller than $d$. This makes the formula $N_n = \sum_{d|n} M(d)$ work, since any cyclic sequence has some minimal period $d$ dividing $n$, and there are $M(d)$ such $d$-periodic cyclic sequences.