How many ways can there be $k$ $1$s in a row in a string of length $n$? Let us first define $[r] = \{1,2,\ldots,r\} = \{x\in\mathbb N | x \le r\}$.
Now let $n,r,k\in\mathbb N$ and $k\le n$. How many strings are there of length $n$ made of characters from $[r]$ that contain $k$ of the symbol $1$ in a row? To be clear this would always include the string of all ones, so it does not need to be exactly $k$ in a row it may be at least $k$ in a row.
I had some ideas on how to do this but they all have seemingly failed:
I tried to deal with this as integer partitions. So each string has a corresponding partition of $n$, where each element run of something in a row in the string (even of length one) corresponds  to that number in our partition. If we could find every partition of $n$ with a $k$ or greater appearing in it we would be on the right road, but then we would need to deal with the fact that that is just an occurrence of something five or more times, not just $1$.
I also tried looking at inclusion-exclusion. I looked us having $n-k+1$ spots in which there may be a start of a run that lasts $k$ elements and then each one of those may have what we are looking for, but the issue is that if I have $k = 10$ and I have a run in the first spot in my string and I have one in the eleventh spot, that forces everything inbetween to also be a run as this means the first 20 elements are all ones.
I thought generating functions may be the next place to look but I wasn't sure how to actually approach it from there.
 A: It’s easier to count the strings that don’t have a run of $k$ $\mathbf 1$s. (To find out how many strings do have a run of $k$ $\mathbf 1$s, just subtract this from the total number of strings $r^n$.)
Such strings are of the form $({\mathbf 1}^{<k}\bar{\mathbf 1})^*{\mathbf 1}^{<k}$, where:


*

*${\mathbf 1}^{<k}$ means a sequence of fewer than $k$ $\mathbf 1$s,

*$\bar{\mathbf 1}$ means any symbol other than $\mathbf 1$,

*and $A^*$ is the Kleene star, meaning zero or more repetitions of $A$.


We can read off a generating function directly from this expression: $$b(n, r,k)=\Biggl(\frac{1}{1-\frac{1-x^k}{1-x}\cdot(r-1)x}\Biggr)\Bigl(\frac{1-x^k}{1-x}\Bigr)$$
which simplifies to $$b(n,r,k)=\frac{1-x^k}{1-x - (r-1)x(1-x^k)}$$
Explicitly, if there are $B(n,r,k)$ strings of length $n$ over an $r$-symbol alphabet that have no runs of $k$ $\mathbf 1$s, then: $$B(n+k, r, k) = (r-1)\bigl(B(n,r,k) + B(n+1,r,k) + \cdots + B(n+k-1,r,k)\bigr)$$
and of course $B(n,r,k)=r^n$ for $n<k$.
For example, if $r=2$ and $k=2$ then we get the Fibonacci numbers. And more generally with $r=2$ we get the Fibonacci n-step numbers $F^{(k)}_{n+k}$. For $r=3$ and $k=2$ we get A028859, and so forth.
