How many restricted length strings are there without significant repetitions Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no sequence of $N$ characters repeats $M$ times in a row?

For instance with N=2 and M=3
101010 would not be counted, but 111010 would be

Here is some data I found on it with a simulation:

c n N M total percent
2,4,2,2,10,0.625
2,5,2,2,16,0.5
2,6,2,2,26,0.40625
2,6,3,2,48,0.75
2,6,2,3,48,0.75
2,7,2,2,42,0.328125
2,7,3,2,88,0.6875
2,7,2,3,88,0.6875
2,8,2,2,68,0.265625
2,8,3,2,162,0.6328125
2,8,4,2,216,0.84375
2,8,2,3,162,0.6328125
2,8,2,4,216,0.84375
2,9,2,2,110,0.21484375
2,9,3,2,298,0.58203125
2,9,4,2,416,0.8125
2,9,2,3,298,0.58203125
2,9,3,3,416,0.8125
2,9,2,4,416,0.8125
2,10,2,2,178,0.173828125
2,10,3,2,548,0.53515625
2,10,4,2,802,0.783203125
2,10,5,2,928,0.90625
2,10,2,3,548,0.53515625
2,10,3,3,802,0.783203125
2,10,2,4,802,0.783203125
2,10,2,5,928,0.90625
3,4,2,2,66,0.8148148148148148
3,5,2,2,180,0.7407407407407407
3,6,2,2,492,0.6748971193415638
3,6,3,2,666,0.9135802469135802
3,6,2,3,666,0.9135802469135802
3,7,2,2,1344,0.6145404663923183
3,7,3,2,1944,0.8888888888888888
3,7,2,3,1944,0.8888888888888888
3,8,2,2,3672,0.5596707818930041
3,8,3,2,5676,0.8651120256058528
3,8,4,2,6318,0.9629629629629629
3,8,2,3,5676,0.8651120256058528
3,8,2,4,6318,0.9629629629629629
3,9,2,2,10032,0.509678402682518
3,9,3,2,16572,0.8419448254839201
3,9,4,2,18792,0.9547325102880658
3,9,2,3,16572,0.8419448254839201
3,9,3,3,18792,0.9547325102880658
3,9,2,4,18792,0.9547325102880658
3,10,2,2,27408,0.4641568866534573
3,10,3,2,48384,0.819387288523091
3,10,4,2,55896,0.9466036681400193
3,10,5,2,58158,0.9849108367626886
3,10,2,3,48384,0.819387288523091
3,10,3,3,55896,0.9466036681400193
3,10,2,4,55896,0.9466036681400193
3,10,2,5,58158,0.9849108367626886
4,4,2,2,228,0.890625
4,5,2,2,864,0.84375
4,6,2,2,3276,0.7998046875
4,6,3,2,3936,0.9609375
4,6,2,3,3936,0.9609375
4,7,2,2,12420,0.758056640625
4,7,3,2,15552,0.94921875
4,7,2,3,15552,0.94921875
4,8,2,2,47088,0.718505859375
4,8,3,2,61452,0.93768310546875
4,8,4,2,64704,0.9873046875
4,8,2,3,61452,0.93768310546875
4,8,2,4,64704,0.9873046875
4,9,2,2,178524,0.6810150146484375
4,9,3,2,242820,0.9262847900390625
4,9,4,2,258048,0.984375
4,9,2,3,242820,0.9262847900390625


The values seem to go to $c^n$ as $N,M$ increase and appear to be a function of $c$, $N+M$. It also seems to decrease as you increase $n$ and increase as you increase $c$. This all makes intuitive sense to me. If I had to guess I would say it is exponential in $n$, polynomial in $c$, and exponential in $N+M$

A secondary question I have is how would you represent the language defined by just the strings counted.
For each particular $c,N,M$, this can be solved explicitly by constructing a DFA accepting the language. The general case may also be approached heuristically, though the dependency structure makes heuristic estimates harder to make.

The case $N = 1$ can be solved explicitly. Suppose that the alphabet is $\{0,\ldots,c-1\}$. Represent each word $w_1\ldots w_n$ as the sequence of differences $x_1\ldots x_n$, where $x_1 = w_1$ and $x_i = w_i - w_{i-1} \pmod{c}$ for $i &gt; 1$. Your language then becomes
$$
\epsilon + \{0,\ldots,c-1\}((\epsilon + 0 + \cdots + 0^{M-1})\{1,\ldots,c-1\})^*(\epsilon + 0 + \cdots + 0^{M-1}).
$$
The corresponding generating function is
$$
1 + cx \cdot \frac{1}{1-\frac{x^M-1}{x-1}\cdot(c-1)x} \cdot \frac{x^M-1}{x-1} =
\frac{x^{M+1}-1}{cx-1-(c-1)x^{M+1}}.
$$
The asymptotic growth of the number of words is controlled by the smallest (in modulus) root of $(c-1)x^{M+1}-cx+1$. If this modulus is $\alpha$, then the growth rate of the sequence (under reasonable assumptions) is $\Theta((1/\alpha)^n)$.

Plotting a few of the polynomials $(c-1)x^{M+1}-cx+1$ reveals that there are two real roots in $[0,1]$. We are interested in the one near $1/c$. Suppose that $x=(1+\epsilon)/c$ is a root. Then
$$
1 = cx - (c-1)x^{M+1} = 1+\epsilon - \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1},
$$
and so
$$
\epsilon = \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}.
$$
This shows that $\epsilon$ is exponentially small in terms of $M$, and so we can approximate $(1+\epsilon)^{M+1}$ by $1+(M+1)\epsilon$ to obtain the equation
$$
\epsilon \approx \frac{c-1}{c^{M+1}}(1 + (M+1)\epsilon)
$$
whose solution is
$$
\epsilon \approx \frac{\frac{c-1}{c^{M+1}}}{1-(M+1)\frac{c-1}{c^{M+1}}} = \frac{c-1}{c^{M+1}-(c-1)(M+1)} \approx \frac{c-1}{c^{M+1}}.
$$
Since $1/x = c/(1+\epsilon) \approx (1-\epsilon) c$, altogether we obtain that the number of words of length $n$ in which no symbol repeats $M$ times is $\Theta(\alpha^n)$, where
$$ \alpha \approx c - \frac{c-1}{c^M}. $$

Carrying this sort of analysis for $N &gt; 1$ seems significantly more difficult.