Question

Consider binary strings with n digits (for example, if n=4, some of the possible strings are 0011,1010,1101, etc.) Let Zn be the number of binary stri

Bivariate numerical data
ANSWERED
asked 2021-03-07
Consider binary strings with n digits (for example, if n=4, some of the possible strings are 0011,1010,1101, etc.)
Let Zn be the number of binary strings of length n that do not contain the substring 000
Find a recurrence relation for Zn
You are not required to find a closed form for this recurrence.

Expert Answers (1)

2021-03-08

Consider such a sequence of n digits.
If the first digit is 1, then we must not have a substring 000 in the remaning part of this sequence. Thus, we have Zn-1 such sequences.
If the first digit is 0, then we look at the second digit. If the second digit is 1, then this sequence starts with 01, meaning that we must not have a substring 000 in the remaning n—2 digits. Therefore, there are Zn-2 such sequences.
If the second digit is 0, then this sequence starts with 00. This means that the third digit must be 1 (otherwise, we would have 000 in this sequence). Therefore, this sequence starts with 001, meaning that we must not have 00 asa substring in the remaining n —3 digits. Thus, there are Zn-3 such sequences.
This covers all cases. Therefore, the recurrence relation is \(Zn=Zn-1+Zn-2+Zn-3\)

49
 
Best answer

expert advice

Have a similar question?
We can deal with it in 3 hours

Relevant Questions

asked 2021-01-31

(a) Find a closed-form solution for this recurrence relation: \(an=2\cdot an−1−n+1\) with \(a1=2a\)
(b) Prove that your closed-form solution is correct.

asked 2021-08-02
Ben and Carl are remembering how you told them that a 0 at the end of a whole number makes it ten times greater. They remember that 420 is ten times bigger than 42, for example. They wonder if the same thing works with decimals. Ben argues that putting a 0 at the end of a decimal number makes it ten times greater. Carl says, "No. You've gotta sneak it in right after the decimal point and push everything to the right." How do you help them to see what's true and what's not?
asked 2021-07-30
Exercise 1: Counting binary strings.
Count the number of binary strings of length 10 subject to each of the following restrictions.
There is only one binary string of length ten with no 1's: 00000000000. There are \(\displaystyle{2}^{{{10}}}\) binary strings of length ten. Therefore the number of binary strings of length ten with at least one 1 is \(\displaystyle{2}^{{{10}}}-{1}\).
(b)
The string has at least one 1 and at least one 0.
(c)
The string contains exactly five 1's or it begins with a 0.
Exercise 2: Counting integer multiples.
(b)
How many integers in the range 1 through 140 are integer multiples of 2, 5, or 7?
asked 2021-05-05
If John, Trey, and Miles want to know how’ | many two-letter secret codes there are that don't have a repeated letter. For example, they want to : count BA and AB, but they don't want to count“ doubles such as ZZ or XX. Jobn says there are 26 + 25 because you don’t want to use the same letter twice; that’s why the second number is 25.
‘Trey says he thinks it should be times, not plus: 26-25, Miles says the number is 26-26 ~ 26 because you need to take away the double letters. Discuss the boys’ ideas, Which answers are correct, which are not, and why? Explain your answers clearly and thoroughly, drawing ‘on this section’s definition of multiptication.. -
...