Petit problème pas si évident..

Bonjour à tous,

Serait-il possible de m'aider à résoudre un problème de combinatoire svp..

Voici l'énoncé :

Trouver le nombre de possibilité de décomposer 185€ en utilisant des billets de 5,10,20 et 50€.

Existe-t-il une formule générale permettant de donner ce nombre immédiatement ?

Merci!

Salut,

oui, il existe une méthode générale.

Dans ton cas, le nombre de possibilités est le coefficient de x^{185} dans la fonction génératrice 1/((1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})).

Je te laisse en déduire la méthode générale.

Ce serait le coefficient de x^185 au dénominateur alors ?

Le problème étant que je dois fournir une réponse rapidement...

Ici, les calculs sont assez monstrueux...

Si tu sais qd meme me donner la réponse que tu trouves dans ce cas afin dêtre sûr de pas faire d'erreur ca m'interesserait merci !

Ah..
Le problème c'est que je ne vois pas de méthode(s) plus courte...
En fait, il faudrait faire ce calcul sous mathematica ou un logiciel du genre.. que je ne possède pas..

Bonjour,

La réponse est 187

Décomposer 185 en billets de 5, 10, 20 et 50 revient à décomposer 37 en "billets" de 1, 2, 4 et 10

si j'appelle ce nombre f({1,2,4,10}, 37), j'ai :
f({1,2,4,10}, 37) =
f({1,2,4}, 37) sans billets de 10
+ f({1,2,4}, 27) avec 1 billet de 10
+ f({1,2,4}, 17) avec 2 billets de 10
+ f({1,2,4}, 7) avec 3 billets de 10

mais :
f({1,2,4}, 37) =
f({1,2}, 37) sans billets de 4
+ f({1,2}, 33) avec 1 billet de 4
+ f({1,2}, 29) avec 2 billets de 4
+ f({1,2}, 25) avec 3 billets de 4
+ f({1,2}, 21) avec 4 billets de 4
+ f({1,2}, 17) avec 5 billets de 4
+ f({1,2}, 13) avec 6 billets de 4
+ f({1,2}, 9) avec 7 billets de 4
+ f({1,2}, 5 ) avec 8 billets de 4
+ f({1,2}, 1) avec 9 billets de 4

On a ainsi :
f({1,2,4,10}, 37) =
f({1,2}, 37)
+ f({1,2}, 33)
+ f({1,2}, 29)
+ f({1,2}, 25)
+ f({1,2}, 21)
+ f({1,2}, 17)
+ f({1,2}, 13)
+ f({1,2}, 9)
+ f({1,2}, 5 )
+ f({1,2}, 1)
+ f({1,2}, 27)
+ f({1,2}, 23)
+ f({1,2}, 19)
+ f({1,2}, 15)
+ f({1,2}, 11)
+ f({1,2}, 7)
+ f({1,2}, 3)
+ f({1,2}, 17)
+ f({1,2}, 13
+ f({1,2}, 9)
+ f({1,2}, 5)
+ f({1,2}, 1)
+ f({1,2}, 7)
+ f({1,2}, 3)

Quant à f({1,2}, n) , on trouve aisément que cela vaut 1 + [n/2]
et donc :

({1,2,4,10}, 37) =
f({1,2}, 37) 19
+ f({1,2}, 33) 17
+ f({1,2}, 29) 15
+ f({1,2}, 25) 13
+ f({1,2}, 21) 11
+ f({1,2}, 17) 9
+ f({1,2}, 13) 7
+ f({1,2}, 9) 5
+ f({1,2}, 5 ) 3
+ f({1,2}, 1) 1
+ f({1,2}, 27) 14
+ f({1,2}, 23) 12
+ f({1,2}, 19) 10
+ f({1,2}, 15) 8
+ f({1,2}, 11) 6
+ f({1,2}, 7) 4
+ f({1,2}, 3) 2
+ f({1,2}, 17) 9
+ f({1,2}, 13 7
+ f({1,2}, 9) 5
+ f({1,2}, 5) 3
+ f({1,2}, 1) 1
+ f({1,2}, 7) 4
+ f({1,2}, 3) 2

= 187


========================
Pour le fun, on peut trouver une formule générale :

f({1,2,4,10},n) = n^3/480
+ (9 - mod(n,2)) n^2/160
+ (212 - 51 mod(n,2)) n/480

+ (( 1 - mod(n,20)/20) mod(n,4) + (3/2 - mod(n+10,20)/20) mod(n+2,4) - mod(n+2,4)) mod(n,2)/8
- (( 1 - mod(n,20)/20) mod(n,4)^2 + (3/2 - mod(n+10,20)/20) mod(n+2,4)^2 - mod(n+2,4)^2) /16
- mod(n,10)^3/480
+ (1+mod(n,2))mod(n,10)^2/160
+ (11- 3mod(n,2)) mod(n,10)/240
+ 1 - mod(n,2)/2

--
Patrick