Coefficients binomiaux, multinomiaux et dénombrement

Les coefficients binomiaux sont des entiers notés $\binom{n}{k}$, avec $n$ et $k$ deux entiers naturels, $n$ étant non-nul.

On peut les exprimer avec une formule relativement simple :

$\binom{n}{k} = \frac{n!}{k! (n-k)!}$

Formule du binôme de Newton

Les coefficients binomiaux apparaissent dans le développement des binômes de Newton, d’où ils tiennent leur nom. Un binôme de Newton est une expression de la forme $(x + y)^n$ avec $n$ un entier naturel.

Par exemple, pour $n = 2$, on peut vérifier que :

$(x + y)^2 = x^2 + 2xy + y^2 = \binom{2}{0} x^2 + \binom{2}{1} xy + \binom{2}{2}y^2$

De même pour $n = 3$, on peut vérifier que :

$(x + y)^3 = x^3 + 3 x^2y + 3xy^2 + y^3 = \binom{3}{0}x^3 + \binom{3}{1}x^2y + \binom{3}{2}xy^2 + \binom{3}{3} y^3$

Plus généralement, on a :

$(x+y)^n = \sum_{k = 0}^n \binom{n}{k}x^k y^{n-k}$

Je présente ici l’expression avec les factorielles en premier, mais en pratique la formule est issue du développement du binôme plutôt que l’inverse, notamment via le triangle de Pascal, ou de la relation associée.

Interprétation en termes combinatoires

À toute première vue, les coefficients binomiaux sont un simple résultat de calcul : on développe l’expression, on réduit les monômes et on voit combien il y en a. On peut cependant prendre un angle d’attaque combinatoire !

Choix possibles lors du développement

On peut voir l’opération de développement comme un choix de $x$ ou $y$ pour chaque parenthèse. Combien de fois je veux voir $x$ dans mon monôme, et combien de fois $y$ ? De combien de manière puis-je choisir mes parenthèses pour que ça arrive ?

Par exemple, pour $n = 3$, on a :

$(x+y)^3 = (x+y)(x+y)(x+y)$

Développer en une fois reviens à choisir pour chaque parenthèse $x$ ou $y$. Il suffit en fait de choisir les parenthèses où on prend $y$, les autres étant alors automatiquement un choix de $x$ vu qu’il n’y a pas d’autre choix possible.

Si je veux former $y^3$, comment puis-je procéder ? Je n’ai pas vraiment le choix, je dois choisir $y$ pour chacune des trois parenthèses : je choisis donc $y$ dans 3 groupes de parenthèses parmi 3, il n’y a qu’une manière de le faire, ce qui signifie que $\binom{3}{3} = 1$.

Ensuite, si je veux former $xy^2$, je dois choisir $y$ dans deux groupes de parenthèses parmi 3, ce qu’on note $\binom{3}{2}$. La dernière est alors une parenthèse où on choisit $x$. Il y a trois manières de le faire : les deux à gauche, les deux à droites ou les deux extrêmes.

On peut continuer comme ça, mais j’imagine que vous avez compris le principe : à chaque fois, on choisit $k$ parenthèses parmi les $n$ parenthèses.

Cela se généralise à tous les choix de ce type : $\binom{n}{k}$ est le nombre de manières de choisir $k$ éléments parmi $n$ éléments indiscernables. $\binom{n}{k}$ se lit d’ailleurs souvent « $k$ parmi $n$ », tout simplement.

Séquences équivalentes par permutation

Une autre interprétation se fait en termes de séquences équivalentes par permutation.

On peut en effet voir le développement comme la formation de toutes les séquences possibles de la forme $a_1 a_2 \dots a_n$, avec $a_i$ correspondant à $x$ ou $y$. Quand on développe mécaniquement, sans réarranger les termes, on forme ainsi toutes les séquences possibles de cette forme.

Par exemple, pour $n=3$:

$(x+y)^3 = xxx + xxy + xyx + yxx + xyy + yxy + yyx + yyy$

Quand on procède ainsi, on laisse plein de termes qui pourraient se factoriser. On peut le faire en comptant les ordres équivalents par permutation, car c’est ce qui va former le coefficient quand on factorise.

Si chaque lettre était différente, on aurait $n!$ ordres possibles (par exemple $x_1x_2x_3$, $x_2 x_1 x_3$, etc.). Cela correspond au nombre de permutations de $n$ éléments distincts.

Ce faisant, on surestime le nombre de termes. Si on a $k$ fois $x$ dans un terme, on a en fait $k!$ ordres identiques quand on ne peut plus distinguer les différents $x$. On réduit ainsi à $\frac{n!}{k!}$ ordres différents.

Pour avoir le bon nombre de termes effectivement présents dans la somme, il faut faire de même pour $y$, qui est présent $n-k$ fois si $x$ est présent $k$ fois et donc on aboutit à la formule du coefficient binomial :

$\binom{n}{k} = \frac{n!}{k! (n-k)!}$

Que se passe-t-il si on n’a plus affaire à un binôme, mais un multinôme ?

On peut définir des coefficients multinomiaux :

$\binom{n}{k_1, k_2,\,\dots, k_m} = \frac{n!}{k_1!k_2! \dots k_m!}$

avec $k_1+k_2+\dots+k_m = n$.

Formule du multinôme de Newton

Les coefficients multinomiaux jouent le même rôle que les coefficients binomiaux dans la formule du multinôme de Newton, qui généralise celle du binôme.

On a ainsi :

$(x_1 + x_2 + \dots + x_m)^n = \sum_{k_1 + k_2 + \dots + k_m = n}\binom{n}{k_1, k_2, \, \dots, k_m}x_2^{k_1}x_2^{k_2}\dots x_m^{k_m}$

avec les coefficients multinomiaux définis comme ci-avant.

Par exemple, on peut développer $(x + y + z)^2$.

C’est bien une formule de généralisation, on retrouve la formule du binôme de Newton pour $m=2$. Les coefficients binomiaux sont en fait les $\binom{n}{k, n-k}$.

Interprétation combinatoire

Le coefficient multinomial $\binom{n}{k_1, k_2,\,\dots, k_m}$ peut s’interpréter similairement à celle du binôme de Newton, tout en généralisant.

Choix d’éléments pour former des groupes

On peut voir le coefficient multinomial comme le nombre de manières de former $m$ groupes de respectivement $k_1$, $k_2$, …, et $k_m$ éléments, choisis parmi $n$ éléments et tels que tout élément soit dans un des groupes (car la somme des $k_i$ vaut $n$).

Quand on regarde le trinôme suivant :

$(x + y + z)^3 = (x + y + z)(x + y + z)(x + y + z)$

Par exemple, pour compter le nombre d’apparitions de $xyz$, il faut voir qu’on peut soit prendre $x$ dans la première parenthèse, $y$ dans le deuxième et $z$ dans la troisième, ou alors n’importe quelle permutation de ces choix ($x$ dans la deuxième, $y$ dans la première et $z$ dans la troisième, etc.), ce qui fait 3! = 6 possibilités, qui est bien le coefficient en question.

Autre exemple, pour compter les $x^2y = x^2y^1z^0$, il faut choisir $x$ dans deux des parenthèses et $y$ dans la troisième. Comme il y a 3 manières de choisir deux parenthèses parmi 3, on trouve que le coefficient est 3, ce qui est bien correct vis-à-vis de la formule.

Ce raisonnement en termes de choix se généralise pour tout multinôme, et généralise aussi l’interprétation faite pour le binôme de Newton.

Séquences équivalentes par permutations

Similairement à l’interprétation faite pour les coefficients binomiaux, on peut faire une interprétation en termes de permutations.

C’est tellement similaire que je serais très bref : il y a $n!$ ordres possibles pour des séquences à $n$ lettres distinguables, et on divise ensuite par les $k_1!$, puis $k_2!$, etc. pour retirer les comptages multiples.

On retombe sur nos pattes !

Le jeu du morpion est très simple : chaque joueur pose un pion (croix ou cercle) à tour de rôle sur une case vide dans une grille 3×3, le premier qui aligne 3 pions en ligne, colonne ou diagonale a gagné. Si personne n’aligne de pion lorsque la grille est complète, il y a match nul.

J’appelle position l’état de la grille après chaque coup. Une manière de voir une position est comme une séquence de 9 éléments, chaque élément étant pris dans l’ensemble $\{0, 1, 2\}$ (0 pour vide, 1 pour le joueur 1 et 2 pour le joueur 2).

Tous les nombres d’éléments ne sont pas compatibles, il faut qu’ils respectent la succession des coups :

• on a d’abord 9 éléments vides (0),
• ensuite, on a 8 vides et un joueur 1,
• ensuite, on a 7 vides, un joueur 1, et un joueur 2,
• ensuite, on a 6 vides, deux joueurs 1 et un joueur 2,
• etc.

On va oublier les conditions de victoire et compter le nombre de positions qui respectent cette succession de coup. Ce sera donc un majorant du nombre réel de positions.

On peut assez naturellement interpréter chaque étape du jeu comme une sélection de cases où placer les éléments dans la grille : combien y a-t-il de manières de choisir des cases pour placer les X vides, Y joueur 1 et Z joueur 2, pour les X, Y, Z décrits ci-dessus ?

C’est une application directe du multinôme en termes de dénombrement.