The Question

How many bit strings contain exactly eight 0s and 10 1s if every 0 must be immediately followed by a 1?

Note: There is a similar but also very different question on this site. Please do not report this as a duplicate because it is not!

My Attempt

I thought could we not also have $8$ 01 strings and $2$ 1 bits. This ensures that 0 is directly followed by a 1. I then have 9 spaces (since the 01 will occupy two of our 18 spaces) to distribute these into, which can be done in 9 ways, then I put the 1s in the remaining spaces, giving us 9 bit strings.

My Problem

My answer was not correct. My textbook gives the answer 45. I'm wondering what was wrong with my approach, and how I would approach this question correctly.

  • 3
    $\begingroup$ You have ten spaces, eight filled by "01" and two filled by "1". $\endgroup$ – vadim123 Nov 6 '14 at 23:44
  • $\begingroup$ Which means I have C(10,8) ways to distribute the "01" and 1 way to slot the two "1" into the remaining 2 spaces. By rule of product I have C(10,8)*1 = 45 spaces? $\endgroup$ – Dunka Nov 6 '14 at 23:48

Per vadim123's comment (and your own thoughts), you have a string of length 10 and you have two letters to use: eight "01"s and two "1"s. In other words, there are 10 locations in the string and you're choosing 2 of them to be special, so the answer is $\binom{10}{2}$.

I don't really follow your attempt-- the problem is as if you have 10 spaces, so I don't know why you say 9.

  • $\begingroup$ My thinking was definitely off. We start off with 18 spaces to put a eight "0"s and ten (1s). I forgot to adjust how many spaces we had when I turned our bits into eight "01"s and 2 "1"s $\endgroup$ – Dunka Nov 7 '14 at 0:04

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.