# How many bit strings of length $n$ contain exactly $k$ blocks of “$10$”?

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.

• If the string begins $01$ or $11$, then the next element could be $0$, which creates an additional $10$ that you have not taken into account in your calculations. – rogerl Oct 14 '17 at 13:22
• Right, the recurrence itself is wrong. Any idea what the correct approach, via generating functions or otherwise, entails? – Aryaman Jal Oct 14 '17 at 14:00

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}.$$

Thanks for the insight. I used a similar technique for a similar problem. I wrote this up for my assignment which is due in a week. Although I believe that I found the recurrence relation correctly, I am unable to go about extracting the coefficients from a quadratic raised to a negative k-th power. Could you please be able to help me how to proceed?

Let $f(n, k)$ represent the number of strings made of $\{a, b\}$ where $k$ is the number of occurrences of ''$ab$'' in a string of length $n$. Note that the string can begin with $ab, aa, bb$, or $ba$. If it begins with $ab$, then there are exactly $f(n-2, k-1)$ number of strings remaining. If it begins with $bb$, then there are exactly $f(n-2, k)$ strings remaining. If it begins with $aa$, or $ba$, then there are exactly $f(n-1, k)$ strings remaining. Thus we have the recurrence relation $f(n, k) = f(n-2, k-1) + f(n-2, k) + 2f(n-1, k)$. Trivially enough, we have that $f(0, k) = f(1, k) = 0$ for any non-zero $k$. Define $A_{k}(x) = \displaystyle \sum_{n=2}^{\infty} f(n, k)x^{n}$. Note that $A_{0}(x) = \displaystyle \sum_{n\geq 2} f(n, 0)x^{n} = \displaystyle \sum_{n \geq 2} (n+1)x^{n}.$ Thus $A_{k}(x) = \sum_{n=2}^{\infty} \Big[ f(n-2, k-1)x^{n} + f(n-2, k)x^{n} + 2f(n-1, k)x^{n}\Big].$

It follows that $A_{k}(x) = \displaystyle \sum_{n=2}^{\infty} x^{2} f(n, k-1)x^{n} + x^{2} f(n, k)x^{n} + 2x f(n, k)x^{n}$

Thus, \begin{align*} A_{k}(x) = x^{2} A_{k-1}(x) + x^{2} A_{k}(x) + 2x A_{k}(x)\\ \implies A_{k}(x) = \displaystyle \frac{x^{2}}{1+2x-x^{2}}A_{k-1}(x)\\ \implies A_{k}(x) = \displaystyle \frac{x^{2}}{1+2x-x^{2}} \cdot \Big( \displaystyle \frac{x^{2}}{1+2x-x^{2}} A_{k-2}(x) \Big) \\ \therefore A_{k}(x) = \displaystyle \Bigg(\frac{x^{2}}{1+2x-x^{2}}\Bigg)^{k} \displaystyle (n+1) \sum_{n \geq 2} x^{n}\\ \therefore A_{k}(x) = (n+1) \displaystyle \frac{x^{2k+2}}{(1+2x-x^{2})^{k} (1-x)}\\ \end{align*} But $f(n, k) = [x^{k}] A_{k}(x)$ \begin{align*} \therefore f(n, k) = [x^{n-2-2k}] \displaystyle (n+1) \frac{1}{(1+2x-x^{2})^{k} (1-x)}\\ \therefore f(n, k) = [x^{n-2k-2}] (n+1) \displaystyle (1+2x-x^{2})^{-k} (1-x)^{-1}\\ \end{align*}