Analyse combinatoire et dénombrement

Multinôme de Newton :

Vous l’avez sans doute deviné, tout comme pour le coefficient binomial, il est également possible de généraliser le binôme de Newton, qu’on appelle, le multinôme de Newton, ou simplement multinôme.

Commençons encore par une application, grâce à laquelle nous allons construire la formule :

Supposons que nous ayons (a+b+c)^3, et qu’on veuille connaître la formule qui nous permettrai de calculer cette expression. A première vu, nous n’avons pas d’autre choix que de développer…

(a+b+c)^3=(a+b+c)(a+b+c)(a+b+c)=(a^2+2ab+b^2+2ac+2cb+c^2)(a+b+c)=a^3+a^2b+a^2c+2a^2b+2ab^2+2abc+b^2a+b^3+b^2c+2a^2c+2abc+2ac^2+2acb+2cb^2+2c^2b+c^2a+c^2b+c^3=a^3+3a^2b+3ab^2+6abc+b^3+3b^2c+3a^2c+3ac^2+3c^2b+c^3

Nous avons trouvé le résultat, mais ceci nécessite un calcul lourd, d’autant plus lourd qu’il y a de termes dans la parenthèse et le degrés de notre polynôme. Il nous faut donc trouver une formule pour calculer plus rapidement…

En fait, si on réécris ça de manière plus succincte, on peut se rendre compte de quelque chose :

(a+b+c)^3=a^3+3a^2b+3a^2c+3ab^2++b^3+3b^2c+6abc+3c^2a+3c^2b+c^3

En effet, on pourrait réécrire ceci comme suit :

(a+b+c)^3= \begin{pmatrix} 3 \\ 3,0,0 \end{pmatrix} a^3b^0c^0 + \begin{pmatrix} 3 \\ 2,1,0 \end{pmatrix}a^2b^1c^0+ \begin{pmatrix} 3 \\ 2,0,1 \end{pmatrix} a^2b^0c^1+ \begin{pmatrix} 3 \\ 1,2,0 \end{pmatrix} a^1b^2c^0+ \begin{pmatrix} 3 \\ 0,3,0 \end{pmatrix} a^0b^3c^0+ \begin{pmatrix} 3 \\ 0,2,1 \end{pmatrix} a^0b^2c+ \begin{pmatrix} 3 \\ 1,1,1 \end{pmatrix} a^1b^1c^1+ \begin{pmatrix} 3 \\ 1,0,2 \end{pmatrix} a^1b^0c^2+ \begin{pmatrix} 3 \\ 0,1,2 \end{pmatrix} a^0b^1c^2 + \begin{pmatrix} 3 \\ 0,0,3 \end{pmatrix} a^0b^0c^3

Je pense que vous voyez maintenant ou nous allons. En effet, nous avons reformulé l’expression à l’aide du binôme de Newton (trinôme en l’occurrence), et du coefficient multinomial (dont nous avons défini dans la page précédente que le coefficient binomial était un cas particulier).

Nous allons à présent pouvoir exprimer la formulation générale du multinôme de Newton.
Soit (x_1,x_2,...,x_r) \in \mathbb{C}, et soit (k_1,k_2,...,k_r) \in \mathbb{N}, et avec n,r > 1, alors :

\boxed{(x_1+x_2+...+x_r)^n= \displaystyle{\sum_{k_1+k_2+...+k_r=n} \begin{pmatrix} n \\ k_1,k_2,...,k_r \end{pmatrix}x_1^{k_1}x_2^{k_2}...x_r^{k_r}}}

Expliquons cette formule, et tentons de répondre à une question que vous vous posez probablement, qui est la suivante : Comment savoir combien de termes nous avons dans la somme ?

Vous l’avez certainement compris, les x_i sont simplement des nombres (réels, complexes ou des entiers), substituant et généralisant à r termes, une expression prenant pour valeurs a,b,c par exemple.
Que veut dire ce symbole de somme sous lequel on a « Somme des k_i=n » ? En fait, c’est très simple, si on reprend l’exemple de (a+b+c)^3, on voit que dans chaque terme de la somme, la somme des degrés de abc est toujours n.

Ensuite vient le coefficient multinomial, ce qui est logique car r>2.

Pour ce qui est du produit des x_i, ceci est une généralisation du binôme de Newton, en effet dans la formule du binôme, on se rappelle, qu’à droite de la formule, on a a^k b^{n-k}. Nous avons vu sur la page précédente que lorsque k=2, n-k pouvait être remplacé par k_2. Ayant r terme dans l’exemple actuel, c’est comme si nous avions a^{k_1} b^{n-k_1} c^{n-k_1-k_2} etc…
On voit très bien ce qu’il se passe dans notre exemple de (a+b+c)^3.

Maintenant… Qu’en est-il du nombre de termes dans la somme ? C’est une question un peu plus compliquée.

En fait, tout le raisonnement se base sur le fait qu’on fixe \sum_{k_i}=n, les k_i sont donc une décomposition de l’entier n.
On peut prendre un exemple analogue à l’exemple des ronds et des barres dans la page des combinaisons sans répétitions. Si on a r=3 et n=4, cela revient à trouver le nombres de 3-combinaisons possibles de 4 objets (En effet, il peut y avoir des répétitions, et x_1+x_2+...+x_r=n=4) parmi 4+2 objets (n ronds + r-1 barres). Exemple :

o|oo|o
Ceci représente le triplet [1,2,1]

Par conséquent, la formule pour connaître le nombre de termes dans un multinôme de Newton est :

\boxed{\begin{pmatrix} n+r-1 \\ n \end{pmatrix}= \displaystyle{\frac{(n+r-1){!}}{n{!}(r-1){!}}}}

On pourrait reprendre notre premier exemple, mais nous allons en prendre un autre, dans lequel on va définir n \neq r. Prenons (a+b+c+d)^3.

Si on applique la formule, on a donc :

\begin{pmatrix} 3+4-1 \\ 3 \end{pmatrix}= \displaystyle{\frac{6{!}}{3{!}3{!}}=20}

Le nombre de termes de la somme du multinôme pour n=3 et r=4 est donc 20.
Nous vous laissons développer pour vérifier que ceci est vrai 🙂

Publicité
Pages : 1 2 3 4 5 6 7