Formule du multinôme de Newton
En mathématiques, la formule du multinôme de Newton est une relation donnant le développement d'une puissance entière Modèle:Mvar d'une somme d'un nombre fini Modèle:Mvar de termes sous forme d'une somme de produits de puissances de ces termes affectés de coefficients, lesquels sont appelés des coefficients multinomiaux. La formule du binôme s'obtient comme cas particulier de la formule du multinôme, pour Modèle:Math ; et dans ce cas les coefficients multinomiaux sont les coefficients binomiaux.
Énoncé
Soient Modèle:Mvar et Modèle:Mvar deux entiers naturels, <math> m\geqslant1</math>, et Modèle:Math des nombres réels ou complexes (ou plus généralement, des éléments d'un anneau commutatif, voire seulement d'un anneau, à condition que ces Modèle:Mvar éléments commutent deux à deux). Alors,
- <math>(x_1 + x_2 + x_3 + \dots + x_m)^n
= \sum_{k_1+k_2+k_3+\ldots+k_m=n} {n \choose k_1, k_2, k_3, \dots, k_m}
x_1^{k_1} x_2^{k_2} x_3^{k_3} \dots x_m^{k_m}</math>.
La somme porte sur tous les m-uplets d'indices entiers naturels Modèle:Math tels que Modèle:Math, certains d'entre eux pouvant être nuls.
Une écriture équivalente mais bien plus concise consiste à sommer sur tous les multi-indices <math>\vec k</math> de dimension Modèle:Mvar dont le module <math>\left|\vec k\right| = \sum\nolimits_{i=1}^m k_i</math> est égal à Modèle:Mvar :
- <math>\left( \sum_{i=1}^m x_i \right)^n = \sum_{\left|\vec k\right|=n} {n\choose\vec k} \prod_{i=1}^m x_i^{k_i}</math>
Les nombres
- <math>{n \choose k_1, k_2, k_3, \ldots, k_m} = {n\choose\vec k} = \frac{n!}{k_1! k_2! k_3! \dots k_m!} = \frac{n!}{\prod_{i=1}^m k_i!}</math>
sont appelés les coefficients multinomiaux.
Le coefficient multinomial <math>{n \choose k_1, k_2, k_3, \ldots, k_m}</math> est également le nombre de « partitions ordonnées » d'un ensemble à Modèle:Mvar éléments en Modèle:Mvar ensembles de cardinaux successifs Modèle:Math. Plus formellement :
<math> {n \choose k_1, k_2, \ldots, k_m}= \operatorname{Card}\left\{(I_1,I_2,\cdots I_m) | \forall i,j \quad I_i \subset\{1,2,\cdots n\},\quad\operatorname{Card}(I_i)=k_i~\text{et}~(i\ne j\Rightarrow I_i\cap I_j=\emptyset) \right\}.</math>
Par exemple, les 3 «partitions ordonnées» comptées par <math> \binom{3}{2,1,0}</math> sont <math> (\{1,2\},\{3\},\{\})</math> , <math> (\{2,3\},\{1\},\{\})</math>, <math> (\{3,1\},\{2\},\{\})</math>.
Et plus concrètement, <math>{n \choose k_1, k_2, k_3, \ldots, k_m}</math> est le nombre de mots de longueur Modèle:Mvar formés avec un alphabet de Modèle:Mvar caractères, le premier caractère étant répété Modèle:Math fois, le deuxième, Modèle:Math fois, ..., le Modèle:Mvar-ième, Modèle:Mvar fois. Par exemple, le nombre d'anagrammes du mot Mississipi vaut <math>{10 \choose 4,4,1,1}=6300</math>.
Démonstrations
Une preuve directe est d'utiliser l'avant-dernière expression ci-dessus des coefficients multinomiaux<ref>Cette preuve combinatoire est disponible par exemple dans Modèle:Ouvrage et sur Wikiversité, dans le lien ci-dessous.</ref>.
Une autre est de raisonner par récurrence sur Modèle:Mvar, en utilisant la formule du binôme<ref>Cette preuve par récurrence est disponible par exemple sur Wikiversité, dans le lien ci-dessous.</ref>.
Enfin, on peut utiliser le développement en série entière (ou simplement formelle) de l'exponentielle<ref>Cette preuve « analytique » est disponible par exemple dans Modèle:Harvsp et sur Wikiversité, dans le lien ci-dessous.</ref>.
Exemples et dénombrements
- <math>
\begin{align} (a+b+c)^3&=(a^3b^0c^0+a^0b^3c^0+a^0b^0c^3)+3(a^2b^1c^0+a^1b^2c^0+a^0b^1c^2+a^0b^2c^1+a^1b^0c^2+a^2b^0c^1)+6a^1b^1c^1\\
&=a^3+b^3+c^3+3(a^2b+ab^2+bc^2+b^2c+ac^2+a^2c)+6abc.
\end{align} </math>
Dans les exemples suivants, les indices intervenant dans les diverses sommes sont supposés être distincts et compris entre 1 et Modèle:Mvar ; s'il n'y a pas de possibilité pour ces indices, la somme est égale à 0 par convention.
- <math>
\left(\sum x_i\right)^2=\sum x_i^2+2\sum x_ix_j </math>
- <math>
\left(\sum x_i\right)^3=\sum x_i^3+3\sum x_i^2x_j+6\sum x_ix_jx_k </math>
- <math>
\left(\sum x_i\right)^4=\sum x_i^4+4\sum x_i^3x_j+6\sum x_i^2x_j^2+12\sum x_i^2x_jx_k+24\sum x_ix_jx_kx_l </math>
Si l'on range les coefficients multinomiaux en triangle de sorte que dans la ligne Modèle:Mvar se trouvent les <math>{n \choose k_1, k_2, \ldots, k_m}</math> avec <math>k_1\geqslant k_2\geqslant \dots\geqslant k_m\geqslant1</math>, les <math>(k_1, k_2, \dots, k_m)</math> étant rangés dans l'ordre lexicographique descendant, on obtient les premières lignes, en commençant à Modèle:Mvar = 1 :
1
1, 2
1, 3, 6
1, 4, 6, 12, 24
1, 5, 10, 20, 30, 60, 120
1, 6, 15, 20, 30, 60, 90, 120, 180, 360, 720
Voir la Modèle:OEIS.
Notons que dans ce triangle le nombre de termes de la ligne Modèle:Mvar est égal au nombre <math>p(n)</math> de partitions de l'entier Modèle:Mvar ; la somme des termes d'une ligne est répertoriée comme Modèle:OEIS.
Le nombre total de termes dans le développement de <math>\left( \sum_{i=1}^m x_i \right)^n </math> est égal, lui, au nombre de monômes unitaires de degré Modèle:Mvar formés à partir de Modèle:Math , soit le nombre de leurs Modèle:Mvar-combinaisons avec répétitions <math>\Gamma_m^n={m+n-1\choose n}.</math>
Lien entre coefficients multinomiaux et binomiaux, et applications
On a : <math>{n \choose k_1, k_2, k_3, \ldots, k_m} = \frac{n!}{k_1! k_2! k_3! \dots k_m!} = \binom n{k_1}\binom {n-k_1}{k_2}\binom {n-k_1-k_2}{k_3}\cdots\binom {n-k_1-\cdots-k_{m-1}}{k_m}</math> , formules que l'on obtient naturellement lorsqu'on cherche le nombre de mots de longueur Modèle:Mvar formés avec un alphabet de Modèle:Mvar caractères, le premier caractère étant répété Modèle:Math fois, le deuxième, Modèle:Math fois, ..., le Modèle:Mvar-ième, Modèle:Mvar fois.
Ceci peut être un moyen simple de prouver que <math>\frac{n!}{k_1! k_2! k_3! \dots k_m!}</math> est entier si <math>k_1+ k_2+ k_3+ \dots+ k_m=n</math>.
Par exemple, pour tous entiers naturels <math>a,b</math>, <math>\frac{(ab)!}{(a!)^b}={ab \choose a,a, \ldots, a} </math> est entier.
Généralisation de la relation de Pascal aux coefficients multinomiaux
On a, pour <math>n\geqslant1</math> et <math>k_1+ k_2+ k_3+ \dots+ k_m=n</math> :
<math>{n-1\choose k_1-1,k_2,k_3, \dots, k_m}+{n-1 \choose k_1,k_2-1,k_3,\dots, k_m
}+\cdots+{n-1\choose k_1,k_2,k_3,\dots,k_m-1} = {n\choose k_1, k_2, k_3, \dots, k_m}</math>
ce qui découle par exemple de <math>(x_1 + x_2 + \dots + x_m)^n =(x_1 + x_2 + \dots + x_m)^{n-1} (x_1 + x_2 + \dots + x_m)
</math>.
