# Number of bit strings with exactly eight zeros and ten ones, where every zero is followed by one

Q: How many bit strings contain exactly eight $0$s and ten $1$s if every $0$ is either immediately followed by a $1$, or this $0$ is the last symbol in the string?

Instructor said the answer was $9^2 \times 8^3 \times7^4 \times 6^5...$

But I don't understand why.

If the string is $0101010101010101$ that leaves two $1$s to place. Aren't there $10$ places to put the two $1$s? After each $1$ and at the beginning or end of the string?

• will you clarify your question more.. – Ri-Li Oct 6 '14 at 14:20

Case 0: The string ends in a 0.

The problem becomes equivalent to counting distinct arrangements of 7 instances of '01' and 3 instances of '1', followed by a '0' at the end. There are $\binom{10}{3} = 120$ arrangements in case 0.

Case 1: The string ends in a 1

The problem is equivalent to counting distinct arrangements of 8 instances of '01' and 2 instances of '1'. There are $\binom{10}{2} = 45$ distinct arrangements here.

Total = $\binom{10}{3} + \binom{10}{2} = 165$.

• I first read only the title, and got the case which ends in a $1$. After reading the question, I had to add the case where the string ends in $0$. (+1) – robjohn Oct 6 '14 at 15:06
• This makes sense. Two scenarios, both of which have 10 possible slots for either two or three 1s. You guys make this look so easy. Thanks. – OrdinaryHuman Oct 6 '14 at 21:04

Indeed, you should consider $010101010101010$, and see that you can put the $3$ remaining $1$s in any of the $9$ places (before the first $0$, after the last, or in between two $0$s).

You have three possible cases :

1. All places are different : $\dfrac{9*8*7}{6}=3*4*7=84$ possibilities.
2. Two are the same: $9*8=72$ possibilities.
3. The three extra $1$s are in the same place: $9$ possibilities.

In total, this gives $165$ possibilities (a lot less than your number).

At first I had just read the title and missed that a trailing $0$ was allowed. So my answer was as follows:

Consider all sequences of $8$ $A$s and $2$ $B$s. Each one uniquely represents each of the possible arrangements of the $0$s and $1$s by mapping $01\leftrightarrow A$ and $\cdot1\leftrightarrow B$ where the $\cdot$ represents the beginning of the string or a $1$. There are $\binom{10}{2}=45$ ways to arrange $8$ $A$s and $2$ $B$s.

To count the strings with a trailing $0$ would be the same as having $7$ $0$s and $10$ $1$s with the same mapping as above, we would need $7$ $A$s and $3$ $B$s. There are $\binom{10}{3}=120$ ways to arrange $7$ $A$s and $3$ $B$s (followed by a $0$).

Since these cases are disjoint (the first case always ends in $1$, the second ends in $0$), we can add these to get $165=\binom{11}{3}$.

Note that the rule for Pascal's Triangle gives $\binom{10}{2}+\binom{10}{3}=\binom{11}{3}$.