How many sequences of bits are there that have the following properties:

  • Their length is either $5$, $7$, or $9$.
  • Their middle bit is a $1$.
  • The number of $0$'s they have is equal to the number of $1$'s they have minus one.

Correct answer: ${4\choose2} + {6\choose3} + {8\choose4} = 96$.

My solution (wrong):

Split the counting into three cases by length.

In the case of length = 5, the middle digit must be $1$ by the first condition, and the remaining four spots must be filled with two $0$'s and two $1$'s by the third condition. There are $4!$ ways to place them.

In the case of length = $7$, following similar reasoning, I deduced there were $6!$ possible strings.

Similarly, for length = $9$, I found $8!$ possible strings.

Thus, my answer was $4! + 6! + 8! = 41,064$, which is incorrect.

What did I do wrong?


You didn't divide through by the amount representing repeats. $4!$ should be $\dfrac{4!}{2!2!}$ because there are $2!$ ways to swap the $0$s without changing a configuration and likewise for the $1$s. Thus, the answer really should be

$$\frac{4!}{2!2!} + \frac{6!}{3!3!} + \frac{8!}{4!4!} = 6 + 20 + 70 = 96.$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy