# Find the number of bit strings which start with four zeroes and end with three ones

Count the number of bit strings that start with four $0$'s or end with three $1$'s if the length of the bit string is:

1. $7$
2. $4$

2. For 7 use inclusion exclusion principle, with event $A$ as getting four zeros in front and event $B$ as 3 one's in the end. So answer will come out to be $2^3+2^4-1$.
In general for lengths $n>=7$ the answer would be $2^{n-4}+2^{n-3}-2^{n-7}$.
• 2. is even simpler to count than using the inclusion exclusion principle. A matching string either starts with 0000 or not. If it doesn't it must end in 111. There are $2^3$ of the first, $2^4-1$ of the second. – copper.hat Feb 16 '15 at 18:18
• @sasha if the length is 8 would the answer be $2^4+2^5-1?$ – Csci319 Feb 19 '15 at 21:35