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:

There are $3!\cdot 3^2=54$ patterns of the form $AXYZB$ where $\{X,Y,Z\}=\{0,1,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$.