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

Improve this question
$\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$
    – JRN
    Commented Jul 28, 2013 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$
    – Samuele Giraudo
    Commented Jul 28, 2013 at 13:06
  • $\begingroup$ @SamueleGiraudo,what is Sequence A056267 of the OEIS?thank you $\endgroup$
    – XL _At_Here_There
    Commented Jul 28, 2013 at 13:11
  • 1
    $\begingroup$ oeis.org/A056267 $\endgroup$
    – Samuele Giraudo
    Commented Jul 28, 2013 at 13:12
  • $\begingroup$ @SamueleGiraudo,thank you ,I have gotten it by searching $\endgroup$
    – XL _At_Here_There
    Commented Jul 28, 2013 at 13:12

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Indeed, it seems that oeis.org/A056267 and oeis.org/A027375 are duplicate. $\endgroup$
    – Samuele Giraudo
    Commented Jul 28, 2013 at 20:22
  • $\begingroup$ @VladimirDorsenko,thank you,your post are also the answer,but it is permissible to choose only one answer $\endgroup$
    – XL _At_Here_There
    Commented Jul 28, 2013 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$
    – Vladimir Dotsenko
    Commented Jul 29, 2013 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$
    – Vladimir Dotsenko
    Commented Jul 29, 2013 at 16:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .