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.