|
|
| Author |
Message |
Patrick Coilland
science forum Guru Wannabe
Joined: 29 Jan 2006
Posts: 197
|
 Posted: Sat May 27, 2006 1:40 pm Post subject:
100 bucks revisited
|
|
|
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  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
|
| Posted: Sun May 28, 2006 4:25 am Post subject:
Re: 100 bucks revisited
|
|
|
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 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
|
| Posted: Sun May 28, 2006 8:40 am Post subject:
Re: 100 bucks revisited
|
|
|
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 |
|
|
|
|
The time now is Wed Sep 08, 2010 4:29 am | All times are GMT
|
|
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
|
| |
|
Online Words | Cheap Home Insurance | Canon EOS 550D | Motorhome Insurance | Find jobs
|
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
