Results 1 to 8 of 8

Math Help - Recursive Relations...

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    56

    Recursive Relations...

    I need help with this question...I have no idea how to start it.

    A country uses as currency coins with values of 1 cent, 2 cents, 5 cents and 10 cents and bills with values of 5 cents, 10 cents, 20 cents and 100 cents. Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters.

    ie a(17) = 9494
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    I need help with this question...I have no idea how to start it.

    A country uses as currency coins with values of 1 cent, 2 cents, 5 cents and 10 cents and bills with values of 5 cents, 10 cents, 20 cents and 100 cents. Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters.

    ie a(17) = 9494
    Sorry I had a logic flaw at first.

    for all n < 0: a(n) = 0
    a(0) = 1
    for all n > 0: a(n) = a(n-1) + a(n-2) + 2*a(n-5) + 2*a(n-10) + a(n-20) + a(n-100)

    Now my answer agrees with the problem statement. Safe to ignore what I wrote below.




    ~~~~~~ Begin original response ~~~~~~~

    This is common for the problem solving necessary for various computer science problems.

    Say a(n) is the number of ways to pay. If you pay with a 1 cent coin, you're left with n-1 coins. If you pay with a 2 cent coin, you're left with n-2 coins.

    Define: for all n \le 0, a(n) = 0.

    Define b(n) such that b(1) = 1; b(2..4) = 2 meaning b(2)=2, b(3)=2, b(4)=2; b(5..9) = 4; b(10..19) = 6; b(20..99) = 7; b(100..) = 8.

    Then for all n > 0: a(n) = b(n) + a(n-1) + a(n-2) + 2*a(n-5) + 2*a(n-10) + a(n-20) + a(n-100).

    Programmatically, we could implement with if-then statements;

    if (n < 1) return 0;
    s = 1 + a(n-1);
    if (n > 1) s += 1 + a(n-2);
    if (n > 4) s+= 2 + 2*a(n-5);
    etc.

    Edit: Hmm I'm getting a(17) = 14227, maybe I mistyped something. Edit 2: After fixing a bug, I now consistently get a(17)=21727 with the two different implementations given above. Can someone help decide whether this is right or the problem statement is right?

    ~~~~~~ End original response ~~~~~~~
    Last edited by undefined; September 6th 2010 at 04:58 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    Thanks a lot, I plugged in values to verify

    a(0) = 1
    a(1) = 1
    a(2) = 2
    a(3) = 3
    a(4) = 5
    a(5) = 10
    a(6) = 10 + 5 + 2 = 17
    a(7) = 17 + 10 + 4 = 31
    a(8) = 31 + 17 + 6 = 54
    a(9) = 54 + 31 + 10 = 95
    a(10) = 95 + 54 + 20 + 2 = 171
    a(11) = 171 + 95 + 34 + 2 = 302
    a(12) = 302 + 171 + 62 + 4 = 539
    a(13) = 539 + 302 + 108 + 6 = 955
    a(14) = 955 + 539 + 190 + 10 = 1694
    a(15) = 1694 + 955 + 342 + 20 = 3011
    a(16) = 3011 + 1694 + 604 + 34 = 5343
    a(17) = 5343 + 3011 + 1078 + 62 = 9494

    It makes perfect sense as to why you did it the way you did. Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    Thanks a lot, I plugged in values to verify

    a(0) = 1
    a(1) = 1
    a(2) = 2
    a(3) = 3
    a(4) = 5
    a(5) = 10
    a(6) = 10 + 5 + 2 = 17
    a(7) = 17 + 10 + 4 = 31
    a(8) = 31 + 17 + 6 = 54
    a(9) = 54 + 31 + 10 = 95
    a(10) = 95 + 54 + 20 + 2 = 171
    a(11) = 171 + 95 + 34 + 2 = 302
    a(12) = 302 + 171 + 62 + 4 = 539
    a(13) = 539 + 302 + 108 + 6 = 955
    a(14) = 955 + 539 + 190 + 10 = 1694
    a(15) = 1694 + 955 + 342 + 20 = 3011
    a(16) = 3011 + 1694 + 604 + 34 = 5343
    a(17) = 5343 + 3011 + 1078 + 62 = 9494

    It makes perfect sense as to why you did it the way you did. Thanks a lot!
    You're welcome! If you're curious, my first solution calculated a different thing, which is: the sum of the number of coins/bills used for every possible way to pay.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    That's cool. It seemed like that's what the question was asking for since it said "Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters." So I was a bit unsure there. I hate doing arithmetic on these...because if you screw one up, you screw all of them up.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    That's cool. It seemed like that's what the question was asking for since it said "Find a recurrence relation for the number of ways to pay a bill of n cents if the order in which the coins and bills are paid matters." So I was a bit unsure there. I hate doing arithmetic on these...because if you screw one up, you screw all of them up.
    The order mattering is simply a way of saying: paying a 3 cent bill with a 1 cent and then a 2 cent coin is different from paying with a 2 cent and then a 1 cent coin. It makes for a simple recursive solution.

    I don't think there was any ambiguity in the question, I simply used wrong logic the first time around, due to not being careful enough. I agree it's quite easy to make a little mistake that throws everything off.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    By the way, you might benefit from a CAS (computer algebra system) such as Pari/GP which I highly recommend (and is open source), I don't know about Mac but it's available in linux and windows distributions, (if google fails you can ask me how to set up), in it you can simply type

    Code:
    a(n)=if(n<0,0,if(n==0,1,a(n-1)+a(n-2)+2*a(n-5)+2*a(n-10)+a(n-20)+a(n-100)))
    and then just type a(17) and it spits out the answer, can be somewhat spoiling..
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    Thanks, I have one already that I use for school(it's required) but for my discrete mathematics course I'll need to work problems out anyway. This problem was somewhat similar to the one I need to turn in.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. Recursive relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 25th 2010, 07:17 AM
  4. Look at the recursive
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 14th 2010, 04:24 AM
  5. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM

Search Tags


/mathhelpforum @mathhelpforum