2
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ 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$. $\endgroup$ Jul 28 '13 at 11:32
  • 2
    $\begingroup$ 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.) $\endgroup$ Jul 28 '13 at 13:06
  • $\begingroup$ @SamueleGiraudo,what is Sequence A056267 of the OEIS?thank you $\endgroup$ Jul 28 '13 at 13:11
  • 1
    $\begingroup$ oeis.org/A056267 $\endgroup$ Jul 28 '13 at 13:12
  • $\begingroup$ @SamueleGiraudo,thank you ,I have gotten it by searching $\endgroup$ Jul 28 '13 at 13:12
2
$\begingroup$

The ordinary generating function is a fairly horrible Lambert expansion (usually with a natural boundary). For more on this subject look in my old paper Walks on Free Groups and other Stories.

$\endgroup$
2
$\begingroup$

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.

This formula shows that a closed expression for the generating function is too much to hope for. Maybe you should think a bit more what you need it for, and whether you can avoid using it.

$\endgroup$
4
  • $\begingroup$ Indeed, it seems that oeis.org/A056267 and oeis.org/A027375 are duplicate. $\endgroup$ Jul 28 '13 at 20:22
  • $\begingroup$ @VladimirDorsenko,thank you,your post are also the answer,but it is permissible to choose only one answer $\endgroup$ Jul 28 '13 at 23:26
  • $\begingroup$ @XL _at_China: it's up to you which answer to accept. I failed to extract information giving a clear answer to your question from the paper of Igor, so I posted this answer, but you should not feel obliged to accept it if Igor's answer is sufficient for you :-) $\endgroup$ Jul 29 '13 at 1:04
  • $\begingroup$ @SamueleGiraudo: I actually just noticed that OEIS says "A027375, A038199 and A056267 are all essentially the same sequence with different initial terms." $\endgroup$ Jul 29 '13 at 16:29

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.