Thread: Generating Functions (I don't get them! at all!)

1. Generating Functions (I don't get them! at all!)

I'm working on a take-home exam, which sounds bad but I don't want help on specific problems... I just don't understand generating functions, ah, shall we say, at all, in any way.

I'm good when we go, e.g.:
1, 2, 4, 8, 16, ... --> 1 + 2z + 4z^2 + 8z^3 + ... --> 1/(1-2z)

Pretty much anything more complex than that completely stumps me. In my notes, I have a left-justified sort of Pascal's triangle, which indicates that the first column (1, 1, 1, ...) has the generating function 1/(1-z), the second column (0, 1, 2, 3, ...) --> 1/(1-z)^2, etc; and that the first row (1, 0, 0, ...) --> 1, the second row (1, 1, 0, 0, ...) --> 1+z, the third row (1, 2, 1, 0, 0, ...) --> (1+z)^2. I do not understand where this comes from, or how to use it in more than the most basic of applications.

I also have a couple of problems that want me to "fill a bag with n fruits subject to the following constraints", where the constraints are like "even number of apples" and "at most 4 oranges". This specific problem is (inexplicably) an example from the book, but while I can copy down the answer I don't understand it at all.

The book says that we want to basically multiply together the generating functions of each condition, which makes sense, but right away I'm confused.
• I thought that g(z) for the even number of apples would be 2/(1-z)^2, because even numbers are 0, 2, 4, 6, ... (well duh) and that's 2(0, 1, 2, 3, ...), so we'd take 2 times 1/(1-z)^2.
• The book says we want 1/(1-x^2), because that's 1 + x + x^2 + x^4 + ...; I don't understand why that's what we're looking for, but this way it follows that "at most one pear" becomes (1+x).
• I'm still iffy on how we got from "at most 4 bananas" and (1 + x + x^2 + x^3 + x^4) to (1-x^5)/(1-x).

I think I'm just missing some fundamental thing here and if I could get that one link then the rest would fall into place. If you would be willing to explain the very basics of generating functions like I'm a baby, I would really appreciate it! I am planning on going to office hours, but as I'm sure some of you understand, I'm frustrated NOW.

2. Re: Generating Functions (I don't get them! at all!)

Originally Posted by rightyourself
1, 2, 4, 8, 16, ... --> 1 + 2z + 4z^2 + 8z^3 + ... --> 1/(1-2z)

Pretty much anything more complex than that completely stumps me. In my notes, I have a left-justified sort of Pascal's triangle, which indicates that the first column (1, 1, 1, ...) has the generating function 1/(1-z)
This is because $1+z+z^2+\dots=1/(1-z)$ (the sum of a geometric progression).

Originally Posted by rightyourself
the second column (0, 1, 2, 3, ...) --> 1/(1-z)^2
This is a little trickier.

\begin{align*}z+2z^2+3z^3+\dots&= z(1+2z+3z^2+\dots)\\&= z\frac{d}{dz}(z+z^2+z^3+\dots)\\&= z\frac{d}{dz}\left(\frac{1}{1-z}-1\right)\\&=\frac{z}{(1-z)^2}\end{align*}

Originally Posted by rightyourself
and that the first row (1, 0, 0, ...) --> 1, the second row (1, 1, 0, 0, ...) --> 1+z, the third row (1, 2, 1, 0, 0, ...) --> (1+z)^2.
Surely if you understand 1, 2, 4, 8, 16, ... --> 1 + 2z + 4z^2 + 8z^3 + ... --> 1/(1-2z), you should understand this. Note that (1 + z)^2=1 + 2z + z^2.

Originally Posted by rightyourself
I also have a couple of problems that want me to "fill a bag with n fruits subject to the following constraints", where the constraints are like "even number of apples" and "at most 4 oranges".
The idea to use generating functions for such problems comes from how coefficients are calculated when two possibly infinite sums are multiplied. In $(z^{a_1}+z^{a_2}+\dots)(z^{b_1}+z^{b_2}+\dots)$, every term from the first sum is multiplied by every term of the second sum. The powers of z of the two terms are added. This corresponds to combining $a_1$ or $a_2$ or ... objects of the first kind and $b_1$ or $b_2$ or ... objects of the second kind in every possible way. In the product, what is the coefficient of some $z^n$? Every way to select a $z^{a_i}$ from the first sum and $z^{b_j}$ from the second sum so that $a_i+b_j=n$ contributes 1 to that coefficient. Therefore, the coefficient of $z^n$ in the product is the number of ways to select n objects of the two kinds.

Originally Posted by rightyourself
• I thought that g(z) for the even number of apples would be 2/(1-z)^2, because even numbers are 0, 2, 4, 6, ... (well duh) and that's 2(0, 1, 2, 3, ...), so we'd take 2 times 1/(1-z)^2.
• The book says we want 1/(1-x^2), because that's 1 + x + x^2 + x^4 + ...
That's 1 + x^2 + x^4 + ... The powers are even natural numbers. The text above explains why it is the powers that matter.

Originally Posted by rightyourself
I'm still iffy on how we got from "at most 4 bananas" and (1 + x + x^2 + x^3 + x^4) to (1-x^5)/(1-x).
Again, this is the sum of a geometric progression. This equality can also be verified directly by multiplying (1 + x + x^2 + x^3 + x^4) and (1 - x).