1
$\begingroup$

Question

How many bit strings contain exactly eight $0\,s$ and ten $1\,s$ if every $0$ must be immediately followed by a $1$ I know a question is already posted here, but i am getting doubt in my approach.

My approach/solution

My arrangement diagram goes like-:

$${\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}$$

I have to fill the gap$(-)$ by remaining $1^{s}$ i.e $2 \,\,1^{s}$

so total number of string possible= $$\binom{18}{2}$$

but the answer is $$\binom{10}{2}$$

where am i wrong ?

$\endgroup$
  • $\begingroup$ Consider the string 101010101010101011. It doesn't matter whether the 1's at the ends went in the red space or the black one, but your method counts them each twice. $\endgroup$ – rogerl Oct 14 '17 at 16:19
2
$\begingroup$

We can also derive the correct result $$\binom{10}{2}$$ based upon your approach. We do so by assuring that each admissible selection is counted precisely once.

The configuration $${\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}01{\color{Red} --}$$ has $9$ positions starting with the left-most ${\color{Red} --}$ up to the right-most ${\color{Red} --}$. We can place at each of these $9$ positions one or two $1$s at most a total of two $1$s.

We observe admissible selections belong precisely to one of two different types:

Either the two $1$s are placed at different positions or the two $1$s are placed at the same position.

  • There are $\binom{9}{2}$ ways to place two $1$s at different positions.

  • There are $\binom{9}{1}$ ways to place two $1$s at the same position.

We conclude there is total of \begin{align*} \binom{9}{2}+\binom{9}{1}\color{blue}{=\binom{10}{2}} \end{align*} admissible selections.

$\endgroup$
  • $\begingroup$ Thanks a lot sir :) $\endgroup$ – laura Oct 15 '17 at 3:22
  • $\begingroup$ @Laura: You're welcome! :-) $\endgroup$ – Markus Scheuer Oct 15 '17 at 4:51
2
$\begingroup$

If you put just one $1$ in a particular gap between $01$s you don't care whether it occupies the left blank or right blank. All the cases were the $1$s went in different gaps are counted four times.

$\endgroup$
  • $\begingroup$ sir , is this not permittable $011101010101010101$? $\endgroup$ – laura Oct 14 '17 at 14:54
  • $\begingroup$ Thanks a lot sir :) $\endgroup$ – laura Oct 15 '17 at 3:22
1
$\begingroup$

Your method does not work, because using your coloring: if the first remaining $1$ goes in a black position, then the second cannot go in a black position. So, you cannot pick any two of the $18$ positions, as that would include two black ones, or two red ones.

Put differently: If you were to put the first $1$ in the first black position, and the second in the second black position, then you get the same string as when you put the first $1$ in the first black position and the second in the second red position. So, you are overcounting.

In fact, you are also counting putting the first in the first black position and the second in the second red position as different frim putting the first in the first red position, and the second in the second black position, but these result in the same string as well, so you are overcounting in that way as well.

Instead, think about it this way: you basically have $10$ 'units' that you are trying to arrange: $8$ units of $01$, and two units of $1$. So the problem has become isomorph to something like: how many strings are there consisting of $8$ $A$'s and $2$ $B$'s?

$\endgroup$
  • $\begingroup$ thanks for the hint , but my doubt is why can't we fill $0111$ i.e one of my final string as $011101010101010101$? $\endgroup$ – laura Oct 14 '17 at 14:51
  • $\begingroup$ @laura: you can and that is counted. To get $011101010101010101$ you put the solo $1$s in the second and third locations of $10$ $\endgroup$ – Ross Millikan Oct 14 '17 at 14:53
  • $\begingroup$ sorry sir , but i am not getting you $\endgroup$ – laura Oct 14 '17 at 14:57
  • $\begingroup$ @laura Yes, you can fill it that way, and notice that in that case one of the $1$ ends up in a black position, and other in a red position, so that is indeed ok. What is not ok, is to put both in a black position, or both in a red pposition. That is why your method is overcounting. I just added this explanation to my Answer. $\endgroup$ – Bram28 Oct 14 '17 at 15:07
  • $\begingroup$ @Bram28 , i got why i am wrong .but can you help me to arrange $011101010101010101$ $\endgroup$ – laura Oct 14 '17 at 15:15

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.