banner

How many bit strings of length seven either begin with two 0s or end with three 1s?

The purpose of this question is to find the number of bit-strings of length $7$ beginning with two $0$s and ending with three $1$s.

The sequence of binary digits is usually called a bit-string. The number of bits signifies the value length in the sequence. A bit-string having no length is regarded as a null string. Bit-strings are useful for representing sets and manipulating binary data. The bit-string elements are labeled left to right from $0$ to one minus the total number of bits in the string. When converting a bit string to an integer, the $0^{th}$ bit corresponds to the $0^{th}$ exponent of two, the first bit corresponds to the first exponent, and so forth.

In discrete mathematics, the subsets are represented by the bit-strings in which $1$ indicates that a subset contains an element of a respective set and $0$ indicates that the subset does not contain that element. The representation of a set by a bit-string makes it simple to take complements, intersections, unions, and set differences.

Expert Answer

Let the set of bit-strings having the length $7$ and starting with two zeros be represented by $A$, then:

$|A|=1*1*2*2*2*2*2=2^5=32$

Let the set of bit-strings having the length $7$ and starting with three ones be represented by $B$, then:

$|B|=2*2*2*2*1*1*1=2^4=16$

Now, the set of the bit-strings of length $7$ starting with two $0$s and ending with three $1$s is given by:

$|A\cap B|=1*1*2*2*1*1*1=2^2=4$

Finally, the number of bit-strings of length $7$ either starting with two $0$s and ending with three $1$s is:

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B|=32+16-4=44$

Example

How many numbers between $1$ to $50$ are divisible by either $2, 3$ or $5$? Assume $1$ and $50$ to be inclusive.

Solution

This example gives a clear idea of how the Sum Principle (Inclusion Exclusion) works.

Let $A_1$ be the set of numbers between $1$ to $50$ which are divisible by $2$ then:

$|A_1|=\dfrac{50}{2}=25$

Let $A_2$ be the set of numbers between $1$ to $50$ which are divisible by $3$ then:

$|A_2|=\dfrac{50}{3}=16$

Let $A_3$ be the set of numbers between $1$ to $50$ which are divisible by $5$ then:

$|A_3|=\dfrac{50}{5}=10$

Now, $A_1\cap A_2$ will be a set where each element between $1$ to $50$ is divisible by $6$, and so:   

$|A_1\cap A_2|=8$

$A_1\cap A_3$ will be a set where each element between $1$ to $50$ is divisible by $10$, and so: 

$|A_1\cap A_3|=5$

$A_2\cap A_3$ will be a set where each element between $1$ to $50$ is divisible by $15$, and so: 

$|A_2\cap A_3|=3$

Also, $A_1\cap A_2\cap A_3$ will be a set where each element between $1$ to $50$ is divisible by $30$, and so: 

$|A_1\cap A_2\cap A_3|=2$

Finally, using the sum principle to get the union as:

$|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|+|A_1\cap A_2\cap A_3|$

$|A_1\cup A_2\cup A_3|=25+16+10-8-5-3+2$

$|A_1\cup A_2\cup A_3|=37$

5/5 - (6 votes)