Combinatorics – How Many Bit Strings of Length 8 Start with 00 or End with 1?

combinatoricsdiscrete mathematics

How many bit strings of length $8$ start with $00$ or end with $1$?

I know about product rule and sum rule but I'm unsure how to incorporate it into this.

Would it be like this$? (x$ being either $1$ or $0):$

For starting with $00:$ $0 0 x x x x x x$

  • $ 2^6 $ combinations?

For ending with $1:$ $x x x x x x x 1$

  • $ 2^7 $ combinations?

Best Answer

Yes, you are correct about each separate case, but to find the number of bit strings of length $8$ that either start with two zeros or end in a one (or both), we cannot simply *add* the two counts and say "we're done." We can use the sum rule, but with modifications:

If we add the counts $2^6 + 2^7$, we need to also account for having double counted those bit strings which both start with two zeros and end in a one: Subtract that number of strings from the sum, and you'll have your answer.

Clarification: The number of bit strings of length 8 of the form 0 0 x x x x x 1 will have been counted $(1)$ in the first total of all strings of the form 0 0 x x x x x x, and $(2)$ it will have been counted in the second total of all strings of the form x x x x x x x 1. So we need to subtract the number of strings of the form 0 0 x x x x x 1 from the combination of the first count and second count, so that they are only counted once.

So, we count the number of bit strings of the form: 0 0 x x x x x 1,

and just as you computed the first two counts, we see that there are $2^5$ such strings which have been counted twice, so we will subtract that from the sum of the first two counts.

Total number of bit strings that start with two zeros $(2^6)$ or end in a one $(2^7)$ or both ($2^5$):

$$ 2^6 + 2^7 - 2^5$$