How many binary strings of length $n$ contain $k$ flips?

Question

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

Answer 1

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