Search   Memberlist   Usergroups
 Page 1 of 1 [3 Posts]
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
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
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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [3 Posts]
 The time now is Thu Aug 16, 2018 2:42 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics 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 The Riemann Hypothesis Revisited Ivan Iliev num-analysis 0 Sat Jul 15, 2006 6:07 pm The Riemann Hypothesis Revisited Ivan Iliev Math 0 Sat Jul 15, 2006 5:59 pm Higgs boson revisited muser Particle 5 Mon Jul 10, 2006 11:17 pm Oil Revisited Bill_Vajk Research 1 Sat Jul 08, 2006 2:37 pm