How many strings of digits of length $n$ contains a substring of $k$ identical consecutive digits?

Question

Let $f(n, k)$ be the number of strings of digits of length $n$ that contain a substring of $k$ identical consecutive digits. What would be a recursive or closed-form way to compute $f(n, k)$?

For example, $f(n, 2)=10^n - 10\times 9^n$ by using complementary counting. There are $10$ choices for each digit ignoring the restriction, and there are $9$ choices for each digit after the first if we can't repeat any two consecutive digits.

Answer 1

We consider the alphabet $V=\{0,1,\ldots,9\}$. We are looking for the number $g(n,k)$ of strings of length $n$ having runs at most length $k-1$. The wanted number is $$f(n,k)=10^n-g(n,k)$$

Strings with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over a q-ary alphabet is given by \begin{align*} \left(1-\frac{qz}{1+z}\right)^{-1} \end{align*}

Replacing occurrences of $0$ in a Smirnov word by one up to $k-1$ zeros generates words having runs of $0$ with length less than $k$. \begin{align*}\ z\longrightarrow z+z^2+\cdots+z^{k-1}=\frac{z\left(1-z^{k-1}\right)}{1-z} \end{align*}

The same can be done for the other digits.

The resulting generating function is for $q=10$ \begin{align*} \left(1- \frac{10\cdot \frac{z\left(1-z^{k-1}\right)}{1-z}}{1+\frac{z\left(1-z^{k-1}\right)}{1-z}}\right)^{-1} &=\frac{1-z^k}{1-qz+(q-1)z^{k}} \end{align*}

Denoting with $[z^n]$ the coefficient of $z^n$ in a series we obtain the number of wanted words of length $n$ as \begin{align*} \color{blue}{f(n,k)}&=10^n-g(n,k)\\ &\color{blue}{=[z^n]\left(\frac{1}{1-10z}-\frac{1-z^k}{1-10z+9z^{k}}\right)} \end{align*}

Example: Let's look at an example. We take $k=3$. We obtain with some help of Wolfram Alpha \begin{align*} \frac{1}{1-10z}-\frac{1-z^3}{1-10z+9z^{k}}=10 z^3 + \color{blue}{190} z^4 + 2800 z^5 +\cdots \end{align*}

The blue colored coefficient of $z^4$ shows there are $\color{blue}{190}$ words of length $4$ built from characters $\{0,1,2,\ldots 9\}$ and runs of a digit with length at least $k=3$.

The number $190$ is easily to check. Strings of length $n=4$ and runs with length $3$ have the form \begin{align*} abbb\qquad\text{or}\qquad bbba \end{align*} with $a,b\in\{0,1,\ldots,9\}$ given $2\cdot 10\cdot 10=200$ different strings. Since $abbb=bbba$ iff $a=b$ we have $10$ strings counted twice and to subtract from $200$ giving a total of \begin{align*} \color{blue}{f(4,3)=190} \end{align*}