# Permutations of bit-sequence(discrete math)

How many bit-squences with length 8 has 1 as it's first bit and 00 as the two last bits(e.g $1011 1100$)

I thought the solution to this problem would be $1 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 2^5$, but my teacher proposed the following solution:

amount that starts with 1: $1 * 2 * 2 * 2 * 2 * 2 * 2 = 2^7$

amount that ends with 00: $2 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 2^6$

amount that starts with 1 and ends with 00: $1 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 2^5$

answer = $2^7 + 2^6 - 2^5 = 160$.

Isn't the amount of bit-squences that starts with 1 and ends with $00$ the answer to the question "How many bit-squences with length 8 has 1 as it's first bit and $00$ as the two last bits"? Isn't the answer simply $2^5$ ?

## 1 Answer

Yes, the answer is simply $2^5$. Your teacher is calculating some other count.

OK, your teacher is calculating the count of those sequences which start with 1 or end with 00. And she's using the inclusion exclusion principle for counting them.

Inclusion-Exclusion Principle

Maybe you misunderstood the problem. You thought there was an and there in the problem statement but it's actually an or.

• ok thank you, the teacher made a mistake. She wrote and, but meant or. – Carefullcars Nov 6 '15 at 22:12