0
$\begingroup$

I'm having a bit of trouble understanding the order matters clause of a recurrence relation problem.

EX: A bus driver must pay a toll of 45 cents. Find a recurrence relation for the number of ways the driver can pay n cents. He can use only nickels and dimes.

My question: If the driver is trying to pay 10 cents, does that mean there are--

Three ways of paying: (first nickel + second nickel, second nickel + first nickel, dime)

OR

Two ways of paying: (two nickels, one dime)

$\endgroup$
1
$\begingroup$

If the question says somewhere that order matters I would read this as saying that the order in which you pay coins matters, but coins of the same type are indistinguishable from each other.

So 2 for your case. But for 15 cents the answer would be 3 because these are distinct: (nickel, nickel, nickel), (nickel, dime), and (dime, nickel).

However I would first look to see if there is an example matching my interpretation, and if not then I would ask the question of the teacher using 15 cents in the question.

$\endgroup$
1
$\begingroup$

It's not clear from the wording but most likely order does not matter since the same coins in any order will pay any given toll.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.