# How many bit strings of length 20 have exactly five $1$’s and do not contain $11111$ as a substring? [closed]

Recall that a bit string is a string composed of characters $$0$$ and $$1$$.

Can someone explain how the answer is:

$${20\choose5} - 16$$?

## closed as off-topic by Martin R, vonbrand, Mars Plastic, Javi, The CountAug 20 at 0:10

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Martin R, vonbrand, Mars Plastic, The Count
If this question can be reworded to fit the rules in the help center, please edit the question.

• What do you know? What have you tried? Where did you get stuck? Also: titles should be a description of the question, not simply the first sentence of the background. – Mees de Vries Aug 19 at 14:34
• 5 positions out of 20 for the ones; but not the sequences that are $k$ zeroes ($0 \le k \le 15$), five ones, and $10 - 5 - k$ zeroes. There are $16$ such sequences. – vonbrand Aug 19 at 14:58

For a bit string length 20 with exactly 5 1's, it must also have exactly 15 0's. In other words, we need to arrange 5 1's and 15 0's in a line. Thus, the number of these bit strings is

$$\frac{20!}{5!\cdot15!} = \binom{20}{5}$$

Sixteen of these strings contain the substring 11111 (1111100...00, 01111100...0..etc.) - we can place the start of the substring 11111 in 16 different places because it can start anywhere from the 1st to the 16th digit in the string.

Thus, the total number of such strings is $$\binom{20}{5}-16$$

• How did you know 16 of the strings contain the substring 11111? – Stuy Aug 19 at 14:37
• @Stuy I believe I explained it in my answer, feel free to ask further questions – BaroqueFreak Aug 19 at 14:39
• @Stuy They are uniquely determined by the startung position of the 11111 block – Hagen von Eitzen Aug 19 at 14:40
• I'm sorry, I still don't understand. I thought it was 16 because 2^5 is 16. – Stuy Aug 20 at 0:23
• $2^{4}=16$. Also we are not using powers of 2 because we have already chosen how many 1s and 0's there are (5 and 15). Have another look at the part that says 'Sixteen of these strings contain the substring 11111' for examples of possible strings – BaroqueFreak Aug 20 at 3:14