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

Question

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

Answer 1

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

Answer 2

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.