Number of words not having a subword of length k with only one letter Let $f_k(n,t)$  be the number of words of length $t$ over the alphabet $\mathcal{A} = \{1,\ldots,n\}$ such that no word contains $i^k$ as a substring for $i \in \mathcal{A}.$
I am looking to find the asymptotic for $f_k(n,t).$ It doesn't seem that hard to do but I am pretty sure others have studied this problem already and I am hence looking for a reference where this problem was studied.
Note I am aware that Guibas and Odlyzko already solved a far more general problem in String Overlaps, Pattern Matching, and Nontransitive Games, what I am looking for is if one can find a more simplified treatment of this problem when one only forbids words where a letter is repeated $k$ times.
 A: Your problem is extremely similar to an example  in the third edition of Herb Wilf's Generatingfunctionology. In example 4.12  there is a count of the number of binary  strings  that avoid the word $1^k$. (By the way, this example only appears in the third edition, not in the second edition which is freely downloadable on his website.) I think a generalization of this example to your problem with an alphabet of arbitrary size would be smooth going.
However, there's a general method for counting strings that avoid particular words that's much more powerful (but no more complex) than the example in Wilf's book: the Goulden-Jackson cluster method. In fact, this paper itself claims that it is a nice reformulation of a result of the authors you mentioned,  Guibas and Odlyzko. The method takes a collection of "forbidden words" over an arbitrary alphabet and efficiently outputs a rational generating function for the numbers of strings of a given length that avoid all the forbidden words. In your case, with an alphabet of $n$ letters and forbidden words $1^k,\dots,n^k$ the method gives the generating function $f$ for your sequence $\langle f_k(n,t):t\ge0\rangle$ as
$$f(z)=\frac{1-z^k}{1-nz+(n-1)z^k}.$$
Of course, there still is the problem of extracting (or approximating) the coefficient $[z^t]f(z)$, but perhaps knowledge of the generating function is enough to get you started.
