How many bit strings of length ten both begin and end with a 1?

Below are the rules that we can use for this type of exercise.

THE PRODUCT RULE: Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.

THE SUM RULE: If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same as any of the set of n2 ways, then there are n1 +n2 ways to do the task.

The definitions above are from the textbook: Discrete Mathematics and its applications by Rosen.

The easier way to solve this type of exercise for me is to express the problem as the rule’s

definitions. That’s why I always start by having the definitions clear.

We know that the bit strings must begin and end with 1 and the length is 10. This is the same as answering how many bit strings of length 8 are there.

Why?

If you take any bit string of length 8 and add a 1 at the beginning and another 1 at the end, then you know how many of the strings have a length of ten and start and end with a 1.

So, how many bit strings of length 8 are there?

We can choose the first bit in two ways (1 or 0). Also, we can choose the second bit in two ways (1 or 0), and so on.

So, we can do the first task in 2 ways. For each of the 2 ways we can do the first task, there are 2 ways we can do the second one, and so on.

So, it is clear we must use the product rule.

Answer:

There are 256 (2x2x2x2x2x2x2x2=2⁸) bit strings of length 10 that begin and end with 1.

Related exercises: