What is a formula for the number of strings with no repeats?

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.

• 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? – Ran G. Apr 17 '12 at 2:04
• Notice $1 <|t|$ requirement. Let me know if / how I can write my post clearer. – Dan Donnelly Apr 17 '12 at 2:13
• yea, I missed this requirement. It makes more sense now. – Ran G. Apr 17 '12 at 2:14
• 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 – Suresh Apr 17 '12 at 2:56
• 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). – user742 Apr 17 '12 at 9:20

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"
• 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. – Gilles 'SO- stop being evil' Apr 18 '12 at 23:04
• @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). – Raphael Apr 19 '12 at 5:58
• My comment is more tight than your answer. – user742 Apr 19 '12 at 19:15