I'm trying to learn generating functions and integer partitions and having particularly difficult time with this question:

"This question is about binary strings where each block of 0s is followed by a block of the same number of 1s." 1. Consider strings of this form which begin with 0 and have only one block of 0s. a) Write out all such strings of size at most 6. b) What is the generating function for these strings?

a) 01, 0011, 000111

b) Issue is that I have no idea how to represent this sequence as a generating function. Can anyone show me how to convert such sequences into generating functions?

Thank you.


2 Answers 2


Let $f(n)$ be the number of such strings of size $n$. Then the (ordinary) generating function associated with this sequence is $$F(x):=\sum\limits_{n \geq 0} f(n) x^n. $$ Based on your description, $f(n) = 1$ if $n$ is even and $f(n) = 0$ if $n$ is odd. The generating function is $$F(x) = \sum\limits_{n \geq 0}f(n) x^n = 1 + x^2 + x^4 + \cdots = \frac{1}{1 - x^2}.$$

Additionally, if we want the generating function for the number of such strings of size at most $n$, then we have $$\sum\limits_{n \geq 0 } \left(\sum\limits_{k = 0}^n f(k)\right) x^n = \frac{F(x)}{1 - x} = \frac{1}{(1 - x^2)(1 - x)}.$$


Think about how you'd come up with a decomposition for the set of binary strings you want. Intuitively, what you want is some number of zeros, the same number of ones and stick them together. And then you want to repeat that an arbitrary number of times. For convenience, lets define the set:

$$ A = 01 \cup 0011 \cup 000111 \cup ....$$

With respect to the weight function being the length of the string, the generating function for $A$ is:

$$ A(x) = x^2 + x^4 + x^6 + x^8 + ... \ = \frac {x^2} {1-x^2}$$

So this covers one repetition of the pattern you want. You want to allow this to happen an arbitrary number of times. So the set of all strings you're really interested in is this:

$$ S = \epsilon \cup A \cup A^2 \cup A^3 \cup ... $$

where $\epsilon$ is the empty string

Then the generating function for S is simply, (using the product and sum rules):

$$ S(x) = 1 + A(x) + A(x)^2 + A(x)^3 + ... $$ $$ = \frac {1} {1-A(x)}$$ $$ = \frac {1} {1 - \frac {x^2} {1-x^2}} $$

Which simplifies to:

$$ \frac {1 - x^2} {1 - 2x^2} $$

In general, the hardest and most important part is finding a clean decomposition of these strings -- an enumeration of the set you're interesting in counting properties of. It takes some practice, but I hope this outlines the general principle.


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.