3.6 Retour sur le problème des pièces de monnaie

Dans le problème des pièces de monnaie, nous avons résolu le problème à l’aide d’une récurrence, puis d’une fonction génératrice ordinaire, et nous avons remarqué que les deux méthodes nous donnaient des solutions différentes. À l’aide de la récurrence, notre solution tenait compte de l’ordre des pièces, alors qu’avec les fonctions génératrices ordinaires, notre solution n’en tenait pas compte. Une question intéressante se pose maintenant. Est-ce que les fonctions génératrices exponentielles pourraient nous permettre d’obtenir la même solution que celle que nous avions obtenue à l’aide de la récurrence ? À première vue, la réponse semble être oui, mais en essayant, on remarque assez rapidement qu’il y a un problème.

Les valeurs semblent correctes, sauf pour $\displaystyle 7$ et $\displaystyle 9$ qui nous donnent des valeurs complètement absurdes. Que s’est-il passé ? On remarque assez rapidement que $\displaystyle 7$ et $\displaystyle 9$ pence sont les deux plus petits montants qui nécessitent à la fois des pièces de $\displaystyle 2$ pence et de $\displaystyle 5$ pence. Le problème se répète par la suite pour tous les montants qui nécessitent ces deux pièces. Le problème est que la fonction génératrice exponentielle considère les pièces de deux pence et de cinq pence non pas comme une seule pièce, mais plutôt comme $\displaystyle 2$ et $\displaystyle 5$ pièces individuelles respectivement. Les fonctions génératrices exponentielles ne peuvent donc pas nous permettre d’obtenir directement la même solution que celle que nous avions obtenue à l’aide de la récurrence.

Il y a cependant une façon de contourner ce problème, mais il nous faut utiliser une combinaison de fonctions génératrices ordinaires et exponentielles, et donc cela nécessite deux variables. Si nous considérons $\displaystyle x$ comme une variable représentant les montants et $\displaystyle y$ une seconde variable tenant compte du nombre de pièce. Comme seul les pièces individuelles doivent tenir compte de l’ordre, ces seulement le $\displaystyle y$ qui sera une fonction génératrice exponentielle, les $\displaystyle x$ resteront sous la forme d’une fonction génératrice ordinaire. On obtient donc:

Ceci nous indique que pour faire un montant de $\displaystyle 7$ pence, il y a deux façons en utilisant deux pièces. Pour faire un montant de $\displaystyle 8$ pence, il y a une seule façon en utilisant quatre pièce. Pour faire un montant de $\displaystyle 9$ pence, il y a $\displaystyle 3$ façons en utilisant trois pièces, puis pour faire un montant de $\displaystyle 10$ pence, il y a une façon en utilisant cinq pièce et une façon qui utilise deux pièce (et donc 2 façons au total). Ceci correpond donc à ce que nous avions obtenu en utilisant une récurrence. On peut ensuite utiliser le code Python suivant pour obtenir un tableau complet.