# Generating function for a special binary string

Let $$S$$ be the set of binary strings consisting of a (nonempty) block of $$0$$s followed by a (nonempty) block of $$1$$s, such that if the block of $$0$$s has odd length, then the block of $$1$$s has even length. What is the generating function for $$S?$$

This is what I've tried. I proved that we can generate all strings in S by the following expression $$S = \{0\}\{0\}^*\{1\}\{1\}^*\setminus\{0\}\{00\}^*\{1\}\{11\}^*.$$ But I don't know how to write generating function for the difference of two sets. Any help appricited!

• The generating function for the difference is the difference of the two generating functions. Feb 13, 2019 at 7:39

The generating function for the first set is

$$(x)({1\over 1-x})(x)({1\over 1-x}) = {x^2\over (1-x)^2}$$

The generating function for the second set is

$$(x)({1\over 1-x^2})(x)({1\over 1-x^2})={x^2\over (1-x^2)^2}$$

Since the generating function's coefficient represent the number of element of that length in the set, the difference of the coefficients is basically the number of elements in the difference of the two sets.

Therefore the generating function is

$${x^2\over (1-x)^2} - {x^2\over (1-x^2)^2}={2x^3+x^4\over (1-x^2)^2}$$