Results 1 to 5 of 5

Math Help - Change combinatorix

  1. #1
    Junior Member
    Joined
    Apr 2006
    Posts
    26

    Change combinatorix

    So i know I need to use combinatorix for this, but I'm not exactly sure how.

    4.3.19 In how many ways can you make change for a dollar, using pennies, nickels, dimes, quarters, and half-dollars? For example, 100 pennies is one way; 20 pennies, 2 nickels, and 7 dimes is another. Order doesn't matter.

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Did you try generating functions?

    Let a_n be the number of non-negative solutions to,
    x_1+5x_2+10x_3+25x_4+50x_5=n.
    Create the generating function,
    f(x) = a_0+a_1x+a_2x^2+....
    Now, realize that,
    g_1(x)g_2(x)g_3(x)g_4(x)g_5(x) = f(x)
    Where,
    g_1(x)=1+x+x^2+...
    g_2(x)=1+x^5+x^{10}+...
    g_3(x)=1+x^{10}+x^{20}+...
    g_4(x)=1+x^{25}+x^{50}+...
    g_5(x)=1+x^{50}+x^{100}+...
    Thus, by geometric series,
    f(x) = \frac{1}{1-x}\cdot \frac{1}{1-x^5}\cdot \frac{1}{1-x^{10}}\cdot \frac{1}{1-x^{25}}\cdot \frac{1}{1-x^{50}}

    Does that work out?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    There is no easy way to do this problem!
    The most efficient way is by generating functions.
    Can you expand the following expression:
    \left( {\sum\limits_{k = 0}^{100} {x^k } } \right)\left( {\sum\limits_{k = 0}^{20} {x^{5k} } } \right)\left( {\sum\limits_{k = 0}^{10} {x^{10k} } } \right)\left( {\sum\limits_{k = 0}^4 {x^{25k} } } \right)\left( {\sum\limits_{k = 0}^2 {x^{50k} } } \right)?

    If you can then the coefficient of x^{100} is the answer to the question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Apr 2006
    Posts
    26
    The highest term I got when multiplying all of that together was (3x^19)/(20(x^20-x^15+x^10-x^5+1)). Did I do something wrong?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2006
    Posts
    26
    I'm still stuck on this one. I don't get an x^100 term when I do the product of the geometric series. What do I do?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: April 12th 2011, 10:51 AM
  2. How do I change . . . .
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: October 31st 2010, 10:43 PM
  3. Replies: 0
    Last Post: November 27th 2008, 04:35 AM
  4. How do I change this?
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 23rd 2008, 07:04 PM
  5. Ice-cream and cookie combinatorix
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: September 20th 2007, 10:28 AM

Search Tags


/mathhelpforum @mathhelpforum