Results 1 to 2 of 2

Math Help - Generating Functions (I don't get them! at all!)

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    VA
    Posts
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

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

    Quote Originally Posted by rightyourself View Post
    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).

    Quote Originally Posted by rightyourself View Post
    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*}

    Quote Originally Posted by rightyourself View Post
    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 View Post
    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.

    Quote Originally Posted by rightyourself View Post
    • 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 View Post
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating Functions help
    Posted in the Advanced Math Topics Forum
    Replies: 6
    Last Post: October 26th 2012, 10:17 PM
  2. Generating functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 8th 2011, 04:30 AM
  3. generating functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 1st 2010, 01:15 AM
  4. Generating functions
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 8th 2009, 10:50 AM
  5. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2008, 04:43 PM

Search Tags


/mathhelpforum @mathhelpforum