Results 1 to 15 of 15
Like Tree1Thanks
  • 1 Post By chiro

Math Help - Generating Function help

  1. #1
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Generating Function help

    Hey there I need some help on what to do next for this problem.

    In how many ways can you make change for a dollar using
    pennies, nickels, dimes, quarters, and half-dollars?

    so far I got
    (1+x+x^2+x^3+...+x^100) <-- pennies
    (1+x^5+x^10+x^15+....+x^100) <- nickels
    (1+x^10+x^20+x^30+...+x^100) <- dimes
    (1+x^25+x^50+x^75+x^100) <- quarters
    (1+x^50+x^75+x^100) <- half dollars

    and the generating function is
    1/(1-x)(1-x^5)(1-x^10)(1-x^25)(1-x^50)

    what do I do from here to get the answer I need?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Generating Function help

    Hey gfbrd.

    What does this function refer to? Are you trying to solve a recurrence relation? Is this function meant to be equal to 0 where you need to find the roots?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Generating Function help

    sorry but i dont think i did anything wrong here, all i want to know is how do i get the coefficient for x^100 from the generating function
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Generating Function help

    Ohh I see what you are trying to do.

    Try expanding out (1-x^5)(1-x^10)(1-x^25)(1-x^50) and then look at the generating function for (1-x) when you get these terms multiplied by the expansion to give x^100 (there should be 16 terms to look for) then collect the coeffecients together.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Generating Function help

    what do you mean by expanding?
    do I multiply this out?

    (1+x+x^2+x^3+...+x^100)(1+x^5+x^10+x^15+....+x^100 )(1+x^10+x^20+x^30+...+x^100)(1+x^25+x^50+x^75+x^1 00)(1+x^50+x^75+x^100)
    if so how do I multiply this out, it would take forever to do it by hand
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Generating Function help

    No don't do that: multiply out (1-x^5)(1-x^10)(1-x^25)(1-x^50) and then look for when x^n * all the individual terms in the expanding polynomial give an x^100 term and collect those terms together.

    Your generating function will be in terms of a_n*x^n so all you need to check are the terms where a_n*x^n * blah*x^k give a_n*blah*x^(n+k) where n+k = 100.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Generating Function help

    ok i expanded it and i got

    1-x^5-x^10+x^15-x^25+x^30+x^35+x^40-x^50+x^55+x^60-x^65+x^75-x^80-x^85+x^90

    i dont really see any x^100 terms here
    im not sure what do i really do next sorry im a bit slow on this
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Generating Function help

    Now you have to consider (1-x^5-x^10+x^15-x^25+x^30+x^35+x^40-x^50+x^55+x^60-x^65+x^75-x^80-x^85+x^90)*a_n*x^n where all these terms have a x^100 term in them.

    For example 1*a_n*x^n has n = 100, while -x^5*a_n*x^n has n = 95 and so on.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Generating Function help

    going from left to right i get n=100,n=95,n=90,n=85,n=75,n=70,n=65,n=60,n=50,n=45 ,n=40,n=35,n=25,n=20,n=15,n=10
    but what do i do with these terms though? sorry i need to take this slowly to understand
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Generating Function help

    Now you need to consider what the a_n's are for those terms and then add them up.

    Remember that these terms are the only time the whole series if were expanding out as a generating function gave a b_n*x^n where n = 100 where this is for the full expanding series.

    Since you have all the possible terms where the n = 100 for the b_n, then the b_n for the expanding series will be the same of all the a_n's in your 1/(1-x) that correspond to those terms which means if you find all the a_n's and multiply them by the coffecients in the polynomial you just expanded then you will get the b_100 term which is the coffecient of the generating series for n = 100.

    A few examples might clear things up:

    1*a_100 for the first term
    -a_5 for the second term
    -a_10 for the third term

    and so on

    and then the final coffecient will be the sum of all these terms since all these terms have the common x^100 term if you looked at the completely expanding generator function with x^100*b_100 (you are trying to find b_100).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Generating Function help

    sorry i dont know if i understand this or not
    1a_100-a_95-a_90+a_85-a_75+a_70+a_65+a_60-a_50+a_45+a_40-a_35+a_25-a_20-a_15+a_10
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Generating Function help

    That's the right technique and that should give you the coeffecient for the 100th term if the polynomial and the calculation is correct.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Generating Function help

    so its a_120? if so then i think there might be a mistake, because i believe the answer should be 292 istead
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Generating Function help

    No it's not that: you don't add up the indexes but the actual values.

    a_100 is the value of the generating series of 1/(1-x) at the 100th position, a_75 is at the 75th position (i.e. n = 100. n = 75) and so on. You need to add these terms up, not the indices themselves.
    Thanks from gfbrd
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Generating Function help

    Oh alright thanks for all your help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. generating function of Pn(x)
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: April 16th 2012, 12:04 AM
  2. Finding probability function of moment generating function
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: July 4th 2011, 04:03 PM
  3. generating function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 25th 2011, 04:54 PM
  4. generating function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 10th 2009, 10:21 PM
  5. Moment generating function and distribution function?
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: January 25th 2009, 02:02 PM

Search Tags


/mathhelpforum @mathhelpforum