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&lt; |t| &lt; |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)  
&nbsp;&nbsp; aaab (a or b)  
&nbsp;&nbsp;&nbsp;&nbsp; aaabbb (can't be b) 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; aaabbba (can't be b or a) 
&nbsp;&nbsp; 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.
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&#39; \dots a_{k^2}a_{k^2}&#39;$. Assume $w$ is repeat-free; that means that $a_ia_i&#39; \neq a_ja_j&#39;$ 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&#39;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"