# Counting bit strings of length $70$ with two restrictions

There is a bit string of length $70$. At least one of the following restrictions must apply:

i)The first $9$ bits cannot contain exactly $5$ 1s

ii)The first $49$ bits cannot contain exactly $27$ 1s.

How many combinations are there?

My first instinct is to do the following: $2^{70}$ and subtract some number of combinations.

I am not sure how to go about this or if there is a more elegant way. I am currently getting the following result, but I am not confident in it because I believe that there may be some double counting:

$2^{70}-(\binom{9}{5}+\binom{49}{27})=$

$997,056,092,945,595,000,000$

• Do you mean that the first $9$ bits cannot contain exactly $5$ 1s or at least $5$ 1s? Likewise, do you mean that the first $49$ bits cannot contain exactly $27$ 1s or at least $27$ 1s? – N. F. Taussig Apr 4 '18 at 21:29
• Yes exactly that amount so the first $9$ bits can contain anything other than $5$ 1's the same rule applies for the first 49 bits as well – OneNoteMan Apr 4 '18 at 21:31
• Showing how you arrived at that number would make it easier for readers of this question to determine if you made an error. – N. F. Taussig Apr 4 '18 at 21:37
• A point of clarification: Are the bad cases those in which exactly $5$ 1s appear in the first $9$ bits and exactly $27$ 1s appear in the first $49$ bits or those in which exactly $5$ 1s appear in the first $9$ bits or exactly $27$ 1s appear in the first $49$ bits? – N. F. Taussig Apr 4 '18 at 21:59
• it would be considered as an inclusive or, one or the other or both – OneNoteMan Apr 4 '18 at 22:01

Your instinct is good. However, you have not counted the bad cases correctly.

As you observed, there are $2^{70}$ possible bit strings. From these, we must subtract those bit strings in which the first $9$ bits contain exactly $5$ 1s or those in which the first $49$ bits contain exactly $27$ ones.

Bit strings of length $70$ in which the first $9$ bits contain exactly $5$ ones: There are $\binom{9}{5}$ ways to select which $5$ of the first $9$ bits are filled with 1s. There are $2^{61}$ ways to fill the remaining $61$ bits. Hence, there are $$\binom{9}{5}2^{61}$$ such bit strings.

Bit strings of length $70$ in which the first $49$ bits contain exactly $27$ ones: There are $\binom{49}{27}$ ways to select which $27$ of the first $49$ bits are filled with 1s. There are $2^{21}$ ways to fill the remaining $21$ bits. Hence, there are $$\binom{49}{27}2^{21}$$ such bit strings.

Notice that if we subtract these numbers from the total, we will have subtracted those cases in which exactly $5$ of the first $9$ bits and exactly $27$ of the first $49$ bits are 1s twice. We only want to subtract such cases once, so we need to add them back.

Bit strings of length $70$ in which exactly $5$ of the first $9$ bits and exactly $27$ of the first $49$ bits are 1s: There are $\binom{9}{5}$ ways to select which $5$ of the first $9$ bits are filled with 1s. If there are also exactly $27$ 1s in the first $49$ bits, then $27 - 5 = 22$ of the next $49 - 9 = 40$ must be filled with 1s. The remaining $21$ bits can be filled in $2^{21}$ ways. Hence, there are $$\binom{9}{5}\binom{40}{22}2^{21}$$ such cases.

Hence, by the Inclusion-Exclusion Principle, the number of admissible bit strings is $$2^{70} - \binom{9}{5}2^{61} - \binom{49}{27}2^{21} + \binom{9}{5}\binom{40}{22}2^{21}$$