Number of unique binary strings containing at least m sequential 1s Let $Z\left(n,m\right)$ be the number of unique binary strings of length $m$ containing at least one instance of $n$ consecutive 1's. I am trying to come up with an expression for $Z$, preferably directly calculable though I will accept a recursive solution as well. I have attempted a formulation based on [1],
$$ \hat{Z}\left(n,m\right) = \sum_{q=m}^{n}\sum_{i=1}^{\lfloor \frac{q}{m}\rfloor}(-1)^{i+1}\binom{n-q+1}{i}\binom{n-mi}{n-q}\text{,}$$
however I am getting some discrepencies against test cases I worked out by hand. For example, it works for $Z\left(7,6\right)=3$ and $Z\left(7,5\right)=8$, but it does not work for $\left(7,4\right)=16$ (the formulation above gives $20$). N.B.: my definitions of $n$ and $m$ are opposite those of [1]; $q$ is the same.
I believe it has something to do with double-counting some string permutations, but I haven't been able to work out what else I have to take out.
Update: I found a recursive formulation [2] that gives me the same result as my $\hat{Z}$ above:
$$ \tilde{Z}\left(n,m\right) = 2\tilde{Z}\left(n-1,m\right) + 2^{n-m-1}-\tilde{Z}\left(n-m-1,m\right) $$
Having found this independent formulation, I will have to revisit my counting and see if I've made a mistake somewhere.
Bonus points for an answer that works for arbitrary dictionaries, i.e. $W\left(a,n,m\right)$ where $a$ is the number of possible symbols in each position of the string. The original question would be equivalent to $Z\left(n,m\right) = W\left(2,n,m\right)$.


*

*[1] G.L., Number of binary strings containing at least n consecutive 1

*[2] Gerry Myerson, response to Number of bit strings with 3 consecutive zeros or 4 consecutive 1s
 A: You can use symbolic combinatorics to get a generating function. It is easier to get the number of strings that don't have $m$ consecutive ones, and subtract from the total.
Call $\mathcal{B}_{1^m}$ the set you are after, and $\mathcal{P}_{< m}$ the set of strings of less than $m$ ones, i.e., $\{ \epsilon, 1, 11, \dotsc, 1^{m - 1} \}$. We have the following symbolic equations:
$\begin{align}
\mathcal{P}_{< m}
  &= \mathcal{E} + \{ 1 \} + \dotsb + \{ 1 \}^{m - 1} \\
\mathcal{B}_{1^m}
  &= \mathcal{P}_{< m}
       + \mathcal{P}_{< m} \times \{ 0 \} \times  \mathcal{B}_{1^m}
\end{align}$
Essentially, one of your strings is either a string of less than $m$ ones, or a string of less than $m$ ones, a zero, and a string of the form we are looking for.
Use $z$ to mark length, so that the symbol itself is irrelevant, and write the equations for the generating functions:
$\begin{align}
P_{< m}(z)
  &= 1 + z + \dotsb + z^{m - 1} \\
  &= \frac{1 - z^m}{1 - z} \\
B_{1^m}(z)
  &= P_{< m}(z) + P_{< m} \cdot z \cdot B_{1^m}(z) \\
  &= \frac{1 - z^m}{1 - z} (1 + z B_{1^m}(z))
\end{align}$
Solving:
$$
B_{1^m}(z)
  = \frac{1 - z^m}{1 - 2 z + z^{m + 1}}
$$
What you are looking for is the coefficient of $z^n$ in this. There is no simple expression for that in the general case.
For $m = 1$ it is:
$$
B_1(z) = \frac{1 - z}{1 - 2 z + z^2} = \frac{1}{1 - z}
$$
so that $Z(n, 1) = 2^1 - 1 = 1$. No surprise there.
If $m = 2$ you have:
$$
B_{11}(z) = \frac{1 - z^2}{1 - 2 z + z^3} = \frac{1 + z}{1 - z - z^2}
$$
so $Z(n, 2) = 2^n - F_{n + 2}$, where $F_n$ is a Fibonacci number, defined by:
$$
F_0 = 0, F_1 = 1, F_{n + 2} = F_{n + 1} + F_n
$$
The cases $m = 3$ and $4$ are still doable, but are a horrible mess of roots when expanding the generating function in partial fractions.
A: It is easiest to count strings which don't contain the runs of ones. Suppose you start with a string of $m$ ones: $$1111111111\ldots1111111111\ \_$$ To ensure that there are no four consecutive ones, we will replace ones with zeros, hopping from left to right, and landing on the underscore.
Counting binary sequences without runs of a given length is equivalent to the stairs problem, with each footfall marking the zero which prevents a run.
Start by considering sequences without 1111. This is like climbing a staircase of height $m$, with steps of length 1, 2, 3, or 4. Let $f(n)$ be the number of ways of reaching step n. If you are at step n, you could have got there from steps $n-1, n-2, n-3,$ or $n-4$. Thus $$f(n) = f(n-1)+f(n-2)+f(n-3)+f(n-4)$$ and you start with $1, 2, 4, 8$:
$$1, 2, 4, 8, 15, 29, 56, 108$$
You need to get to step 5 at least, so add $15+29+56+108=208$. Therefore there are $256-208=48$ sequences which contain 1111.
As for the situation with $a>2$, the only modification is that each footfall can represent any of the $a-1$ digits which aren't $1$. Thus for base-$a$ strings, we'd use $$f(n)=(a-1)(f(n-1)+f(n-2)+f(n-3)+f(n-4))$$ instead.
