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).

-
We can probably answer the enumeration question independent of the search application. However, just for background, can you provide a link to the specific question on stackoverflow? You just gave the link to the front page. –  Hugh Denoncourt Aug 21 '12 at 17:24
@HughDenoncourt of course, but all you'll find there is a failed attempt and some comments. I'll fix the link. –  Amine Aug 21 '12 at 18:06

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$.

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}$$

-
I had trouble understanding the equations involving $L$, it is now crystal clear. I don't know how I didn't think of recursion. Well done, thank you very much (especially for the little Java part). Would you mind explaining the probabilistic result a little ? –  Amine Aug 22 '12 at 8:32
@Amine explanation added –  leonbloy Aug 22 '12 at 13:23
Interesting, thanks again for all the work you've put into this. –  Amine Aug 22 '12 at 14:18

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.

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$.

-
Hello, thanks for your answer. I would like to know how you deduce the generating function, then the recursive formula. This is blowing my mind kind of. –  Amine Aug 23 '12 at 9:13
No problem. I can't really give my derivation of the generating function here, since it relies on some of my own (unpublished) research. That said, it is probably "known", and it could presumably be proven with leonbloy's recurrence. If you like you can shoot me an email and I'll provide more detail. I'll put a little more info about finding the recurrence relation above. –  Jair Taylor Aug 23 '12 at 18:46