How many bit strings of length $20$ have either less than ten $1$’s or contain $11$ as a substring? The answer is $2^{20}-2$.
I am wondering how did they get $2$? Because if a string contains $11$ as a substring, then out of $20$ positions $2$ of them are fixed. Furthermore if the string has more than ten ones in it, then the solution to get those ten positions specifically will be $_{20}C_{10}$. (Note I am not taking the substring case into consideration here as of now.)
Hence the number of strings will be $2^{20}-\ _{20}C_{12}$. But the answer is $2^{20}-2$. Can someone give me a better explanation? Or is my chain of reasoning wrong?
2^20-2
could be written$2^{20}-2$
to be written as $2^{20}-2$. $\endgroup$