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.