GATE Overflow Test Series | Discrete Mathematics | Test 2 | Question: 8

Question

How many bit strings of length $7$ contain more $0$’s than $1$’s?

• A. $93$
• B. $84$
• C. $64$
• D. none of these

Comments

Since the cases are symmetric, the cardinality of set of strings with more $0’s$ than $1’s$ will be equal to the cardinality of set of strings with more $1’s$ than $0’s$. (replacing $0$ with $1$ and $1$ with $0$ will create a bijection between these sets)

Since $7$ is odd, so there will not be a case with equal $0’s$ and $1’s$.

So, we can say that of all the $2^7$ cases, half of them will have more $0’s$ than $1’s$

half of $2^7$ = $\frac{2^7}{2} = 2^6 = 64$ cases with more $0’s$ than $1’s$

Answer 1

Number of bit strings of length $7$ containing more $0$'s than $1$'s

$\quad = $Number of bit strings containing exactly $4\;\;0$'s

$\quad+ $Number of bit strings containing exactly $5\;\;0$'s

$\quad+ $Number of bit strings containing exactly $6\;\;0$'s

$\quad+ $Number of bit strings containing exactly $7\;\;0$'s

$\qquad = \binom{7}{4} + \binom{7}{5} + \binom{7}{6} + \binom{7}{7} $  

$\qquad =35 + 21 + 7 + 1 = 64.$

Answer 2

Total Number of 7 length bit strings are 2^7 = 128

Exactly half of them will have more 0s then 1s, i.e. 64 .

 

So answer is 64.