16.2.1. Counting Bad Strings

In question 2 you have to find out the recurrence relation for the number of bit strings of length n that contain the substring '000'. It might have more than 1 occurrence of '000' as well. In fact, a string of length n consisting of all 0’s is a valid string.

In this section, we are tasked with determining how many bit strings of a specific length (n) include the substring '000'. A string like '00000' would be considered valid because it contains multiple instances of '000'. This exploration helps us understand how to quantify and analyze strings that meet specific criteria, which is common in combinatorial problems.

Imagine building a tower with blocks, where each type of block represents a distinct bit (0 or 1). The requirement is to ensure that somewhere in your tower, there exists a sequence of three consecutive blocks of type '0'. Just as you would check for the placement of blocks in your physical tower, we check arrangements of bits in strings.

Instead of counting the number of strings containing '000', we will count the number of strings of length n not containing '000'. Here, the term bad string denotes strings that do not have an occurrence of '000'. So, I call or denote the sequence of all n length bit strings not containing '000' by this sequence and this is the n-th term of such sequence.

To simplify the counting process, we switch our focus from the number of strings containing '000' to those that do not contain it, referred to as 'bad strings'. This approach allows for a clearer perspective in formulating a recurrence relation, as it's often easier to assess what is NOT present than to track multiple valid occurrences.

Think of a game where you try to keep your room clean by avoiding clutter. Instead of counting the items (toys, clothes) you want to keep, you count the clutter you don't want. This is an easier task and can provide insight into how to maintain a tidy space.

There are 3 disjoint categories of bit strings of length n not containing '000'. Category 1 consists of those strings of length n that start with 1. If it starts with 1, then the remaining portion must not have any occurrence of '000'.

We categorize bad strings into three groups to systematically approach counting. The first category includes those that start with '1'. The crucial point here is that after placing '1', the rest of the string must independently avoid forming '000', allowing us to apply previous findings to this smaller problem.

Imagine sorting fruits. If you decide to place a specific fruit (like an apple) at the front, the rest of your basket (the remaining fruits) must still be arranged in a particular way (without letting any rotten fruits group together).

Category 2 of bad strings are those that start with '01' and in that case, the remaining n-2 bit positions should not have any occurrence of '000'. Category 3 of bad strings where the first 2 positions are 0, and in that case, the third position cannot be 0.

The second category allows strings beginning with '01', maintaining that the rest of the string avoids '000'. The third category has two starting 0s, followed by a required 1 to ensure the sequence remains 'bad'. Each category gives a clear structure to the overall counting process, ensuring we systematically consider all cases.

Continuing with the fruit basket analogy, if the first two fruits are bananas, you can’t put another banana next, but must present a different fruit (like an orange) to avoid spoiling the pattern. This shows us how we can carefully curate our selections.

The number of bad strings of length n will be the sum of the number of bad strings of length n-1, n-2, and n-3, leading to our recurrence equation for the sequence.

By analyzing each category, we find the total number of non-'000' strings of length n is simply the sum of valid counts from previous lengths (n-1, n-2, and n-3). This method unveils a recurrence relation that will help calculate the number of bad strings more efficiently by using previous results.

Consider the incremental building of a wall with different blocks. Each layer (n) can only be built by correctly stacking the previous layers (n-1, n-2, and n-3) without repeating certain patterns. The walls built in previous attempts serve as a model for your current project.

Since this is an equation of degree 3, we need 3 initial conditions: s(1) = 2, s(2) = 4, and s(3) = 7.

To use the recurrence effectively, we need initial conditions that anchor our calculations and serve as a base for future results. These conditions represent the number of bad strings for smaller lengths—providing a clear starting point for extending to greater lengths.

Imagine starting a construction project. You first lay out the foundation (initial conditions) properly to ensure that subsequent floors (larger string lengths) can be built reliably using the pattern set by the base.

--