Let $t_{n}$ be the number of words with length $n$ and symbols $\{1,2,3\}$ which are not equal to any of their cyclic shifts. For example, the word $1232$ has cyclic shifts $2123, 3212, 2321$, none of which are equal to $1232$, so it is counted by $t_{n}$.
I'm asked to find a formula for $t_{n}$ using Möbius Inversion. We use the following version of Möbius Inversion for posets (power set with subsets): Let $f$ be a function from $2^{V}$ (Power set of $V$) to the real numbers, and define $g(X) = \sum_{Y \subseteq X} f(Y)$. Then $f(X) = \sum_{Y \subseteq X} (-1)^{|X| - |Y|}g(Y)$.
I have a feeling I'm severely overlooking something, because I have no idea how to do this with Möbius Inversion. However, I think am onto something, which may shine some light on how to do it.
It seems as though the only words which will be equal to one of their cyclic shifts are the words which are entirely repetitions of subwords. For example $13341334$ is just a repetition of $1334$ two times. So for each proper divisor $d$ of $n$, take every word of length $d$, then repeat it $\frac{n}{d}$ times will give all the "bad" words of length $n$, although with a good amount of over counting.
It seems like the alternating sign in Möbius Inversion might help resolve the over counting, but I'm not sure if I'm even stabbing in the right direction.
Any help is appreciated,
Thanks
Note $$ 3^n = \sum_{d|n}t_d\tag1 $$ because every word on $n$ letters can be uniquely expressed as $\frac{n}d$ copies of some word of length $d$ not equal to any of its cyclic shift, for some $d|n$.
Now, in any poset $P$ with functions $f,g:P\to \mathbb R$, we have $$\forall t\in P:f(t)=\sum_{s\le t}g(s)\qquad\iff\qquad \forall t\in P:g(t)=\sum_{s\le t} f(s)\mu'(s,t),\tag2$$ where $\mu'(s,t)$ is a the Möbius function for that poset. This is the most general expression of Möbius inversion. See Wikipedia.
In this case, the most useful choice of poset is the divisor order on positive integers, not the Boolean poset of subsets as you said in your post. The Möbius function for the divisor poset is $\mu'(s,t)=\mu(t/s)$, where $\mu$ is the usual Möbius funciton.
Using $(2)$, $(1)$ implies $$ t_n = \sum_{d|n}3^d\mu(n/d)=\sum_{d|n}\mu(d)3^{n/d}. $$