0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rogerl Oct 14 '17 at 13:22
  • $\begingroup$ Right, the recurrence itself is wrong. Any idea what the correct approach, via generating functions or otherwise, entails? $\endgroup$ – Aryaman Jal Oct 14 '17 at 14:00
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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*}

This is the part where I'm stuck at. Please help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.