contestada

A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. find a recurrence relation for the number of ways to pay a bill of n pesos if the order in which the coins and bills are paid matters.

Respuesta :

metchelle
In order to find the recurrence relation, find first the pattern by writing the terms. 

If one pays a certain amount of pesos (n) , it could be shown as follows:
To pay 1 peso -              then n-1 peso
To pay 2 peso coin-       then n-2 peso if n≥2
To pay 5 peso coin-       then n-5 peso if n≥5
To pay 10 peso coin-     then n-10 peso if n≥10
To pay 5 peso bill-         then n-5 peso if n≥5
To pay 10 peso bill-       then n-10 peso if n≥10
To pay 20 peso bill-       then n-20 peso if n≥20
To pay 50 peso bill-       then n-50 peso if n≥50
To pay 100 peso bill-     then n-100 peso if n≥100

A₀ = 1
The pattern being each new option is part of the recurrence relation. Therefore:
(note: n-1, n-2,... and so on are subscript of A)
 
An = An−1+An−2+An−5+An−10+An-5+ An-10+An−20+An−50+An−100An
An = An−1+An−2+2An−5+2An−10+An−20+An−50+An−100An

Otras preguntas