Strings with no long runs from proper subalphabets

Question

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the complement. I am interested in values like, say, $N_{21,8,4}$.

Can we compute $N_{n,k,b}$ efficiently? Is there a reasonable formula for it?

It is analogous to a person whose circle of closest friends is changing at a reasonable rate; there is never too long between times when someone enters or leaves the circle.

---

Example 1. $R_{5,3,2}$ is the number of binary strings of length 5 that contain some unary run of length 3: these are of the form 000XY, 00111, 01000, 0111X (if start with a 0) so $$ R_{5,3,2} = 16. $$ Example 2. $R_{5,4,3}$: the complement (no run of length 4 from any 2-ary subalphabet) can be analyzed by looking at the middle 3 letters:

1. There are $3!\cdot 3^2=54$ patterns of the form $AXYZB$ where $\{X,Y,Z\}=\{0,1,2\}$.

2. If $XYZ$ is from a 2-ary alphabet (but not unary) then $A$ and $B$ have to be the missing letter in $XYZ$, so there are $\binom{3}{2} (2^3-2) = 18$ of this form.

Total $N_{5,4,3}=72$ and $R_{5,4,3}=3^5-72=171$.

Answer 1

Here is a dynamic programming approach to compute $N_{n,k,b}$ in time $O_{k,b}(n)$. You can extract from it a recurrence for $N_{n,k,b}$ in the $n$ variable.

Given a suitable sequence, for each of the $b$ letters, we can count the number of steps from the last occurrence of each letter to the end, which is a number $1$ to $k$. So we get a list of $b$ numbers $1$ to $k$. These numbers are clearly distinct, and $1$ is included, so there are $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}$ possibilities.

Store at each step the number of length $n$ sequence satisfying your condition for each of the $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}$ possible ending types. Then we can compute from this the number of length $n+1$ sequences satisfying your conditon for each of the possible ending types.

The way to do this is pretty simple. Given a list of numbers, we know that adding one letter at the end increases all the numbers by $1$, except the number corresponding to the letter we add, which goes to $1$. So there are usually $b$ possibilities for the next type, which are given by picking one of the numbers and setting it to $1$ and adding $1$ to the rest. The only exception is if one of the numbers is $k$, in which case we have to set that one to $1$ and increment the rest.

This tells us how to update the information at each step, and finally how to compute $N_{n,k,b}$ by adding up over all the different ending types.

It also gives us a recurrence relation for $N_{n,k,b}$ in the variable $n$. The updating step corresponds to multiplying by a certain $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}\times \begin{pmatrix} k-1 \\ b-1 \end{pmatrix}$ matrix. By Cayley-Hamilton, the sequence we generate satisfies the recurrence relation defined by the characteristic polynomial of the matrix. In particular, the growth rate in $n$ is exponential by the largest eigenvalue of the matrix.

In the case $N_{21,8,4}$, we have $\begin{pmatrix} k-1 \\ b-1 \end{pmatrix}=\begin{pmatrix} 7 \\ 3 \end{pmatrix}=35$, which is not too big, so the algorithm should not take too long to run and give the exact answer, nor should it be too difficult to compute the matrix and find the growth rate.