4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ will you clarify your question more.. $\endgroup$ – Ri-Li Oct 6 '14 at 14:20
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – robjohn Oct 6 '14 at 15:06
  • $\begingroup$ 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. $\endgroup$ – OrdinaryHuman Oct 6 '14 at 21:04
2
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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

$\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.