Determine an unambiguous expression for the following sets of binary strings and then find their generating series as a rational function: a). Binary strings where there are never three or more 1's in a row. b). Non-empty binary strings in which the first and last entries are the same. You do not need to prove that your expressions are unambiguous.

Question

anonymous · Answer

To help wrap my head around this, I'm assuming a binary string (of what, $n$ terms?) that would fall into the first category is something like (assuming $n=10$)
$$1,1,0,0,0,0,1,1,0,1$$
and the second,
$$1,0,0,1,0,1,0,1,1,1$$
The first step would be to count how many of such strings you can build. The first one is a bit tricky, but the second one isn't too bad, so I'll try that one first.

Of $n$ terms in the string, the first and last must be the same, so there is only one option for the ends (1 or 0), leaving $n-2$ terms remaining in the string. For any of these $n-2$ terms, you have two options (1 and 0). This means there are $\large2^{n-2}$ total strings that satisfy the equal-end condition.

My next question would be, where do generating functions/series come into play here?