Its in the counting techniques section
2 Answers
-
This is equal to
The number of bit strings of length 7 beginning with two 0’s
+ the number of bit strings of length 7 ending with three 1’s
– the number of bit strings of length 7 beginning with two 0’s *and* ending with three 1’s.
If we specify the first two bits, that leaves 5 free bits, so there are
2^5 = 32 bit strings of length 7 beginning with two 0’s
If we specify the last three bits, that leaves 4 free bits, so there are
2^4 = 16 bit strings of length 7 ending with three 1’s.
If we specify the first two and last three bits, that leaves 2 free bits, so there are
2^2 = 4 bit strings of length 7 beginning with two 0’s and ending with three 1’s.
So our calculation is
32 + 16 – 4 = 44 strings.
—-
EDIT:
We need to subtract the strings that begin 00 and end 111, or else we count them twice.
For instance, 0010111 is a string that begins with two 0’s so it’s one of 32.
It also ends in three 1’s so it’s one of the 16.
Unless we subtract the number of such doubly-qualified strings, we count them twice.
This is called the “Inclusion-Exclusion Principle.”
-
If it begins with two 0’s , then the rest five bits can be 0 or 1 …….. 2^5 or 32 ways
If it ends with three 1’s , then the rest four bits can be 0 or 1 ………. 2^4 or 16 ways
total ways = 32 + 16 = 48 ways
