How many binary strings of length $n$ exist with $k$ $10$s or $01$s

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

• Recursion often works well for problems like this. If you know the answer for strings of length $n-1$ (and all $k$) can you answer the question for strings of length $n?$ – saulspatz Sep 13 '18 at 16:02
• While I can see the logic I'm not sure how to actually go about proving it through anything other than inspection. This is a new topic for me and I don't have any experience writing formal proofs for this. They also mention that the answer should be in forms of binomial coefficients. – Bone Sep 13 '18 at 16:07

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

• Sound logic. Just to confirm, the question uses the phrase 'Justify your answer'. Is this sufficient justification or is there a more formal way of proving this somehow? – Bone Sep 13 '18 at 16:10
• @Bone I gave you a brief response which, in my opinion, is sufficiently formal. – Robert Z Sep 13 '18 at 16:15 Let $$A$$ be binary strings that ends with $$0$$ and $$B$$ that ends with $$1$$.

$$x$$ is a counter variable for the length of an accepted word, while $$t$$ will count the transitions. Then:

$$A = xA + txB + x$$

$$B = xB + txA + x$$ and

$$A+B = {2x \over 1-x-tx} = 2x + 2x^2(1+t) + 2x^3(1+t)^2 +...$$

The required number for length $$n$$ and $$k$$ changes is the coefficient of $$x^nt^k$$.

For example, if $$n = 4$$ and $$k = 2$$ we have six good words: 0100, 0110, 0010, 1011, 1001, and 1101.