1

Let $f(n)$ denote the number of bitstrings (words from the alphabet {$0, 1$}) of length $n$ which do not contain three consecutive zeros. Write a linear recurrence of order $3$ with adequate initial conditions for $f(n)$. Verify that it gives the correct answer for $n = 6$.


Can anyone show me how to solve this question? I'm really struggling on this question

hpotter054
  • 31

3 Answers3

1

For the sake of simplicity let $F(n)$ the set associated to the strings we want to count.

Let $n \geq 4$ and $w \in F(n)$. We have the following disjoint possibilities for the end of $w$:

  • it finishes with 1, then the first $n-1$ digits form a word in $F(n-1)$
  • it finishes with 10, then the first $n-2$ digits form a word in $F(n-2)$
  • it finishes with 100, then the first $n-3$ digits form a word in $F(n-3)$

Finally we have $$f(n)=f(n-1)+f(n-2)+f(n-3)$$

These numbers are interestingly called Tribonacci numbers!

Verification:

  • $f(1)=2$,
  • $f(2)=4$,
  • $f(3)=7$,
  • $f(4)=13$ (0010, 0011, 0100, 0101, 0110, 0111, 1001, 1010, 1011, 1100, 1101, 1110, 1111)
  • $f(5)=24$ (00100, 00101, 00110, 00111, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10010, 10011, 10100, 10101, 10110, 10111, 11001, 11010, 11011, 11100, 11101, 11110, 11111)
  • $f(6) = 44$ (001001, 001010, 001011, 001100, 001101, 001110, 001111, 010010, 010011, 010100, 010101, 010110, 010111, 011001, 011010, 011011, 011100, 011101, 011110, 011111, 100100, 100101, 100110, 100111, 101001, 101010, 101011, 101100, 101101, 101110, 101111, 110010, 110011, 110100, 110101, 110110, 110111, 111001, 111010, 111011, 111100, 111101, 111110, 111111)

And we have $44 = 24 + 13 + 7$

NB I first found that $f(n)=2f(n-1)-f(n-4)$, which is also correct but of order 4 :)

fonfonx
  • 4,282
1

I'm not sure whether generating functions might be too advanced for the OP, but I thought I'd show how that would answer the question...

So, first consider the generating function for sequences which are either empty, or begin with a 0 and end with a 1. Such a sequence is a repetition of 0 of more blocks, each consisting of 1 or 2 0's followed by 1 or more 1's. So, the generating function for 0 blocks is 1; the generating function for 1 block is $(x+x^2) \cdot (x + x^2 + x^3 + \cdots) = (x+x^2) \cdot \frac{x}{1-x}$; the generating function for 2 blocks is the square of that; and so on. So, the overall generating function is $$ \sum_{k=0}^\infty \left[(x+x^2) \cdot \frac{x}{1-x}\right]^k = \frac{1}{1 - (x+x^2) \cdot \frac{x}{1-x}} = \frac{1-x}{1 - x - x^2 - x^3}. $$

Now, to add the possibility of starting with some 1's and ending with some 0's, 0 or more 1's at the start multiplies the generating function by $1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$; and adding 0, 1, or 2 0's at the end multiplies the generating function by $1 + x + x^2$. Therefore, the final generating function is $$ \sum_{k=0}^\infty f(k) x^k = \frac{1 + x + x^2}{1 - x - x^2 - x^3}. $$

From this, you can almost directly read from the denominator a recurrence relation of: $$ f(n) = f(n-1) + f(n-2) + f(n-3). $$

Daniel Schepler
  • 20,364
  • It later occurred to me it would be easier to find the generating function by breaking down into blocks of 1, 01, or 001 optionally followed by either 0 or 00. Then it doesn't end up being too notionally different from fonfonx's answer, though. In the end, I decided to keep this answer as is, to show that even if you're not clever enough to simplify the blocks in that way, and go with the more obvious way to break it down into blocks, the algebra still simplifies for you with not that much extra work. – Daniel Schepler May 25 '17 at 21:32
  • Another solution with generating functions would be: build the deterministic finite state machine where the state is ${ 0, 1, 2 }$ according to how many 0's have come immediately before; and let $f_i(x)$ be the generating function for strings accepted by state $i$. Then $f_0(x) = 1 + x f_0(x) + x f_1(x)$; $f_1(x) = 1 + x f_0(x) + x f_2(x)$; and $f_2(x) = 1 + x f_0(x)$. Then you just need to solve that system of linear simultaneous equations - haven't worked out the full solution, but it's not too hard to calculate the determinant of the coefficient matrix is $1 - x - x^2 - x^3$. – Daniel Schepler May 25 '17 at 21:37
0

Let $f(n)$ be the number of strings of length $n$.

Consider the number of zeros at the end of the string of length $n$.

Consider the last two digits.

If they are 11 or 01, the string of length n+1 can end with a zero or 1.

If they are 10 the string of length n+1 can again end with a zero or 1.

If they are 00, the string of length n+1 can only end with a 1.

Does this help?

You may want to consider $f_{ij}(n)$ to be the number of strings of length $n$ that end in $ij$, where $ij = 00, 01, 10, 11$ and get recurrences for each.

marty cohen
  • 107,799