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.
$a_{1}+a_{2}+\cdots +a_{p}=k,$ où $k$ et $p$ sont des entiers naturels non nuls.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$a_{1}+a_{2}+....+a_{p}=k$ ?
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.
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$.
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.
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.
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.
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$.
É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.
http://www.les-mathematiques.net/phorum/read.php?34,1544316,1544448#msg-1544448