# Understandable, interesting uses of Möbius inversion?

I'm teaching discrete math to computer scientists. This is mostly their first proof-based course. We cover a bit of number theory, and as I hate loose ends, I cover a bit of Möbius inversion. (It is required later to justify some transfer formulas for the symbolic method in combinatorics and elsewhere.)

My problem is that I haven't been able to find clear applications of arithmetic sums (sums over the divisors of $n$) more than Euclid/Euler on perfect numbers. Even less convincing uses of Möbius inversion.

How many binary sequences are there that have period $n$? The sequence $\ldots110110110\ldots,$ for example, has period 3.

Suppose we wanted to compute the number of binary sequences with period $6.$ There are $2^6$ binary strings of length $6,$ but not all of them, when infinitely repeated in both directions, produce a sequence with period $6$. Among the strings of length $6,$ we find examples such as $111111,$ $101010,$ and $110110,$ which produce sequences with periods $1,$ $2,$ and $3,$ rather than $6.$ We can break the set of strings of length $6$ down as follows:

1. there are $2$ strings that give period $1$, namely $111111$ and $000000;$
2. there are $2$ strings that give period $2$, namely $101010$ and $010101,$ the second of which is a cyclic permutation of the first;
3. there are $6$ strings that give period $3$, namely $110110$ and its two cyclic permutations, and $100100$ and its two cyclic permutations;
4. there are $54$ strings that give period $6,$ including $111110$ and its five cyclic permutations, $111100$ and its five cyclic permutations, $111010$ and its five cyclic permutations, and so on.

The answer to our question is therefore $9:$ there are nine classes of strings that give period $6$, each consisting of six strings that are cyclic permutations of each other, and therefore $9$ sequences of period $6.$

Here's how we could have used Möbius inversion to compute this number. Let $M(n)$ be the number of binary sequences with period $n.$ Each such binary sequence could have been produced by any of $n$ strings, which are all cyclic permutations of each other. From this observation, we have $$2^n=\sum_{d\mid n}d M(d).$$

Applying the Möbius inversion formula to this equation, we get $$nM(n)=\sum_{d\mid n}\mu(d)2^{n/d}$$ or $$M(n)=\frac{1}{n}\sum_{d\mid n}\mu(d)2^{n/d}$$ Applying this to $n=6$, we get $$M(6)=\frac{1}{6}(\mu(1)2^6+\mu(2)2^3+\mu(3)2^2+\mu(6)2^1)=\frac{1}{6}(64-8-4+2)=9.$$

• Just the kind of example I was looking for. Thanks! I'll wait to see if others show up. – vonbrand Jun 17 '14 at 0:36
• That's beautiful! – Ryan Reich Jun 17 '14 at 17:17

In the end I adopted the following beautiful result.

A string can be written as repetitions of its root, the smallest substring that it is a repeat of. I.e., "abababab" has "ab" as root. If a string is its own root, it is called primitive. Call $p_n$ the number of primitive strings of length $n$.

If the strings are written over an alphabet of $s$ symbols, there are $s^n$ strings in all. But they are all repetitions of some primitive root, whose length divides $n$: $$s^n = \sum_{d \mid n} p_d$$ Möbius inversion gives: $$p_n = \sum_{d \mid n} \mu(n / d) s^d$$ For example, with $s = 2$, $n = 4$ this gives $p_4 = 12$. This can also be computed by noting that primitive strings of length $1$ over $\{a, b\}$ are just $a$ and $b$ (giving rise to $aaaa$ and $bbbb$), of length $2$ the only ones are $ab$ and $ba$ (giving rise to $abab$ and $baba$). All other length $4$ strings are primitive, i.e., there are $2^4 - 4 = 12$ of them.

• I'm still looking for further nice examples. Thanks in advance for any suggestions. – vonbrand Jun 19 '14 at 19:57