Chapter 6, Problem 1RQ

Explain how the sum and product rules can be used to find the number of bit strings with a length not exceeding

To determine

Explain how the sum and product rules can be used to find the number of bit strings with a length not exceeding $10$.

Answer to Problem 1RQ

Total number of string length $=2047$.

Explanation of Solution

Given:

Length of string should be less than $10$

Concept used:

Number of bit string of length $n=2^n$

Calculation:

Here, length of string $\le 10$

Number of bit string of length $1+$ number of bit string of length $2+\mathrm{...........}+$ number of bit string of length $10$.

$\begin{array}{l}=2^0+2^1+2^2+{\mathrm{...........2}}^{10}\\ =1+2+4+8+16+32+64+128+256+572+1024\\ =2047\end{array}$

Product rule.

Suppose each place is to be occupied either by zero or by $1$.

Then $m$ places can be filled in first place by two ways, 2^nd place by two way, $\mathrm{.....}{n}^{th}$ place by $2$ ways.

So, total number of strings $=2\times 2\times 2\times \mathrm{...........}\times 2$

$=2^m$

So, bit string of length $0=2^0=1$

Bit string of length $1=2^1=2$

Bit string of length $2=2^2=4$

Bit string of length $10=2^{10}=1024$

So, total number of strings length $\le 10=2^0+2^1+2^2+\mathrm{..........}+2^{10}=2047$

Conclusion:

Total number of string length $=2047$.