Got a combinatorics question and honestly no idea how to get by it. Would love some reference to material related to the topic as well as my course notes do a great job of not having any examples.
A change in a binary string is an occurrence of two consecutive terms in the string that are different (that is, one is a $0$ and the other is a $1$). For example, in the binary string $1001$, there are two changes: the $10$ at the beginning and the $01$ at the end. In $1010$, there's $3$ changes because: $10$ at the beginning, $01$ in the middle, $10$ at the end.
How many binary strings of length $n$ have exactly $k$ changes? Where a change is the existence of $10$ or $01$s
Best Answer
Yes, your approach is correct. Along the string, the digits change $k$ times. Such changes can be placed between the $i$th digit and $(i+1)th$ digit for $i=1,\dots, n-1$. This can be done in $\binom{n-1}{k}$ ways. Finally note that each string starts with a $0$ or $1$ so the total number of such strings is $2\binom{n-1}{k}$.