8
$\begingroup$

I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1< |t| < |s|$, there is no disjoint copy of $t$ in $s$. For exapmle, let $A=\{a,b\}$. Then $aaa$ is one of the strings I want to count, since for the substring $aa$, there are no disjoint copies. However, $abab$ contains such a repeat.

If someone's already figured out a useful formula, please link. Otherwise, I will refer back to this post in any article I write, if I use someone's answer.

Here is another example. Let's try to construct a long string over $\{a,b\}$, that contains no repeats:

aaa (can't be a)
   aaab (a or b)
     aaabbb (can't be b)
       aaabbba (can't be b or a)
   aaaba (can't be a or b)

If we built a tree, we could count the number of nodes, but I want a formula.

Edit: Well, it's not as daunting as I first thought if we convert this to a bin-choosing problem. A set of strings of length k with at least one repeat is equal to the set that is the union of all permutations of the cartesian product: $A \times A \times \cdots\times A \text{(k-4 times)} \times R \times R$ where $R$ is the required repeat. I don't know if that's helpful, but it sounded pro :) Anyway, let their be |A| bins, choose any two (even if the same one) to be the repeat, then choose $k-4$ more and multiply (the first 4 are already chosen, see?). Now I just need to find that formula from discrete math.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ why there is no disjoint copy in $aaa$? isn't $t=a$ a valid substring of $s=aa$, that is, $s=tt$? Can you give couple more examples to clarify what should and shouldn't be count? $\endgroup$ – Ran G. Apr 17 '12 at 2:04
  • 1
    $\begingroup$ Notice $1 <|t|$ requirement. Let me know if / how I can write my post clearer. $\endgroup$ – Dan Donnelly Apr 17 '12 at 2:13
  • $\begingroup$ yea, I missed this requirement. It makes more sense now. $\endgroup$ – Ran G. Apr 17 '12 at 2:14
  • 1
    $\begingroup$ I'm not seeing how (with a 2 letter alphabet for example) you can construct a string of length (say) 10 with no repeats. i.e the desired number must be upper bounded by some function of k independent of n $\endgroup$ – Suresh Apr 17 '12 at 2:56
  • 2
    $\begingroup$ I just can say for alphabet of size $n$ longest possible string without repeats, is $$2\cdot{n \choose 2} + 3\cdot n$$ $3\cdot n$ is because you can have a strings of length $3$ with same elements, and $2 \cdot {n \choose 2}$ is because you just have just $2 \cdot {n \choose 2}$ different combination of this elements, and adding new combination causes to repeating. (I considered that you say about disjoint repeating). $\endgroup$ – user742 Apr 17 '12 at 9:20
1
$\begingroup$

This answers the question after the number of repeat-free words per size, implying that the desired quantity even exists.

Definition: Call $w \in \Sigma$ repeat-free if and only if it does not contain a factor $xyx$ with $x \in \Sigma^{\geq 2}$ and $y \in \Sigma^*$.

Claim: For given finite alphabet $\Sigma$ with $|\Sigma| = k$, there are no repeat-free words of length greater than $2k^2 + 1$.

Proof Idea: By pigeon-hole principle. Take a word $w$ of length $2k^2 + 2$ (or a longer word and consider its prefix of this length), i.e. $w = a_0a_0' \dots a_{k^2}a_{k^2}'$. Assume $w$ is repeat-free; that means that $a_ia_i' \neq a_ja_j'$ for all $i \neq j$ (otherwise we had a repeat). Therefore, there are $k^2 + 1$ many pairs of symbols; this contradicts $|\Sigma^2| = k^2$. So $w$ is not repeat-free. $\square$

Note that this is a rough proof: factors $a_i'a_{i+1}$ might create a repeat even sooner.

Notation:

  • $\Sigma^{\geq k} = \bigcup_{i=k}^\infty \Sigma^i = \Sigma^* \setminus \bigcup_{i=0}^{k-1} \Sigma^i$
  • "factor" = "subword" = "substring"
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This doesn't really answer the question. You've only proved a very crude and pretty obvious upper bound, the question asked for an exact formula. $\endgroup$ – Gilles 'SO- stop being evil' Apr 18 '12 at 23:04
  • $\begingroup$ @Gilles: I misread the question at first but thought I could leave what I wrote up here for others (e.g. Kaveh, who claimed there were infinitely many such words). $\endgroup$ – Raphael♦ Apr 19 '12 at 5:58
  • $\begingroup$ My comment is more tight than your answer. $\endgroup$ – user742 Apr 19 '12 at 19:15

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.