Formule du multinôme de Newton

En mathématiques, la formule du multinôme de Newton est une formule donnant le développement d'une puissance entière naturelle n d'une somme d'un nombre fini m de nombres sous forme d'une somme de produits de puissances de ces nombres 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 ${\displaystyle m=2}$ ; et dans ce cas les coefficients multinomiaux sont les coefficients binomiaux.

Énoncé

Soient m et n deux entiers naturels, ${\displaystyle m\geqslant 1}$, et x₁, x₂,..., x_m 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 m éléments commutent deux à deux). Alors,

${\displaystyle (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}}}$.

La somme porte sur tous les m-uplets d'indices entiers naturels (k₁, k₂,...,k_m) tels que k₁ + k₂ + ... + k_m = n, certains d'entre eux pouvant être nuls.

Une écriture équivalente mais bien plus concise consiste à sommer sur tous les multi-indices ${\displaystyle {\vec {k}}}$ de dimension m dont le module ${\displaystyle \left|{\vec {k}}\right|=\sum \nolimits _{i=1}^{m}k_{i}}$ est égal à n :

${\displaystyle \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}}}$

Les nombres

${\displaystyle {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}!}}}$

sont appelés les coefficients multinomiaux.

Le coefficient multinomial ${\displaystyle {n \choose k_{1},k_{2},k_{3},\ldots ,k_{m}}}$ est également le nombre de « partitions ordonnées » d'un ensemble à n éléments en m ensembles de cardinaux successifs k₁, k₂,...,k_m. Plus formellement :

${\displaystyle {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\neq j\Rightarrow I_{i}\cap I_{j}=\emptyset )\right\}.}$

Par exemple, les 3 «partitions ordonnées» comptées par ${\displaystyle {\binom {3}{2,1,0}}}$ sont ${\displaystyle (\{1,2\},\{3\},\{\})}$ , ${\displaystyle (\{2,3\},\{1\},\{\})}$, ${\displaystyle (\{3,1\},\{2\},\{\})}$.

Et plus concrètement, ${\displaystyle {n \choose k_{1},k_{2},k_{3},\ldots ,k_{m}}}$ est le nombre de mots de longueur n formés avec un alphabet de m caractères, le premier caractère étant répété k₁ fois, le deuxième, k₂ fois, ..., le m-ième, k_m fois. Par exemple, le nombre d'anagrammes du mot Mississipi vaut ${\displaystyle {10 \choose 4,4,1,1}=6300}$.

Démonstrations

Une preuve directe est d'utiliser l'avant-dernière expression ci-dessus des coefficients multinomiaux^[1].

Une autre est de raisonner par récurrence sur m, en utilisant la formule du binôme^[2].

Enfin, on peut utiliser le développement en série entière (ou simplement formelle) de l'exponentielle^[3].

Exemples et dénombrements

• ${\displaystyle {\begin{aligned}(a+b+c)^{3}&=(a^{3}b^{0}c^{0}+a^{0}b^{3}c^{0}+a^{0}b^{0}c^{3})+3(a^{2}b^{1}c^{0}+a^{1}b^{2}c^{0}+a^{0}b^{1}c^{2}+a^{0}b^{2}c^{1}+a^{1}b^{0}c^{2}+a^{2}b^{0}c^{1})+6a^{1}b^{1}c^{1}\\&=a^{3}+b^{3}+c^{3}+3(a^{2}b+ab^{2}+bc^{2}+b^{2}c+ac^{2}+a^{2}c)+6abc.\end{aligned}}}$

Dans les exemples suivants, les indices intervenant dans les diverses sommes sont supposés être distincts, ne jamais se répéter et être compris entre 1 et n ; s'il n'y a pas de possibilité pour ces indices, la somme est égale à 0 par convention.

• ${\displaystyle \left(\sum x_{i}\right)^{2}=\sum x_{i}^{2}+2\sum _{i<j}x_{i}x_{j}}$
• ${\displaystyle \left(\sum x_{i}\right)^{3}=\sum x_{i}^{3}+3\sum x_{i}^{2}x_{j}+6\sum x_{i}x_{j}x_{k}}$
• ${\displaystyle \left(\sum x_{i}\right)^{4}=\sum x_{i}^{4}+4\sum x_{i}^{3}x_{j}+6\sum x_{i}^{2}x_{j}^{2}+12\sum x_{i}^{2}x_{j}x_{k}+24\sum x_{i}x_{j}x_{k}x_{l}}$

Si l'on range les coefficients multinomiaux en triangle de sorte que dans la ligne n se trouvent les ${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}}$ avec ${\displaystyle k_{1}\geqslant k_{2}\geqslant \dots \geqslant k_{m}\geqslant 1}$, les ${\displaystyle (k_{1},k_{2},\dots ,k_{m})}$ étant rangés dans l'ordre lexicographique descendant, on obtient les premières lignes, en commençant à n = 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 suite A036038 de l'OEIS.

Notons que dans ce triangle le nombre de termes de la ligne n est égal au nombre ${\displaystyle p(n)}$ de partitions de l'entier n ; la somme des termes d'une ligne est répertoriée comme suite A005651 de l'OEIS.

Le nombre total de termes dans le développement de ${\displaystyle \left(\sum _{i=1}^{m}x_{i}\right)^{n}}$ est égal, lui, au nombre de monômes unitaires de degré n formés à partir de x₁, x₂,..., x_m , soit le nombre de leurs n-combinaisons avec répétitions ${\displaystyle \Gamma _{m}^{n}={m+n-1 \choose n}.}$

Lien entre coefficients multinomiaux et binomiaux, et applications

On a : ${\displaystyle {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}}}}$ , formules que l'on obtient naturellement lorsqu'on cherche le nombre de mots de longueur n formés avec un alphabet de m caractères, le premier caractère étant répété k₁ fois, le deuxième, k₂ fois, ..., le m-ième, k_m fois.

Ceci peut être un moyen simple de prouver que ${\displaystyle {\frac {n!}{k_{1}!k_{2}!k_{3}!\dots k_{m}!}}}$ est entier si ${\displaystyle k_{1}+k_{2}+k_{3}+\dots +k_{m}=n}$.

Par exemple, pour tous entiers naturels ${\displaystyle a,b}$, ${\displaystyle {\frac {(ab)!}{(a!)^{b}}}={ab \choose a,a,\ldots ,a}}$ est entier.

Généralisation de la relation de Pascal aux coefficients multinomiaux

On a, pour ${\displaystyle n\geqslant 1}$ et ${\displaystyle k_{1}+k_{2}+k_{3}+\dots +k_{m}=n}$ :

${\displaystyle {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}}}$

ce qui découle par exemple de ${\displaystyle (x_{1}+x_{2}+\dots +x_{m})^{n}=(x_{1}+x_{2}+\dots +x_{m})^{n-1}(x_{1}+x_{2}+\dots +x_{m})}$.

Notes et références

1. Cette preuve combinatoire est disponible par exemple dans Louis Comtet, Analyse combinatoire avancée, Techniques de l'ingénieur (lire en ligne), p. 3 et sur Wikiversité, dans le lien ci-dessous.
2. Cette preuve par récurrence est disponible par exemple sur Wikiversité, dans le lien ci-dessous.
3. Cette preuve « analytique » est disponible par exemple dans Comtet, p. 3 et sur Wikiversité, dans le lien ci-dessous.

Voir aussi

Sur les autres projets Wikimedia :

• Formule du multinôme, sur Wikiversity

Articles connexes

• Formule du trinôme de Newton
• Permutation avec répétition
• Loi multinomiale

Bibliographie

(en) Paul Erdős et Ivan Niven, « The number of multinomial coefficients », Amer. Math. Monthly, vol. 61,‎ 1954, p. 37-39 (lire en ligne)

• Portail de l’algèbre