0
$\begingroup$

From: A Course in Combinatorics by van Lint / Wilson enter image description here

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

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

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$

$\endgroup$
  • $\begingroup$ Nice. Could you be able to explain where the two equalities in the last row came about? $\endgroup$ – Al Jebr Feb 26 '16 at 6:12
  • $\begingroup$ I mean, the algebraic manipulations. How did we get $\frac{2^l}{l}$? $\frac{\mu(k)}{k}$? $k | \frac{n}{l}$? $\endgroup$ – Al Jebr Feb 26 '16 at 6:20
  • $\begingroup$ 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$ $\endgroup$ – Jason Carr Feb 26 '16 at 6:27
1
$\begingroup$

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.

$\endgroup$

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.