What is a formula for the number of strings with no repeats?
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"