FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
100 bucks revisited
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
Author Message
Patrick Coilland
science forum Guru Wannabe


Joined: 29 Jan 2006
Posts: 197

PostPosted: Sat May 27, 2006 1:40 pm    Post subject: 100 bucks revisited Reply with quote

Some days ago, Rahul asked for the number of possibilities of composing
n dollars with 1, 2, 5, 10, 20, 50 or 100 coins/notes (order does not
matter, coins/notes unlimited).

Here is a closed form of this number.
If I call nb({1,2,5,10,20,50, 100}, n) the requested number, then :


nb({1,2,5,10,20,50, 100}, n) = a6(n) * n^6 /7200000000
+ a5(n) * n^5 /600000000
+ a4(n) * n^4 /144000000
+ a3(n) * n^3 /1200000
+ a2(n) * n^2 /720000
+ a1(n) * n /2400
+ a0(n) * 1 /6

With coefficients being functions of mod(n,.), bounded and periodic
(period 100) :

a6(n) = 1
a5(n) = 47
a4(n) = 2327 + 6f(n)
a3(n) = 1754 + 19f(n) + 2g(n)
a2(n) = 37837 + 1437f(n) + 342g(n) + 6k(n) + 6k(n+10)
a1(n) = 873 + 223f(n) + 98g(n) + 6k(n) + 2k(n+10) + 24*l(n)
a0(n) = 6 + 6f(n) + 6g(n) + k(n) + 6*l(n) + 6m(n)


f(n) = 3mod(n,5)/20 - mod(n,5)^2/20 - mod(n,10)/20
- mod(n,2)/2 + mod(n,2) (mod(n,10) - mod(n,5))/10

g(n) = - mod(n,10)^3 /600
+ mod(n,10)^2 /200
+ (1 - 6f(n)) mod(n,10) /60

k(n) = - mod(n,20)^4 /8000
+ mod(n,20)^3 /2000
+ (11 - 6f(n)) mod(n,20)^2 /400
- ( 1 + 6g(n)) mod(n,20) /20

l(n) = - mod(n,50)^5 /12000000
+ mod(n,50)^4 /400000
+ (21 - 2f(n) ) mod(n,50)^3 /120000
- (14 - f(n) + 2g(n)) mod(n,50)^2 /4000
- (89 - 11f(n) - 6g(n) + 4k(n+10)) mod(n,50) /1200
- (k(n) - k(n+10)) mod(n,100)/600

m(n) = - mod(n,100)^6 /7200000000
+ mod(n,100)^5 /200000000
+ ( 313 - 6f(n)) mod(n,100)^4 /144000000
+ ( - 64 + f(n) - 2g(n) ) mod(n,100)^3 /1200000
+ (-6217 + 183f(n) + 18g(n)
- 6k(n) - 6k(n+10)) mod(n,100)^2 /720000
+ ( 245 - 5f(n) + 10g(n) - 2k(n)
+ 2k(n+10) - 24*l(n))mod(n,100) /2400

===================================================================
And, for example :
nb({1,2,5,10,20,50, 100}, 50) = 451
nb({1,2,5,10,20,50, 100}, 100) = 4563

It is certainly simplier to write a little (very few lines) computer
prog to find the number, rather than computing this formula Smile but I
found funny (!) to establish it. I wasn't sure it existed such a closed
form.

--
Patrick
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sun May 28, 2006 4:25 am    Post subject: Re: 100 bucks revisited Reply with quote

Patrick Coilland wrote:
Quote:
Some days ago, Rahul asked for the number of possibilities of composing
n dollars with 1, 2, 5, 10, 20, 50 or 100 coins/notes (order does not
matter, coins/notes unlimited).

Here is a closed form of this number.
If I call nb({1,2,5,10,20,50, 100}, n) the requested number, then :


nb({1,2,5,10,20,50, 100}, n) = a6(n) * n^6 /7200000000
+ a5(n) * n^5 /600000000
+ a4(n) * n^4 /144000000
+ a3(n) * n^3 /1200000
+ a2(n) * n^2 /720000
+ a1(n) * n /2400
+ a0(n) * 1 /6

With coefficients being functions of mod(n,.), bounded and periodic
(period 100) :

a6(n) = 1
a5(n) = 47
a4(n) = 2327 + 6f(n)
a3(n) = 1754 + 19f(n) + 2g(n)
a2(n) = 37837 + 1437f(n) + 342g(n) + 6k(n) + 6k(n+10)
a1(n) = 873 + 223f(n) + 98g(n) + 6k(n) + 2k(n+10) + 24*l(n)
a0(n) = 6 + 6f(n) + 6g(n) + k(n) + 6*l(n) + 6m(n)


f(n) = 3mod(n,5)/20 - mod(n,5)^2/20 - mod(n,10)/20
- mod(n,2)/2 + mod(n,2) (mod(n,10) - mod(n,5))/10

g(n) = - mod(n,10)^3 /600
+ mod(n,10)^2 /200
+ (1 - 6f(n)) mod(n,10) /60

k(n) = - mod(n,20)^4 /8000
+ mod(n,20)^3 /2000
+ (11 - 6f(n)) mod(n,20)^2 /400
- ( 1 + 6g(n)) mod(n,20) /20

l(n) = - mod(n,50)^5 /12000000
+ mod(n,50)^4 /400000
+ (21 - 2f(n) ) mod(n,50)^3 /120000
- (14 - f(n) + 2g(n)) mod(n,50)^2 /4000
- (89 - 11f(n) - 6g(n) + 4k(n+10)) mod(n,50) /1200
- (k(n) - k(n+10)) mod(n,100)/600

m(n) = - mod(n,100)^6 /7200000000
+ mod(n,100)^5 /200000000
+ ( 313 - 6f(n)) mod(n,100)^4 /144000000
+ ( - 64 + f(n) - 2g(n) ) mod(n,100)^3 /1200000
+ (-6217 + 183f(n) + 18g(n)
- 6k(n) - 6k(n+10)) mod(n,100)^2 /720000
+ ( 245 - 5f(n) + 10g(n) - 2k(n)
+ 2k(n+10) - 24*l(n))mod(n,100) /2400

===================================================================
And, for example :
nb({1,2,5,10,20,50, 100}, 50) = 451
nb({1,2,5,10,20,50, 100}, 100) = 4563

It is certainly simplier to write a little (very few lines) computer
prog to find the number, rather than computing this formula Smile but I
found funny (!) to establish it. I wasn't sure it existed such a closed
form.

I had several recurrences that solved the problem ---

] N_n(0) = 1
] N_n(k<0) = 0
] N_1(k) = N_1(k-1)
] N_5(k) = N_1(k)+N_5(k-5)
] N_10(k) = N_5(k)+N_10(k-10)
] ...

and it isn't too difficult to solve these one at a time. Any
introductory combinatorics book will show you how to solve (in theory)
recurrence relations such as these.

--- Christopher Heckman
Back to top
Patrick Coilland
science forum Guru Wannabe


Joined: 29 Jan 2006
Posts: 197

PostPosted: Sun May 28, 2006 8:40 am    Post subject: Re: 100 bucks revisited Reply with quote

Proginoskes nous a récemment amicalement signifié :
Quote:

and it isn't too difficult to solve these one at a time. Any
introductory combinatorics book will show you how to solve (in theory)
recurrence relations such as these.


You're right, the recurrence is quite obvious (no need of introductory
combinatorics book) :
nb({1}, n) = 1
nb({1,2}, n) = sum(0<=2k<=n, nb({1}, n-2k))
nb({1,2,5}, n) = sum(0<=5k<=n, nb({1,2}, n-5k))
nb({1,2,5,10}, n) = sum(0<=10k<=n, nb({1,2,5}, n-10k))
nb({1,2,5,10,20}, n) = sum(0<=20k<=n, nb({1,2,5,10}, n-20k))
....

The question is to *solve* the recurrence to obtain a closed form.
On a practical point of view, there are a lot of intermediate recurrence
to solve.

For example, must be solved :
S(r,n) = sum(0<= k <=n, k^r)
==> well known, and easy with Bernouilli numbers
T(p,r,n) = sum(0<= kp <=n, (n-kp)^r)
==> less easy with Bernouilli numbers again
U(p,r,n,a) = sum(0<= kp <=n, mod(n-kp,a)^r)
==> less less easy

This is the reason for which the complete exact closed form
of nb({1,2,5,10,20,50,100}, n) seemed no so obvious to obtain for me.

But I can understand that it would be obvious for you :-)

BTW, I was happy to solve it and I posted the result not for glory but
just for those interested in.

--
Patrick
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
The time now is Tue Dec 12, 2017 9:59 pm | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts FLMTA Prize #1: S(n)=0 & n>(phi(x)*phi(y)*phi(z)/8) --> t... DGoncz@aol.com Math 5 Thu Jul 20, 2006 9:46 pm
No new posts The Riemann Hypothesis Revisited Ivan Iliev num-analysis 0 Sat Jul 15, 2006 6:07 pm
No new posts The Riemann Hypothesis Revisited Ivan Iliev Math 0 Sat Jul 15, 2006 5:59 pm
No new posts Higgs boson revisited muser Particle 5 Mon Jul 10, 2006 11:17 pm
No new posts Oil Revisited Bill_Vajk Research 1 Sat Jul 08, 2006 2:37 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.3599s ][ Queries: 16 (0.3428s) ][ GZIP on - Debug on ]