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

  • $\begingroup$ 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?$ $\endgroup$ – saulspatz Sep 13 '18 at 16:02
  • $\begingroup$ 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. $\endgroup$ – 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}$.

  • $\begingroup$ 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? $\endgroup$ – Bone Sep 13 '18 at 16:10
  • $\begingroup$ @Bone I gave you a brief response which, in my opinion, is sufficiently formal. $\endgroup$ – Robert Z Sep 13 '18 at 16:15

automaton with counters

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.


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.