Math Is Fun Forum

Transcending

Member

Registered: 2015-06-15

Posts: 12

Combinations and Permutations

In South Africa the currency is made up of Rands, R, and cents, c, and there are six coins currently in circulation:
1c, 2c, 5c, 10c, 20c, 50c, R1, R2, R5.

It is possible to make R10 in the following way:
1 × R5 + 1 × R2 + 2 × R1 + 1 × 50c + 1 × 20c + 2 × 10c + 1 × 5c + 1 × 2c + 3 × 1c

How many different ways can R10 be made using any number of coins?

A•     335 868 921
B•     41 789 014
C•     265 532 101

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

Hi;

Did you copy the question correctly? For one thing that is more than six types of coins. When I compute the answer based on those coins I do not get one of the choices.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Transcending

Member

Registered: 2015-06-15

Posts: 12

Re: Combinations and Permutations

Yes that is exactly how the question is set. You have been very helpful, thank you.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

It is easy to formulate this problem but it is not so easy to compute the number. The problem also needs some clarification.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,996

Website

Re: Combinations and Permutations

Did you use a brain?

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

billy412

Member

Registered: 2016-04-28

Posts: 1

Re: Combinations and Permutations

what was the answer?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

Hi;

That is obviously not the right question.

there are six coins currently in circulation:
1c, 2c, 5c, 10c, 20c, 50c, R1, R2, R5.

This is 9 coins not 6.

I can get the answer using generating functions and computation. Do you have the right question? For this question I am getting 327631321 ways. This has been checked in 3 ways. Since it is not one of the choices I can only conclude that the question has not been copied correctly.

Did you use a brain?

You certainly do not mean a human brain do you?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Monox D. I-Fly

Member

From: Indonesia

Registered: 2015-12-02

Posts: 2,000

Re: Combinations and Permutations

You certainly do not mean a human brain do you?

Did you use a reptilian brain?

---

Actually I never watch Star Wars and not interested in it anyway, but I choose a Yoda card as my avatar in honor of our great friend bobbym who has passed away.
May his adventurous soul rest in peace at heaven.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

Did you use a reptilian brain?

The reppie brain is not good for computation I am told. As a matter of fact they are contemptuous of human mathematics.

Be that as it may the whole computation required generating functions and a CAS.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Combinations and Permutations

Using C++ program I am getting a value of 327631469 slightly different from bobbym.

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

phanthanhtom

Member

Registered: 2012-06-22

Posts: 290

Re: Combinations and Permutations

Uhm, the REAL South African Rand does have six coins in circulation: 10c, 20c, 50c, 1R, 2R and 5R.

Would it help now?

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Combinations and Permutations

Uhm, the REAL South African Rand does have six coins in circulation: 10c, 20c, 50c, 1R, 2R and 5R.

Would it help now?

It will make the problem shorter. we are not bothered about it . It is a fictitious problem.

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Combinations and Permutations

with only 6 coins as mentioned the number of ways come to 4710.

Last edited by thickhead (2016-05-10 05:08:50)

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

Hi;

I am getting 4562.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Combinations and Permutations

I had some error in my C++ program. With 6 types of coins the results being not very lengthy I could check the ways of having the coins and I found some duplicates. I could eliminate the error to get no. of ways 4562. Accordingly with 9 coins (results not checked) it came to 327631321.
But going by C++ is hard way. Would bobbym give out the generating function which would give the value quickly?

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

The gf's will be difficult to compute without a CAS or without a program to multiply large polynomials.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,996

Website

Re: Combinations and Permutations

A dp solution also works

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

Yes, but the gf's, recurrences, integral are much nicer.

This is the gf:

or

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,996

Website

Re: Combinations and Permutations

Why are there two terms in the last expression?

I life the gf better but to extract information from it, you need a dp

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Combinations and Permutations

Yes, but the gf's, recurrences, integral are much nicer.

This is the gf:

or

I think the expression should be like

but then what would you substitute for x to get the number of ways?
but my solution has no calculation. it starts with a counter {2,0,0,0,0,0,0,0,0} to represent 9 counters for the different coins and using functions to go downstream and have a count to add up the ways one by one. the next would be {1,2,1,0,0,0,0,0,0} done by a function "changeR5"  making count=2 and sending the counter to "changeR2" and "changeR1" etc. the programmer does not know how many times each function is called but the final value of "count " determines the number of ways. i had some difficulty since i made a C++ program after 20 years' gap.

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,879

Re: Combinations and Permutations

Hi;

I adapted a Python code I found on SE and got 4,562 for the 6 coins (in 0.02 seconds) and 327,631,321 for the 9 coins (in 6.1 minutes).

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Combinations and Permutations

I took 3 days to write and solve in C++. i have not yet digested generating function and now Python code.

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,879

Re: Combinations and Permutations

I don't know GFs, C++ or Python (I know some BASIC and a tiny bit of M), but the Python code from StackExhange was clear enough for me to be able to modify it to suit the two puzzles.

Last edited by phrontister (2016-05-12 01:37:08)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations and Permutations

I think the expression should be like

Both forms are correct.

I took 3 days to write and solve in C++

That is an important point. 3 days to write and .01 seconds to run in C++. Coding in M takes 5 minutes to write and 20 seconds to run, which is faster?

but then what would you substitute for x to get the number of ways?

You do not have to substitute for x, you expand out the polynomial and check the coefficient of x^1000.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Combinations and Permutations

But to learn mathematica I would take years and one should have the software.

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}