3
$\begingroup$

I want to find the number of bit strings of length $n$ in which any two consecutive $1$'s are separated by an even number of $0$’s

My attempt:

Let $a_n$ be the required number

Take two cases:

  • The string ends with $1$. In this case, the string must end with $001$. Number of such strings is $a_{n-3}$
  • The string ends with $0$. Number of such strings is $a_{n-1}$

Mistake which I found but can't fix in my approach:

For $n=5$, $10$ is a valid length 2 string, appending $001$ doesn't give a valid length $5$ string.

$\endgroup$
5
  • $\begingroup$ string ending with $1$ can end with $11, 111, 1111, \dots $ also $\endgroup$ – ab123 Oct 2 '18 at 9:24
  • $\begingroup$ Is a string like $00010011000010$ valid? That is, can we have an even number of $0$s between any two consecutive ones, but an odd number of zeroes at the beginning or end of the string? $\endgroup$ – Michael Lugo Oct 2 '18 at 13:56
  • $\begingroup$ @ab123 No, there has to be atleast 2 zeroes between two ones $\endgroup$ – sc_ Oct 2 '18 at 14:31
  • $\begingroup$ @Michael Lugo Yes, those are valid $\endgroup$ – sc_ Oct 2 '18 at 14:32
  • $\begingroup$ The answer is give the recurrence relation $T ( n ) = T ( n - 1 ) + T ( n - 2 ) + 1 , n \geq 2$ $\endgroup$ – sc_ Oct 12 '18 at 16:05
0
$\begingroup$

Form a graph with $6$ nodes: $S, A, B, C, D, E$.

  • $S$ the starting state (we're here when the string is empty)
  • $A$ a state for beginning zeros
  • $B$ a state where you have just gotten a one (and the string isn't already rejected)
  • $C$ counting zeros after a one, have odd amount
  • $D$ counting zeros after a one, have even amount
  • $E$ the rejecting state

And the transition matrix, when indexed by this order of states (check each transition and justify them yourself)

$$ P = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 \\ \end{bmatrix} $$

Now $a_n = 2^n-P^n_{S, E}$. That is, we are looking for the top-right element of $P^n$, it gives the number of walks of length $n$ on the graph that end up in the rejecting state and start from the state $S$.

We can diagonilize $P$ to solve for a formula. Eigenvalues are

$\lambda_1 = 2$
$\lambda_2 \approx 1.32472$
$\lambda_3 = 1$
$\lambda_4 \approx 0.662359 + 0.56228 i$
$\lambda_5 = \bar{\lambda_4}$
$\lambda_6 = 0$

Here $\lambda_2, \lambda_4$ and $\lambda_5$ are the roots of $x^3-x-1$ which we get by dividing the exact roots away from the characteristic polynomial: $\frac{x^6 - 3x^5 + x^4 + 2x^3 + x^2 - 2x}{x(x-1)(x-2)}$.

But then you would need to solve the eigenvectors and the inverse of that matrix and for me it looks pretty messy. Anyway, I think the sequence $a_n$ is this OEIS sequence and there a recurrence is given and from that it is easier to solve for the formula (for example via generating functions).

$\endgroup$
0
$\begingroup$

Here's another approach. Use the graph as in my previous answer, but don't bother with the starting state $S$, we can start at $A$ (we start with no zeros and then can have a zero or a one so it's OK). The graph looks like this:

graph for finding which binary strings to reject and which approve

Let's define $a_n, b_n, c_n, d_n, e_n$ to be the number of walks on the graph that start from $A$ and after $n$ steps end up in $A, B, C, D, E$. What we want to calculate is the total number of approved strings:

$$x_n = a_n+b_n+c_n+d_n.$$

We notice these facts:

  • $a_n = 1$
  • $b_n = b_{n-2}+b_{n-3}$, and $b_0=0, b_1=b_2 = 1$
  • $c_n = c_{n-1}+c_{n-2}-c_{n-4}$, and $c_0=c_1=0, c_2=c_3=1$
  • $d_n = c_{n-1}$, and $d_0=0$

The first is obvious, since only the string $00\dots0$ can end up in $A$.
Also, the last since we can only arrive to $D$ from $C$.

Let's prove the other two inductively on $n$. First notice a helpful equation from the fact that we can arrive to $C$ from $B$ or from $D$:

  • $\pmb{c_{m}} = b_{m-1} + d_{m-1} = \pmb{b_{m}+b_{m-1}-1}$, since $b_{m} = d_{m-1}+1$ (remember $a_m = 1$)

Let's now do the induction step for $b_{n+1}$:

$$b_{n+1} = a_{n}+ d_{n} = 1 + c_{n-1} = b_{n-1}+b_{n-2}$$

Then for $c_{n+1}$. I found it easier to start with what we want, that is:

$$c_n+c_{n-1}-c_{n-3} \\ = b_n+b_{n-1}-1 + b_{n-1}+b_{n-2}-1 - (b_{n-3}+b_{n-4}-1)\\ = b_n+b_{n-1}-1 + b_{n-1}+b_{n-2}-1 - b_{n-1} +1 \\ = b_n-1+ b_{n-1}+b_{n-2}\\ = b_n-1+ b_{n+1}\\ = c_{n+1}. $$

The base cases can be checked easily (for example with the matrix approach), here are how the sequences begin

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1...
0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28...
0, 0, 1, 1, 2, 3, 4, 6, 8, 11, 15, 20, 27, 36, 48...
0, 0, 0, 1, 1, 2, 3, 4, 6, 8, 11, 15, 20, 27, 36...

Then finally we also find a recursion for the sum of these, it is actually the same recurrence as for $c$ and $d$

$$x_n = x_{n-1}+x_{n-2}-x_{n-4} \text{ and } x_0=1, x_1=2, x_3=3$$

Let's prove this with induction and also here it's easier to start with the right hand side. The $c$ and $d$ terms gather nicely, $a$ is just the $1$ that survives and noticing that $b_{n}-b_{n-3}=b_{n-2}$ and then that $b_{n-2}+b_{n-3}=b_{n}$ proves the result.

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