Share
Explore BrainMass

Generating function for strings of 1's and 0's

Find the generating function with respect to length for the set of {0,1}- strings having the property that each block of 1's contains an even number of 1's and each block of 0's contains an of number of 0's.

Attachments

Solution Preview

Let's denote the generating function of a single blocks of 1's by f(x) and the generating function of a single blocks of 0's by
g(x). We'll allow a block of 1's to be of zero length. There is only one block of length 2r of 1's, so the generating function a blocks of 1's is:

f(x) = sum from r = 0 to infinity of x^(2r) = 1/(1-x^2)

Note that the coefficient of x^n gives the number of blocks of length n. Similarly there only being one block of length 2r+1, means that the generating function of blocks of 0's is:

g(x) = sum from r = 0 to infinity of x^(2r+1) = x/(1-x^2)

Then, to find the generating function of strings, we use the fact that we have allowed blocks of 1's to be of zero length. This means that we can always take the first block of string to be block of 1's. If the string starts with a 0, then that block of 1's is taken to be of length zero. Likewise, for a finite number of blocks, the last block ...

Solution Summary

We show how using simple algebraic means, one can obtain the generating function for strings of 1's and 0's such that all blocks of 1's are of even length and all blocks of 0's are of odd length.

$2.19