If I have say the string $1010010001010101$, which has a length of $16$ and there are $12$ flips. My thoughts are to just count the number of ways I can stick a $10$ in the there so ${n-1 \choose 0.5k}$ but I know that doesn't account for the times the first and last bits aren't the same and $k$ is odd, or what the bits in between the $10$ are, since they could be a run of $1$s or $0$s.

Been out of school for a couple of years and it's kind of depressing how much I've forgotten, so any help would be greatly appreciated, thanks


If you have $n$ digits, then there are $n-1$ spaces between the digits, of which $k$ are "flips" and the others are not. We have $\binom{n-1}{k}$ ways to position the flips. Additionally, for each of these choices of flip positions, the leftmost digit could be a zero or a one, so we multiply the number of choices by 2 to account for this difference: $$ 2 \binom{n-1}{k} $$

  • $\begingroup$ "spaces between the digits" ahhhhh, now I remember how I'm supposed to think about it, thanks! $\endgroup$ – XRBtoTheMOON Sep 22 '19 at 18:56

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.