De combien de façons payer une somme ?

De combien de façons payer une somme ?

On dispose de pièces de valeurs pieces = [1, 2, 5] en quantité illimitée. On veut compter le nombre de façons de payer une somme $S$, l'ordre des pièces ne comptant pas ($2+1$ et $1+2$ sont la même façon).

• Énumérer à la main les façons de payer $5$.
• On note w[s] le nombre de façons de payer $s$ avec les pièces déjà traitées. Expliquer pourquoi le programme suivant est correct, puis donner le nombre de façons de payer $10$.

def nb_facons(pieces, S):
    w = [1] + [0] * S          # une seule facon de payer 0 : rien
    for p in pieces:
        for s in range(p, S + 1):
            w[s] = w[s] + w[s - p]
    return w[S]

• Que compterait-on si l'on échangeait les deux boucles ?