2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – N. F. Taussig Apr 4 '18 at 21:29
  • $\begingroup$ 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 $\endgroup$ – OneNoteMan Apr 4 '18 at 21:31
  • $\begingroup$ Showing how you arrived at that number would make it easier for readers of this question to determine if you made an error. $\endgroup$ – N. F. Taussig Apr 4 '18 at 21:37
  • $\begingroup$ 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? $\endgroup$ – N. F. Taussig Apr 4 '18 at 21:59
  • $\begingroup$ it would be considered as an inclusive or, one or the other or both $\endgroup$ – OneNoteMan Apr 4 '18 at 22:01
3
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.