# 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. Aug 21, 2012 at 17:24
• @HughDenoncourt of course, but all you'll find there is a failed attempt and some comments. I'll fix the link.
– ttzn
Aug 21, 2012 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 ?
– ttzn
Aug 22, 2012 at 8:32
• @Amine explanation added Aug 22, 2012 at 13:23
• Interesting, thanks again for all the work you've put into this.
– ttzn
Aug 22, 2012 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.
– ttzn
Aug 23, 2012 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. Aug 23, 2012 at 18:46