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

• Mar 25th 2013, 09:18 PM
rightyourself
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. :)
• Mar 26th 2013, 01:14 PM
emakarov
Re: Generating Functions (I don't get them! at all!)
Quote:

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 $\displaystyle 1+z+z^2+\dots=1/(1-z)$ (the sum of a geometric progression).

Quote:

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

This is a little trickier.

\displaystyle \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*}

Quote:

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.

Quote:

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 $\displaystyle (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 $\displaystyle a_1$ or $\displaystyle a_2$ or ... objects of the first kind and $\displaystyle b_1$ or $\displaystyle b_2$ or ... objects of the second kind in every possible way. In the product, what is the coefficient of some $\displaystyle z^n$? Every way to select a $\displaystyle z^{a_i}$ from the first sum and $\displaystyle z^{b_j}$ from the second sum so that $\displaystyle a_i+b_j=n$ contributes 1 to that coefficient. Therefore, the coefficient of $\displaystyle z^n$ in the product is the number of ways to select n objects of the two kinds.

Quote:

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.

Quote:

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).