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

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)

• Could you give the reference of your citation? This might help to understand the context. – J.-E. Pin Feb 26 '16 at 5:35
• A Course in Combinatorics_van Lint / Wilson – Al Jebr Feb 26 '16 at 5:36

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$

• Nice. Could you be able to explain where the two equalities in the last row came about? – Al Jebr Feb 26 '16 at 6:12
• I mean, the algebraic manipulations. How did we get $\frac{2^l}{l}$? $\frac{\mu(k)}{k}$? $k | \frac{n}{l}$? – Al Jebr Feb 26 '16 at 6:20
• The first equation comes from swapping the two so that l is 'picked' first, then choosing k from the remaining factors to swap it around. Basically d = l*k. So then 1/d becomes 1/l * 1/k, and is moved into the proper sums. Similarly mu(d/l) is changed to just mu(k). Then the second equation comes from the first via mobius inversion: it's a certain identity that follows from the statement that $\sum_{d|n} \phi(d) = n$ – Jason Carr Feb 26 '16 at 6:27

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.