# Generating function of factorable binary words

A word $w$ on the alphabet $A := \{0, 1\}$ is factorable if \begin{equation} w = u^k \mbox{ where } u \in A^* \mbox{ and } k \geq 2. \end{equation}

Let $L$ be the language of the set of factorable words on $A$ and $f(t)$ be its generating series, that is \begin{equation} f(t) := \sum_{n \geq 0} |L \cap A^n| \; t^n. \end{equation}

What is the generating function of $L$?

• Is $k$ a positive integer or is it a word over the alphabet $\{0,1\}$? I think you mean that $w$ and $u$ are words, instead of $w$ and $k$. Jul 28 '13 at 11:32
• Your are asking for primitive words over a binary alphabet. The coefficients of the generating series you are looking for are the ones of Sequence A056267 of the OEIS. (And please, make an effort in writing your question.) Jul 28 '13 at 13:06
• @SamueleGiraudo,what is Sequence A056267 of the OEIS?thank you Jul 28 '13 at 13:11
• oeis.org/A056267 Jul 28 '13 at 13:12
• @SamueleGiraudo,thank you ,I have gotten it by searching Jul 28 '13 at 13:12

A slightly more relevant reference to OEIS than Samuele Giraudo gave is http://oeis.org/A027375. In particular, there one finds the formula $$a_n = \sum_{d\mid n} \mu(d)2^{n/d}$$ which in fact easily follows from the definition by means of Moebius inversion. For more than two letters, you should replace $2$ above by the number of letters.