Loading the lesson
Loading the lesson
Search AllRounder.ai
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Learn it your way
A short class with Sarah and her students. The other ways are under More.
Sign up free to listen. Transcripts are free to read.
Today, we are talking about 'bad strings' in binary sequences, specifically those containing '000'. Can anyone tell me what a bad string would be?
I think a bad string would be like '0001' or '10000'.
Exactly! Those strings are invalid because they contain the substring '000'. Now, how can we count these bad strings?
Could we count all the binary strings and subtract the good ones?
Yes! We will use that strategy. First, we need to identify good strings, which do not contain '000'.
How do you even start counting the good strings then?
Great question! We'll categorize them based on their initial characters. If a string starts with '1', what can we say about the remainder?
The remainder must also be a good string!
Precisely! This starts forming a recurrence relation for good strings.
To summarize, we begin with the definition of bad strings as those containing '000' and outline our plan to count the valid (good) strings first.
Now, let's talk about the three disjoint cases for good strings. If we have a string of length n, and it starts with '1', that leaves us with g(n-1) valid strings, correct?
Right, because the first character is fixed to '1'.
Now, what if it starts with '01'?
Then we have g(n-2) because we're left with the next character and need to ensure no '000' substrings.
Great! Finally, if it starts with '00', what do we end up with?
The next character can only be '1'. So we have to count the good strings of length n-3, right? It's g(n-3).
Exactly! If we sum these, we can express our relationship as g(n) = g(n-1) + g(n-2) + g(n-3).
Recap: We've derived our function for good strings based on three cases by examining their leading characters.
Before we calculate our bad strings, we need to know some initial conditions. What do you think are the counts for g(0), g(1), and g(2)?
For g(0), there's one string, which is the empty string.
Correct! And g(1) includes '0' and '1'. How many are they?
That would make 2 for g(1).
Good. And what about g(2)? Which strings do we consider?
'00', '01', '10', '11.' Still no bad strings!
Excellent! So g(2) equals 4, making our initial conditions: g(0)=1, g(1)=2, g(2)=4.
To recap, we've derived our recurrence and established initial conditions—all vital to determine the number of bad strings next!
Now, let’s compute our bad strings! What’s the relation established for bad strings?
Isn't it that f(n) = 2^n - g(n)?
Exactly! So we need to derive g(n) to find bad strings. Can you calculate for n=3?
Using our relation, g(3) = g(2) + g(1) + g(0) = 4 + 2 + 1, which equals 7.
Correct! And how many total strings do we have for n=3?
For n=3, that's 2^3 = 8.
Thus, f(3) = 8 - 7 = 1, meaning there’s only one bad string of length 3.
To summarize, we computed the bad strings as f(n) = 2^n - g(n) and used initial conditions to help evaluate specific cases.
Good strings show their worth, with '000' out of birth.
Imagine a garden where the flowers never grow '000'. The good flowers only bloom when they are free from this pattern.
G for Good, B for Bad - Let’s just count the good and be glad!
GBS - Good Binary Strings don't have the Bad substring '000'.
Term
What is g(n)?
Click to flip
Term
Define initial conditions for g(n).
Click to flip
A binary string that contains the substring '000'.
A binary string that does not contain the substring '000'.
An equation that recursively defines a sequence based on previous terms.
A sequence of digits comprising only 0s and 1s.
The starting values required to compute further terms in a recursive sequence.
This section discusses how to count sequences of binary strings while considering specific patterns ('bad' strings that contain substring '000').
The section introduces the concept of bad strings in binary sequences, particularly focusing on counting strings of a given length that contain the substring '000'. It presents a recurrence relation as a method for establishing the number of invalid strings by breaking them down into manageable categories.
In this section, we focus on counting binary strings of length n that do not contain the substring '000'. Rather than directly counting the desired strings, we employ a more effective strategy: counting the complementary set — that is, the strings that do not contain '000' and then using the total number of possible strings to derive the count of bad strings.
We denote the number of bad strings of length n (strings containing '000') as 'f(n)'. We establish that the total number of n-length binary strings is given by '2^n'. The main task becomes to formulate a recurrence relation for 'g(n)', the number of good strings (those that do not contain '000').
More specifically, we categorize binary strings into three disjoint cases based on their prefix:
g(n-1) strings.n-2, should also exclude '000', giving g(n-2) strings.n-3, giving us g(n-3) valid configurations.From these categories, we derive a recurrence relation:
g(n) = g(n-1) + g(n-2) + g(n-3)This relation shows that the current number of good strings is the sum of good strings from previous lengths. The first few values help establish initial conditions:
To find the original 'f(n)', we use the total binary strings minus valid strings: f(n) = 2^n - g(n).