Soit $n$ un entier naturel non nul et $p$ un entier naturel. Il s’agit de déterminer le nombre exact de solutions de l’équation suivante, où toutes les inconnues sont des entiers naturels :
x_1+\dots+x_n=p.
Un exemple, pour $n=3$ et $p=4$
Vous cherchez tous les triplets possibles $(x_1,x_2,x_3)$ d’entiers naturels tels que :
x_1+x_2+x_3=4.
Vous allez traiter cette situation en envisageant toutes les possibilités pour l’inconnue $x_3.$
Cas où $x_3 = 4$
Dans ce cas, vous avez :
x_1+x_2 = 0.
Cela conduit immédiatement à $x_1=x_2=0.$
Il y a un triplet solution $(0,0,4).$
Cas où $x_3 = 3$
Dans ce cas, vous avez :
x_1+x_2 = 1.
Il y a deux possibilités, soit $x_1=1$ et $x_2=0$, soit $x_1=0$ et $x_2=1.$
Cela donne deux triplets $(1,0,3)$ et $(0,1,3).$
Cas où $x_3 = 2$
Dans ce cas, vous avez :
x_1+x_2 = 2.
Il y a trois possibilités, soit $x_1=2$ et $x_2=0$, soit $x_1=1$ et $x_2=1$, soit $x_1=0$ et $x_2=2.$
Cela donne trois triplets $(2,0,2)$, $(1,1,2)$ et $(0,2,2).$
Cas où $x_3 = 1$
Dans ce cas, vous avez :
x_1+x_2 = 3.
Il y a quatre possibilités, soit $x_1=3$ et $x_2=0$, soit $x_1=2$ et $x_2=1$, soit $x_1=1$ et $x_2=2$ et $x_1=0$ et $x_2=3.$
Cela donne quatre triplets $(3,0,1)$, $(2,1,1)$, $(1,2,1)$ et $(0,3,1).$
Cas où $x_3 = 0$
Dans ce cas, vous avez :
x_1+x_2 = 4.
Il y a cinq possibilités, soit $x_1=4$ et $x_2=0$, soit $x_1=3$ et $x_2=1$, soit $x_1=2$ et $x_2=2$ et $x_1=1$ et $x_2=3$, $x_1=0$ et $x_2=4.$
Cela donne cinq triplets $(4,0,0)$, $(3,1,0)$, $(2,2,0)$, $(1,3,1)$ et $(0,4,0).$
Concluez
Le nombre de solutions positives et entières de l’équation $x_1+x_2+x_3=4$ est égal à $15.$
ll serait intéressant de pouvoir généraliser. Aussi, vous allez traiter le cas où le nombre d’inconnues est égal à $n$ et où le résultat de la somme prend des petites valeurs.
Le nombre de solutions pour $n$ inconnues lorsque $p=0$
Il s’agit de résoudre $x_1+\dots+x_n=0$ où toutes les inconnues sont des entiers naturels. Du coup, toutes les inconnues sont nulles et il y a une seule solution, qui est le $n$-uplet suivant : $(0,\dots,0).$
Le nombre de solutions pour $n$ inconnues lorsque $p=1$
Il s’agit de résoudre $x_1+\dots+x_n=1$ où toutes les inconnues sont des entiers naturels.
Soit $(x_1,\dots,x_n)$ un $n$-uplet solution de cette équation.
Il est impossible que toutes les inconnues soient nulles. Du coup, au moins une d’entre elles notée $x_i$, avec $i$ compris entre $1$ et $n$ est supérieure ou égale à $1.$
Si $x_i\geq 2$, la somme $x_1+\dots+x_n$ est supérieure ou égale à $2$ ce qui contredit que $(x_1,\dots,x_n)$ est solution. Donc $x_i = 1.$ Il en résulte immédiatement que la somme $\sum_{j\neq i} x_j$ est nulle, donc toutes les autres inconnues sont nulles.
Il y a donc exactement $n$ solutions candidats possibles pour être solution.
Réciproquement, pour tout $i$ compris entre $1$ et $n$, considérons le $n$-uplet qui contient uniquement des zéros, sauf à la coordonnée numéro $i$ qui est égale à $1.$ La somme des coordonnées est bien égale à $1.$
Il y a donc en tout $n$ solutions.
Note. Pour $n=4$, les solutions seraient $(1,0,0,0)$, $(0,1,0,0)$, $(0,0,1,0)$ et $(0,0,0,1).$
Le nombre de solutions pour $n$ inconnues lorsque $p=2$
Il s’agit de résoudre $x_1+\dots+x_n=2$ où toutes les inconnues sont des entiers naturels.
Deux types de solutions sont possibles : les $n$-uplets dont l’une des coordonnées vaut $2$ et toutes les autres valent $0$. Il y en a exactement $n.$
Il y a aussi les $n$-uplets comportant deux coordonnées parmi $n$ égales à $1$, et les autres sont nulles, il y en a $\binom{n}{2} = \frac{n(n-1)}{2}.$
En définitive, le nombre de solutions est égal à :
\begin{align*}
n+\frac{n(n-1)}{2} &= \frac{2n}{2}+\frac{n(n-1)}{2}\\
&= \frac{n(2+n-1)}{2}\\
&=\frac{n(n+1)}{2}\\
&=\binom{n+1}{2}.
\end{align*} Le nombre de solutions pour $n$ inconnues lorsque $p=3$
Il s’agit de résoudre $x_1+\dots+x_n=3$ où toutes les inconnues sont des entiers naturels.
Trois types de solutions sont possibles : les $n$-uplets dont l’une des coordonnées vaut $3$ et toutes les autres valent $0$. Il y en a exactement $n.$
Il y a aussi les $n$-uplets comportant une coordonnée égale à $1$, une autre égale à $2$ et les autres sont nulles, il y en a $n(n-1)$ d’après le principe du produit.
Il y a aussi les $n$-uplets comportant trois coordonnées égales à $1$ parmi $n$, les autres étant nulles, il y en a $\binom{n}{3} = \frac{n(n-1)(n-2)}{6}.$
En définitive, le nombre de solutions est égal à :
\begin{align*}
n+n(n-1)+\frac{n(n-1)(n-2)}{6} &= \frac{6n}{6}+\frac{6n(n-1)}{6}+\frac{n(n-1)(n-2)}{6} \\
&=\frac{6n+n(n-1)(6+n-2)}{6}\\
&=\frac{6n+n(n-1)(n+4)}{6}\\
&=\frac{n[6+(n-1)(n+4)]}{6}\\
&=\frac{n(6+n^2+3n-4)}{6}\\
&=\frac{n(n^2+3n+2)}{6}\\
&=\frac{n(n+1)(n+2)}{6}\\
&=\binom{n+2}{3}.
\end{align*}
Avant de passer au cas général, vous aurez besoin d’un lemme sur les coefficients binomiaux
Vous allez démontrer la propriété suivante :
\boxed{\forall (a,b)\in\N^2,\quad \sum_{k=0}^b \binom{a+k}{a} = \binom{a+b+1}{a+1}.}Pour tout entier naturel $b$, vous notez $\mathscr{S}(b)$ la proposition suivante : « Pour tout entier naturel $a$, $\sum_{k=0}^b \binom{a+k}{a} = \binom{a+b+1}{a+1}.$ »
Initialisation. Pour $b=0.$
Soit $a$ un entier naturel.
D’une part, $\sum_{k=0}^0\binom{a+k}{a} = \binom{a}{a}=1.$
D’autre part, $\binom{a+0+1}{a+1} = \binom{a+1}{a+1} = 1.$
Du coup, $\mathscr{S}(0)$ est vérifiée.
Hérédité. Soit $b$ un entier naturel tel que $\mathscr{S}(b)$ soit vérifiée.
Soit $a$ un entier naturel. En séparant le dernier terme de la somme et en utilisant l’hypothèse de récurrence, il vient :
\begin{align*}
\sum_{k=0}^{b+1} \binom{a+k}{a} &= \sum_{k=0}^{b} \binom{a+k}{a} + \binom{a+b+1}{a}\\
&= \binom{a+b+1}{a+1}+ \binom{a+b+1}{a}.
\end{align*}Or, d’après la relation de Pascal sur les coefficient binomiaux :
\binom{a+b+1}{a}+\binom{a+b+1}{a+1} = \binom{a+b+2}{a+1}.Ainsi :
\sum_{k=0}^{b+1} \binom{a+k}{a} = \binom{a+(b+1)+1}{a+1}.La propriété $\mathscr{S}(b+1)$ est vérifiée.
Conclusion. Par récurrence, il a été démontré que pour tout entier naturel $b$, la propriété $\mathscr{S}(b)$ est vraie. Le résultat annoncé est bien démontré.
Passez au cas général
Bien que les dénombrements précédents aient été effectués avec des approches différentes, ils semblent tous converger vers un résultat qui va être démontré par récurrence, sur le nombre d’inconnues.
Pour tout entier naturel $n$ non nul, vous notez $\mathscr{P}(n)$ la proposition suivante : « Pour tout entier naturel $p$, le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n = p$ est égal au coefficient binomial $\binom{n+p-1}{p}$. »
Initialisation. Pour $n=1.$ Soit $p$ un entier naturel. La résolution de l’équation à une inconnue positive entière $x_1=p$ possède une seule solution. Or, $\binom{1+p-1}{p} = \binom{p}{p}=1$ donc $\mathscr{P}(1)$ est vérifiée.
Hérédité. Soit $n$ un entier naturel tel que $\mathscr{P}(n)$ soit vérifiée.
Soit $p$ un entier naturel, vous cherchez le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n+x_{n+1}=p.$
Lorsque $x_{n+1} = 0$, l’équation s’écrit $x_1+\dots+x_n=p$ elle possède $n$ variables positives et entières donc d’après l’hypothèse de récurrence, il y a $\binom{n+p-1}{p} = \binom{n+p-1}{n-1}$ solutions.
Plus généralement l’inconnue $x_{n+1}$ peut être égale à $k$, où $k\in\llbracket 0, p\rrbracket.$ l’équation à résoudre s’écrit $x_1+\dots+x_n=p-k$ et d’après l’hypothèse de récurrence, elle possède $\binom{n+p-k-1}{p-k} =\binom{n+p-k-1}{n-1}$ solutions.
D’après cette analyse, le nombre de solutions de l’équation $x_1+\dots+x_n+x_{n+1}=p$ est égal à la somme suivante :
\sum_{k=0}^p\binom{n+p-k-1}{n-1}.En effectuant le changement d’indice $\ell = p-k$, vous obtenez :
\sum_{k=0}^p\binom{n+p-k-1}{n-1} = \sum_{\ell=0}^p\binom{n-1+\ell}{n-1}.D’après le lemme, la somme $\sum_{\ell=0}^p\binom{n-1+\ell}{n-1}$ est égale au coefficient binomial $\binom{n+p}{n} = \binom{n+p}{p} = \binom{(n+1)+p-1}{p}.$
La propriété $\mathscr{P}(n+1)$ est vérifiée.
Conclusion. Par récurrence, il a été établi que pour tout entier naturel non nul $n$, $\mathscr{P}(n)$ est vérifiée.
Concluez
Pour tout entier naturel $n$ non nul et pour pour tout entier naturel $p$, le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n = p$ est égal au coefficient binomial $\binom{n+p-1}{p}$.
Prolongements
Inéquation
Soit $n$ un entier naturel $n$ non nul et $p$ un entier naturel. Déterminez le nombre de solutions positives et entières de l’inéquation $x_1+\dots+x_n \leq p.$
Raccourci combinatoire
Pourriez-vous démontrer, en utilisant l’assertion « on obtient $n$ quantités à partir de $n-1$ piquets », que pour tout entier naturel $n$ non nul et pour pour tout entier naturel $p$, le nombre de solutions positives et entières de l’équation $x_1+\dots+x_n = p$ est égal au coefficient binomial $\binom{p+(n-1)}{n-1}$ ?
Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !