Monnaie romaine: semis, triens et quadrans.
dans Arithmétique
Auguste souhaite payer une somme de $10 000$ as.
Il dispose d'un très grand stock de pièces composé uniquement de semis, triens et quadrans.
De combien de manières différentes peut-il payer cette somme?
Al-Kashi
Il dispose d'un très grand stock de pièces composé uniquement de semis, triens et quadrans.
De combien de manières différentes peut-il payer cette somme?
Al-Kashi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il manque la définition de certains mots, que je n'ai pas envie d'aller pêcher je ne sais où.
Sinon, le terme général de la série génératrice d'une partition particulière devrait faire l'affaire.
Cordialement,
Rescassol
Dans la cas où tu n'aurais pas de réponse à la question posée, et si je n'ai pas fait d'erreur,
$$ \forall n \in \N,\:\: \text{Card} \Big\{ (x,y,z) \in \N^3 \mid \dfrac x2 + \dfrac y3 + \dfrac z4 =n \Big \} = (n+1)^2.$$
J'ai bien le même résultat que toi. Il suffit en effet de raisonner modulo $3$ puis $2$.
Je me suis intéressé au cas général de l'équation $ax+by+cz=n$ l'année dernière.
Le problème devient plus délicat dans le cas général. J'ai néanmoins réussi à traiter certains cas généraux qui il me semble ne sont pas résolubles avec les séries génératrices.
Al-Kashi
L'équation "générale" $ax+by+cz =n$ peut se traiter avec les séries génératrices. C'est d'ailleurs la raison pour laquelle je ne me suis pas trop fatigué pour fournir une réponse.
Soient $a,b,c \in \N^*\:\text{distincts},\:\:\: m:=\text{PPCM} (a,b,c).\:\:$ On note $ \:P\in\Z[X] $ défini par: $ \:\:P(X)= \dfrac {X^m-1}{X^a-1} \dfrac{X^m-1}{X^b-1}\dfrac{X^m-1}{X^c-1} =\displaystyle \sum_{k=0} ^d a_kX^k, \quad d =3m -a-b-c,\quad \forall k \in [\![0;d]\!],\quad a_k \in \N,\:\:a_k = a_{d-k}.$
Soit $n\in \N.\:$ On note respectivement $\:q_n\:$ et $\:r_n\:$ le quotient et le reste de la division euclidienne de $n$ par $\: m.\:\:$ Alors:
$$\text{Card} \Big \{ (x,y,z) \in \N^3 \mid ax+by +cz =n\Big\} = \displaystyle \sum _{k=0} ^2 \binom {q_n +2-k}2 a_{km + r_n} $$
Arrives-tu par exemple à obtenir une relation close pour le cas $23x+19y+42z=n$?
Al-Kashi
Je ne comprends pas ce que tu reproches au juste à la formule que j'ai indiquée, qui n'énonce que des choses bien connues et fournit immédiatement une réponse à $\:6x+4y+3z =12n.$
Je ne pense pas qu'il en existe, pour le cas général, de franchement plus simple. J'aurais d'ailleurs tendance à la qualifier de close car il n'y aura au maximum que $3$ termes sous le symbole $\Sigma$.
L'expression du nombre de solutions cherché dépend bien entendu du reste de la division de $n$ par $m =23\times19\times42.\:\:$.Il faut alors bien sûr calculer les $a_k,\:\:(0\leqslant k\leqslant165102)$ en développant
$P(X)= \Big (1+ X^a+\dots (X ^a)^{ \frac ma-1}\Big)\Big(1 +X^b\dots (X^b)^{\frac mb-1}\Big)\Big(1 +X^c \dots (X^c)^{\frac mc-1}\Big)$ et le nombre cherché (pardon de me répéter) est :
$$\binom {q_n+2}2 a_{r_n} + \binom {q_n +1}2 a _{m+r_n} + \binom {q_n}2 a_{2m + r_n}$$
Le degré de complexité du calcul des $a_k$ ne dépend que des données $a,b,c$ et non de $n$.
Dans le dénombrement qui a initié ce fil, on avait $ m = 12, \: q_n =n, \: r_n =0, \:a_0 = a_{12} =1,\: a_{24}=0.$
Non, il ne s'agit pas d'un reproche. En fait je suis d'accord avec toi sur le fait que de manière générale la formule que tu rappelles permet de donner une méthode pour déterminer le résultat souhaité.
Ce que je veux dire, c'est que dans la plupart des cas, cette méthode n'est guère pratique car elle entraîne de longs calculs et qu'il était du coup intéressant de tenter de développer d'autres méthodes pour obtenir des résultats.
Par exemple, pour l'équation proposée $23x+19y+42z=n$, qui relève du cas général $ax+by+(a+b)z=n$, on peut éviter les calculs de coefficients et obtenir une formule close assez simple.
Al-Kashi
Je ne sais pas si tu as tenté avec les séries génératrices. Voilà ce que j'obtiens en empruntant un chemin de piétons pour reprendre ton expression:
On se ramène sans perte de généralité au cas où $a$ et $b$ sont premiers entre eux non nuls.On note:
$\forall (k,p)\in\N^{2}$, $(k)_p$ le reste de la division euclidienne de $k$ par $p$.
$\tilde{a}$ l'inverse de $a \mod (a+b)$.
$\tilde{b}$ l'inverse de $b \mod (a+b)$.
On pose $ \sigma=\dfrac{n-a(\tilde{a}n)_{a+b}}{a+b}$ et $ \theta=\dfrac{n-b(\tilde{b}n)_{a+b}}{a+b}$
Sauf erreur de ma part, le nombre de solutions de l'équation $ax+by+(a+b)z=n$ est :
Si $n\not\equiv 0 \mod (a+b)$:
$$\Big\lfloor \dfrac{\sigma+a}{a} \Big\rfloor \Big(1+\sigma-\dfrac{a}{2}\Big\lfloor \dfrac{\sigma}{a} \Big\rfloor\Big)+\Big\lfloor \dfrac{\theta+b}{b} \Big\rfloor \Big(1+\theta-\dfrac{b}{2}\Big\lfloor \dfrac{\theta}{b} \Big\rfloor\Big)$$
Si $n\equiv 0 \mod (a+b)$:
$$\Big\lfloor \dfrac{\sigma+a}{a} \Big\rfloor \Big(1+\sigma-\dfrac{a}{2}\Big\lfloor \dfrac{\sigma}{a} \Big\rfloor\Big)+\Big\lfloor \dfrac{\theta+b}{b} \Big\rfloor \Big(1+\theta-\dfrac{b}{2}\Big\lfloor \dfrac{\theta}{b} \Big\rfloor\Big)-\dfrac{n}{a+b}-1$$
Al-Kashi
C'est assez bien pour moi.