Counting certain binary strings

Question

Let b be a binary string of length r with no adjacent 0s or 1s, e.g. b can be 01010 or 1010 but not 1001 or 0010. For n > r, perform the following operation on a binary string c of length n: if there is a substring consisting of adjacent 0s or 1s, then "callapse" such adjacent 0s or 1s into a single digit 0 or 1, e.g. if c is 01100111010011, then it is turned into 01010101. Simply put, every 00 callapses into 0 and so does every 11. How many binary string of length n will result in binary strings of lenght r without adjacent 0s and 1s?

Answer 1

You can uniquely encode a binary string of length n by its first digit and then n-1 choices of whether the ith position is equal to the (i+1)st position or not. For example, 10001 is encoded as [1,(change-same-same-change)]. The string 00001 is encoded as [0,(same-same-same-change)]. This encoding is useful here. A binary string has r streaks precisely when it has r-1 changes out of n-1. So, there are 2 * (n-1 choose r-1) binary strings with r streaks, where (n-1 choose r-1) is a binomial coefficient, because we can choose the first digit to be either 0 or 1 and then any set of r-1 changes out of the n-1 possible locations will produce r streaks. For example, if n=4, there are 2 strings with 1 streak, 6 strings with 2 streaks, 6 strings with 3 streaks, and 2 strings with 4 streaks. The pattern 2-6-6-2 is twice a row of Pascal's triangle.

Answer 2

We shall call a binary string b "admissible" if it has no adjacent 0s or 1s, as compared to a general binary string. There are only two admissible binary strings of length r: one starts with 0 and the other starts with 1. Since the two will result in the same number of general binary strings of length n that callapse into admissible ones, we need to count only one case, say the one starts with 0. For admissible binary strings of length 2, 3, and 4, we have 01, 010, and 0101.

A general binary string that can callapse into an admissible one if and only if it consists of r segmens of adjacent 0s and 1s, of which the 0-segments and the 1-segments distribute alternatively, e.g. 0011100 callapses into 010. Suppose that it has segments of length n₁, n₂, n₃, ..., n_r. Then we have n = n₁ + n₂ + ... + n_r, with each n_i ≥ 1. Each of such general binary string of length n corresponds uniquely to a partition of the integer n into r parts. The number of such partitions is

_n-1C_r-1 = (n −1)!/(r −1)!(n − r)! = (n −1)(n − 2)...(n − r +1)/(r −1)!,

which is the number of combinations of choosing r −1 objects out of n −1 objects.

I could go on to explain why this is the number of such partitions. But it would make the answer too long. I will post this as a separate question and provide an answer.