Nombre de solutions entières d'une équation

Salut est-ce que quelqu'un peut m'indiquer comment je peux calculer le nombre d'entiers naturels vérifiant l'équation suivante.
$a_{1}+a_{2}+\cdots +a_{p}=k,$ où $k$ et $p$ sont des entiers naturels non nuls.

Réponses

  • La question signifie-t-elle : étant donnés $p \in \mathbb N^*$ et $k \in \mathbb N$, calculer le nombre de $p$-uplets $(a_1,a_2,...,a_p) \in \mathbb N^p$ tels que :
    $a_{1}+a_{2}+....+a_{p}=k$ ?
  • Oui c'est ça
  • J'ai mis $k \in \mathbb N$ et non $k \in \mathbb N^*$ parce qu'on peut considérer le cas $k=0$.
    C'est un marronnier. Il y a plusieurs façons de traiter cette question.
    Une attaque possible. Tu notes $T(p,k)$ le nombre cherché, tu peux dresser empiriquement le tableau des valeurs de $T(p,k)$ pour les petites valeurs de $p$ et de $k$, et tu verras apparaître des nombres familiers, et tu pourras faire une conjecture, et avoir des idées pour la démonstration.
    Bon courage.
    Fr. Ch.
  • Corriger le titre
  • Bonjour,
    A une telle suite $a = (a_1, \cdots, a_p)$ de somme $k$, on associe une autre suite $a'$ constituée de $1$ et $0$ de la manière suivante :
    $$
    a' = \overbrace {1 1 \cdots 1}^{a_1}\ 0\ \overbrace {1 1 \cdots 1}^{a_2}\ 0\ \cdots\ 0\ \overbrace {1 1 \cdots 1}^{a_{p-1}}\ 0\ \overbrace {1 1 \cdots 1}^{a_p}
    $$En français : il y a $a_1$ fois 1 puis un 0 puis $a_2$ fois 1 puis un 0 ....etc... Bien entendu certains $a_i$ peuvent être nuls.

    A. Quel est le nombre de termes de la suite $a'$ ?
    B. Combien de zéros dans la suite $a'$ ?
    C. Peut-on retrouver la suite $a$ à partir de la suite $a'$ ? Comment ?
    D. Il y a une correspondance biunivoque entre l'ensemble $A$ des suites $a$ vérifiant . .... et l'ensemble $A'$ des suites de $0,1$ de longueur ? et contenant ? zéros.
    E. En déduire le cardinal de $A$.
  • Bon, Claude Quitté, c'est une des façons de traiter le problème, c'est bien loin d'être la seule. Il n'est pas certain que ce soit celle qui convienne le mieux à Nemya. J'avais tenté de la lancer sur une autre piste : expérimentation, conjecture, puis démonstration par... C'est une autre façon, c'est bien loin d'être la seule, elle non plus.
    On a déjà parlé maintes fois de ce problème sur ce forum, c'est un marronnier, ai-je dit.
    Tiens, ce pourrait être l'occasion de récapituler les méthodes de résolution de ce problème... Et pourquoi pas les fonctions génératrices ?
    Tout dépend du niveau où se place Nemya. Peut-être prépa-HEC ? La balle est dans son camp.
    Bonne soirée.
    Fr. Ch.
  • Une autre méthode. À chaque $p$-uplet $(a_1,a_2,...,a_p) \in \mathbb N^p$ tel que : $a_{1}+a_{2}+....+a_{p}=k$, on associe le $p$-uplet $(b_1,b_2,...,b_p) $ tel que : $b_i=a_1+a_2+...+a_i+i$.
    On définit ainsi une bijection de l'ensemble des $p$-uplets en question sur l'ensemble des $p$-uplets $(b_1,b_2,...,b_p) \in \mathbb N^p$ tels que : $1 \le b_1<b_2<...<b_{p-1}<b_p=k+p$.
    Le nombre cherché est donc le nombre des $(p-1)$-parties $\{ b_1,...,b_{p-1} \}$ de l'ensemble $\{1,2,...,k+p-1\}$, soit...
    C'est juste pour donner une autre méthode, dont je doute qu'elle convienne, elle non plus, à la questionneuse
    Bonne nuit.
    Fr. Ch.
  • Juste pour s'amuser, voici la méthode des fonctions génératrices.
    Soit la série entière formelle : $ \displaystyle F(X)=\frac{1}{1-X}=\underset{\ell =0}{\overset{+\infty }{\sum }}X^{\ell }$. Alors, pour $ p \in \mathbb N ^*$ : $\displaystyle \frac{1}{(1-X)^{p}}=(F(X))^{p}=\underset{\ell _{1}=0}{\overset{+\infty }{\sum }}X^{\ell _{1}}\underset{\ell _{2}=0}{\overset{+\infty }{\sum }}X^{\ell
    _{2}}...\underset{\ell _{p}=0}{\overset{+\infty }{\sum }}X^{\ell _{p}}=\underset{k=0}{\overset{+\infty }{\sum }}c_{p,k}X^{k}$,
    où $\displaystyle c_{p,k}=\underset{\ell _{1}+\ell _{2}+...+\ell _{p}=k}{\underset{\ell_{1}\in \mathbb{N},\ell _{2}\in \mathbb{N},...,\ell _{p}\in \mathbb{N}}{\sum }}1$, autrement dit : $\displaystyle c_{p,k}=\underset{\ell _{1}+\ell _{2}+...+\ell _{p}=k}{\underset{(\ell_{1},\ell _{2},...,\ell _{p})\in \mathbb{N}^{p}}{\sum }}1$.
    Ce coefficient $c_{p,k}$ est donc le nombre de $p$-uplets $(\ell _{1},\ell _{2},...,\ell _{p})\in \mathbb{N}^{p}$ tels que $\ell _{1}+\ell _{2}+...+\ell _{p}=k$, c'est le nombre que nous cherchons, que j'avais noté $T(p,k)$ dans un message précédent.
    Pour le calculer, dérivons la série : $ \displaystyle F^{\prime }(X)=\frac{1}{(1-X)^{2}}=\underset{\ell =1}{\overset{+\infty }{\sum }}\ell X^{\ell -1}$, puis
    $ \displaystyle F^{\prime \prime }(X)=\frac{2}{(1-X)^{3}}=\underset{\ell =2}{\overset{+\infty }{\sum }}\ell (\ell -1)X^{\ell -2}$, etc., bref pour tout $ q \in \mathbb N$ :
    $ \displaystyle F^{(q)}(X)=\frac{q!}{(1-X)^{q+1}}=\underset{\ell =q}{\overset{+\infty }{\sum }}\ell (\ell -1)...(\ell -q+1)X^{\ell -q}$.
    D'où : $ \displaystyle \frac{1}{(1-X)^{q+1}}=\underset{\ell =q}{\overset{+\infty }{\sum }}\frac{\ell (\ell -1)...(\ell -q+1)}{q!}X^{\ell -q}=\underset{\ell =q}{\overset{+\infty }{\sum }}\binom{\ell }{q}X^{\ell -q}=\underset{k=0}{\overset{+\infty
    }{\sum }}\binom{k+q}{q}X^{k}$
    Et enfin, pour tout $ p \in \mathbb N ^*$ : $ \displaystyle \frac{1}{(1-X)^{p}}=\underset{k=0}{\overset{+\infty }{\sum }}\binom{k+p-1}{%
    p-1}X^{k}$.
    Ce qui résout la question.
    J'ai rédigé en séries entières formelles pour me changer les idées, mais on peut rédiger en séries entières tout court, réelles ou complexes, avec rayon de convergence égal à $1$, ceci dit pour les niveaux d'enseignement qui ne connaîtraient pas les séries entières formelles (classes prépas).
    On peut même calculer $\displaystyle \frac{1}{(1-z)^{p}}=\underset{k=0}{\overset{+\infty }{\sum }}c_{p,k}z^{k}$ sans dérivation, par récurrence sur $p$, pour ceux qui ne connaîtraient pas les séries entières du tout, mais seulement les séries numériques.

    Mais je ne crois pas que cette solution convienne non plus à Nemya, qui devrait se manifester.

    Bonne journée.
    Fr. Ch.
    15/03/2020
    N'oubliez pas de voter aux élections municipales, premier tour.
  • Tant qu'on y est, et dans la série "comment écraser un acarien avec un marteau-piqueur", voilà une autre idée utilisant la Méthode du Cercle de Hardy-Littlewood-Ramanujan.

    On note $\mathcal{D}_p(k)$ le dénumérant en question, i.e. le nombre de solutions entières de l'équation proposée ici. On a, pour tout $\rho \in \left]0,1 \right[$
    \begin{align*}
    \mathcal{D}_p(k) &= \frac{1}{2 \pi i} \oint_{|z| = \rho} \left( \sum_{j=0}^\infty z^k \right)^p \frac{\textrm{d}z}{z^{k+1}} = \frac{1}{2 \pi i} \oint_{|z| = \rho} \frac{1}{(1-z)^p} \frac{\textrm{d}z}{z^{k+1}} \\
    &= \sum_{j=0}^\infty {p+j-1 \choose j} \frac{1}{2 \pi i} \oint_{|z| = \rho} \frac{\textrm{d}z}{z^{k-j+1}} \\
    &= \sum_{j=0}^\infty {p+j-1 \choose j} \times \begin{cases} 1, & \textrm{si} \ k=j \, ; \\ 0, & \textrm{sinon} \, ; \end{cases} = {p+k-1 \choose k}.
    \end{align*}
    Le nom méthode du cercle provient de ce que l'on intègre sur un cercle de rayon $< 1$. Dans les cas plus compliqués (problème de Goldbach, par exemple), on prend un rayon $\rho(k)$ qui dépend de $k$ et tel que $\rho(k) \to 1$ lorsque $k \to \infty$.
  • Devant le silence de Nemya, je vais développer ma première solution.
    Étant donnés $p \in \mathbb N^*$ et $k \in \mathbb N$, je note $c_{p,k}$ (et non plus $T(p,k)$) le nombre de $p$-uplets $(a_1,a_2,...,a_p) \in \mathbb N^p$ tels que : $a_{1}+a_{2}+....+a_{p}=k$. Une méthode d'attaque, c'est la méthode expérimentale dans les modèles réduits.
    Pour les petites valeurs de $p$ et $k$, on peut dresser empiriquement le tableau des $c_{p,k}$ :
    \begin{array}{cccccc}
    \mathbf{\mathit{p}~\backslash ~\mathit{k}} & \mathbf{0} & \mathbf{1} &
    \mathbf{2} & \mathbf{3} & \mathbf{4} \\
    \mathbf{1} & 1 & 1 & 1 & 1 & 1 \\
    \mathbf{2} & 1 & 2 & 3 & 4 & 5 \\
    \mathbf{3} & 1 & 3 & 6 & 10 & 15 \\
    \mathbf{4} & 1 & 4 & 10 & 20 & \ast \\
    \mathbf{5} & 1 & 5 & 15 & \ast & \ast \end{array}
    On reconnaît les coefficients binomiaux et le triangle de Pascal, disposé différemment qu'à l'ordinaire.
    On observe que, pour $p \ge 2$ et $k \ge 1$ on a : $c_{p,k}=c_{p,k-1}+c_{p-1,k}$. Pourquoi ?

    Parmi les $p$-uplets $(a_1,a_2,...,a_p) \in \mathbb N^p$ tels que : $a_{1}+a_{2}+....+a_{p}=k$, il y a ceux pour qui $a_p=0$ et ceux pour qui $a_p \ge 1$.
    Le nombre de ceux pour qui $a_p=0$ est le nombre des $(p-1)$-uplets $(a_1,a_2,...,a_{p-1}) \in \mathbb N^{p-1}$ tels que : $a_{1}+a_{2}+....+a_{p-1}=k$ ; ce nombre est $c_{{p-1},k}$.
    Le nombre de ceux pour qui $a_p \ge 1$ est le nombre des $p$-uplets $(a_1,a_2,...,a'_{p}) \in \mathbb N^p$ tels que : $a_{1}+a_{2}+....+a_{p-1}+a'_{p}=k-1$, avec $a'_{p}=a_{p}-1$ ; ce nombre est $c_{p,{k-1}}$.

    On a ainsi démontré la formule de récurrence de Pascal sous la forme : $c_{p,k}=c_{p,k-1}+c_{p-1,k}$.
    Cette formule permet de remplir sans mal, rapidement, le tableau précédent à partir de $c_{1,k}=c_{p,0}=1$.

    Maintenant, il faut en déduire la valeur de $c_{p,k}$ avec un raisonnement par récurrence, qui reste à rédiger.

    Bonne journée, joyeux équinoxe.
    Fr. Ch.
Connectez-vous ou Inscrivez-vous pour répondre.