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