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).
 A: 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} $$
A: There is also a nice generating function for this problem.  Fix $p$ and let $S(n,m)$ be the number of words of length $n$ using at most $p$ distinct letters, with no repetition of $m$ identical letters in a row, as defined by leonbloy.  Then $$ \sum_{n = 0}^\infty S(n,m) x^n = \frac{1 - x^m}{1 - px - (1-p)x^m}.$$
If you're not familiar with generating functions, this means that you can get the number you're looking for pretty easily by extracting the coefficient of $x^n$ in the Taylor series for the above expression using mathematical software such as Sage, Mathematica etc. Since it's rational, i.e., a fraction of polynomials, this also allows to find another recursive formula.  
Added -  more details:
In general a rational generating function
$$\sum_{n=0}^\infty f(n) x^n = \frac{p(x)}{1 + a_1x + \ldots + a_mx^m}$$
will, for large n, obey a recurrence relation
$$f(n) + a_1f(n-1) + \ldots + a_nf(n-m) = 0.$$
Amazing, isn't it? See Richard Stanley - Enumerative Combinatorics Vol 1 Ch. 4, or just Google it. In this case we have the denominator 
$$1 - px - (1-p)x^m$$
so we get the recurrence
$$S(n,m) - pS(n-1,m) - (1-p)S(n-m) = 0.$$
$$S(n,m) = pS(n-1,m) + (1-p)S(n-m,m).$$ A little checking shows this holds for $n > m$, and we have the initial values $S(n,m) = p^n$ for $n< m$, and $S(m,m) = p^m - p$.
A: Repetitions in strings: algorithms and combinatorics
