How many bit strings of length $n$ contain exactly $k$ blocks of "$10$"?

Question

How many bit strings of length $n$ contain exactly $k$ blocks of "$10$"?

My attempt: Let $F(n, k)$ be the number of bit strings of length $n$ that contain exactly $k$ blocks of $10.$ Note that for $k \neq0, $ $F(0, k) = F(1, k)= 0.$ Consider a bit string of length $n$ where $ n \geq 2.$

Every bit string either begins with:

1) $10$, or

2) $01$, $00$ or $11.$

In the former case, we get $F(n-2, k-1)$ since the remaining $n-2$ bits must contain $k-1$ blocks of $10$ in exactly $F(n-2, k-1)$ ways.

In the latter case, in either of the $3$ situations we get $F(n-2, k)$ since the remaining $n-2$ bits must contains $k$ blocks of $10$ in $F(n-2, k)$ ways.

Therefore for $n \geq 2, k \geq 1$ we have:

$F(n, k) = F(n-2, k-1)+ 3F(n-2, k)$.

For $k \geq 1$ let $A_k(x) = \displaystyle \sum_{n \geq2}F(n,k)x^n$ (and let $A_0(x)=1$) then multiplying the above recurrence by $x^n$ and summing over all $n \geq 2$ we get:

$A_k(x) = x^2 A_{k-1}(x) +3x^2A_{k}(x) $

$\Rightarrow A_k(x) = \dfrac{x^2}{1-3x^2} A_{k-1}(x)$

$\Rightarrow A_{k}(x) = \dfrac{x^{2k}}{(1-3x^2)^k} $

$\Rightarrow F(n, k) = [x^n] A_k(x)$

$\Rightarrow F(n, k) = [x^n] \dfrac{x^{2k}}{(1-3x^2)^k}$

$\Rightarrow F(n, k) = [x^{n-2k}] \displaystyle \sum_{r \geq 0} \binom{k+r-1}{r} 3^r x^{2r}$

which clearly gives a wrong answer for odd $n$. Could somebody point out where in the above calculation have I gone wrong? Thanks in advance.

Answer 1

Essentially this amounts to finding the places where the string switches from a run of $1$'s to a run of $0$'s. Note that there are $n-1$ places where such a switch may occur (between each pair of numbers). In any event, there must be $k$ places where the string switches from $1$ to $0$:

• If the string starts and ends with $0$, then (since it starts with $0$) there must also be $k$ places where it switches from $0$ to $1$. There are $\binom{n-1}{2k}$ ways of making these choices.

• If the string starts with $1$ and ends with $0$, then there must (since it ends in $0$) also be $k-1$ places where it switches from $0$ to $1$; there are $\binom{n-1}{2k-1}$ ways of making these choices.

• If the string starts with $0$ and ends with $1$, then there must (since it starts with $0$) also be $k+1$ places where it switches from $0$ to $1$; there are $\binom{n-1}{2k+1}$ ways of making these choices.

• Finally, if the string starts and ends with $1$, there must (since it ends with $1$) also be $k$ places where it switches from $0$ to $1$. There are $\binom{n-1}{2k}$ ways of making these choices.

So finally, the total number of such strings is $$\binom{n-1}{2k} + \binom{n-1}{2k-1} + \binom{n-1}{2k+1} + \binom{n-1}{2k} = \binom{n}{2k} + \binom{n}{2k+1} = \binom{n+1}{2k+1}.$$