Number of words with a minimal number of repetitions Given :


*

*a word length $n$,

*a set of characters $C = \{c_1, ..., c_p\}$,

*and a minimal number of repetitions $m$,


How many words of $n$ characters from $C$ containing at least one sequence of $m$ times the same character are there ?
I have very limited knowledge of combinatorics and algebra so please, don't just give "clues". Thank you.
Note : This question was first asked at stackoverflow.com but obviously testing every possible string (even with shortcuts) is a ridiculously inefficient way of solving this, which is why I came here for a mathematical solution (and also because math is beautiful).

Updated: heavily simplified.
Let $P$ be the alphabeth (set of characters) size. Let $S(N,M)$ be the number of strings of length $N$ (over that alphabeth) that does NOT include any subsequence of $M$ consecutive repeated characters.
Then
$$
S(N,M)=\left\{
 \begin{array}{ll}
  P^{N}  & N<M \\
  (P-1) \sum_{i=1}^{M-1} S(N-i,M) &  N \ge M
 \end{array}
\right.
$$
With this, we can compute recursively the values of $S(N,M)$ for any $N,M,P$.
For example.
This can be related, at least for $P=2$, to the Fibonacci M-step numbers (though here we have a different starting values; in any case, this suggest that a explicit closed-form value would be rather complicated).
An asymptotic can be obtained by a probabilistic argument (brief explanation added) :
Assume that all realizations of the sequence of $N$ characters are equiprobable, and lets compute the fraction that follow our restriction (all runs have length less than $M$) as a probability.
Let $x_i \ge 1$ ($i=1\cdots c$) be the $i-$th runlength. We have that the sum is fixed ($\sum x_i = N$) and $c$ (number of runs) is a random variable. I claim that this model is asymptotically equivalent to another one in which the number of runs $c$ is fixed and the $x_i$ are iid; and hence the sum is variable (but $E[\sum x_i] = c \, E[x_i]= N$). This is conceptually the same as the "Poissonization" method. In our  case,  $x_i$ are geometric variables, with $p = (P-1)/P = 1 - \theta$ (probability that the run stops at the next try).
Because the mean of this geometric variable (with support in $1 \cdots \infty$) is $1/p$ we obtain $c = N (1 -\theta)$ . The event that $x_i < M$ for some particular $i$ can be computed as a geometric sum as $ 1 -\theta^{M-1}$ and because $x_i$ are iid, $P(x_1 < M ;x_2 <M \cdots) =P(x_1<M)^c$ we have finally obtain the desired fraction and
$$ S(N,M) \approx P^N \, \left(1-\theta^{M-1}\right)^{N(1-\theta)}, \hspace{1cm} \theta=\frac{1}{P} $$
