Results 1 to 8 of 8

Math Help - Generating Functions question

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    26

    Generating Functions question

    Alright I have two problems both of which i THINK need to be done with a generating function.... any tips would really be appreciated


    First question:
    1)Find the number of solutions to the equation
    2x + 3y + 6z = 73
    where x, y, and z are non-negative integers.

    I just took each case individually and got 78 possible solutions, but I was wondering if there was an easier way to do this rather than just finding each solution and counting it.

    Also I am getting stuck on this one too:
    How many ways are there to put 5 identical objects into n bins, where each
    bin can have at most 2 objects?

    2)From what we learned in class, I would guess that the generating function would be:

    G(x)=(1+x+x^2)^n which is equal to [(x^3-1)/(x-1)]^n which is equal to
    (x^3-1)^n*(1/(x-1))^n.

    Then that implies that it equals ((x^3-1)^n)*SUM((a_k)x^k)
    where a_k= C(k+n-1,k)

    Usually I would just plug in 5 for k, and get my answer, but what do I do with the (x^3-1)^n??

    Any help would be great!!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by mathgirlie View Post
    Alright I have two problems both of which i THINK need to be done with a generating function.... any tips would really be appreciated


    First question:
    1)Find the number of solutions to the equation
    2x + 3y + 6z = 73
    where x, y, and z are non-negative integers.

    I just took each case individually and got 78 possible solutions, but I was wondering if there was an easier way to do this rather than just finding each solution and counting it.
    Also I am getting stuck on this one too:
    How many ways are there to put 5 identical objects into n bins, where each
    bin can have at most 2 objects?

    2)From what we learned in class, I would guess that the generating function would be:

    G(x)=(1+x+x^2)^n which is equal to [(x^3-1)/(x-1)]^n which is equal to
    (x^3-1)^n*(1/(x-1))^n.

    Then that implies that it equals ((x^3-1)^n)*SUM((a_k)x^k)
    where a_k= C(k+n-1,k)

    Usually I would just plug in 5 for k, and get my answer, but what do I do with the (x^3-1)^n??

    Any help would be great!!!!
    On 1), did you find the generating function? I think that's the point of the exercise. But in the end, I don't think the generating function will save you much work, in this case. (If someone else sees a shortcut, I hope they will post it.)


    For 2), you have found G correctly. Notice that
    G(x) = (1-x^3)^n \; (1-x)^{-n}
    = \sum_i (-1)^i \binom{n}{i} x^{3i} \cdot \sum_j (-1)^j \binom{-n}{j} x^j
    (I'm assuming you feel comfortable with binomial coefficients like \binom{-n}{j}.)
    To end up with x^5 in this product, you need to consider x^0 \cdot x^5 and x^3 \cdot x^2. Do you see where they come from?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    26
    Alright thanks for the help on the 2nd one, I think I understand it, but I really don't understand where you got the (-1)^i and (-1)^j part. Is that because we are subtracting x?. Also, I'm not too sure about how to set up the generating function for the first part... any tips?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by mathgirlie View Post
    Alright thanks for the help on the 2nd one, I think I understand it, but I really don't understand where you got the (-1)^i and (-1)^j part. Is that because we are subtracting x?. Also, I'm not too sure about how to set up the generating function for the first part... any tips?
    The (-1)^i is there because we are expanding (1- x^3)^n = (1 + (-1 \cdot x)^3)^n.

    For the first part, consider the more general problem of determining the number of solutions of

    2x + 3y + 6z = r
    where x, y, z are non-negative integers.
    Let's say the number of solutions is a_r.
    We want the generating function f(x) = \sum_{r=0}^{\infty} a_r x^r.
    All I can say is that it's easy once you see it-- just think about how you multiply polynomials:

    f(x) = (1 + x^2 + x^4 + x^6 + \dots) \cdot (1 + x^3 + x^6 + x^9 + \dots) \cdot (1 + x^6 + x^{12} + x^{18} + \dots)

    Then you shoud use your knowledge of series to simplify that expression.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    26
    thanks so much for your help, I really appreciate it!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2009
    Posts
    26
    quick question though, one of those coefficients will be negative, so does that mean I ignore the negative sign and add them together or do I subtract the smaller number from the larger number?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    Posts
    95
    hey mathgirlie,

    I think you can greatly simplify things for the first question by considering, given
    <br />
2x+3y+6z=73<br />

    <br />
2x \equiv 1 \bmod{3}<br />
\iff<br />
x \equiv 2 \bmod{3}<br />
\iff<br />
x = 3x'+2<br />

    for some x' and similarily

    <br />
y \equiv 1 \bmod{2}<br />
\iff<br />
  y= 2y'+1<br />

    for some y' so that

    <br />
2x+3y+6z=73 \iff 2(3x'+2) + 3(y'+1) + 6z = 73 \iff x'+y'+z = 11<br />

    for some x',y'

    so a generating function like

    <br />
f(x)=(1+x+x^2+x^3+...)^3<br />

    suffices
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by mathgirlie View Post
    quick question though, one of those coefficients will be negative, so does that mean I ignore the negative sign and add them together or do I subtract the smaller number from the larger number?
    Don't ignore the negative sign! Follow the usual rules for adding signed numbers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about generating functions
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 22nd 2011, 09:26 AM
  2. Replies: 0
    Last Post: April 19th 2011, 06:48 AM
  3. Replies: 0
    Last Post: April 15th 2011, 05:43 AM
  4. Combinatorics question - generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 4th 2009, 05:22 PM
  5. Probability Generating Functions Question
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 15th 2009, 07:39 PM

Search Tags


/mathhelpforum @mathhelpforum