Licence CC BY

Coefficients binomiaux, multinomiaux et dénombrement

Un lien entre algèbre et combinatoire

Si vous avez fait un peu de mathématiques, vous connaissez peut-être les coefficients binomiaux, notés (nk)\binom{n}{k}, pour deux entiers naturels nn et kk, qui apparaissent dans la formule du binôme de Newton. Il existe aussi une généralisation assez directe de ces coefficients : les coefficients multinomiaux qui apparaissent dans la formule du multinôme de Newton.

Ces deux familles de coefficients sont utilisés pour faire de la combinatoire (plus précisément du dénombrement). Ce tutoriel présente brièvement les coefficients, puis explique le lien entre leur définition habituelle et leur interprétation pour le dénombrement, avant de conclure sur un exemple simple : un majorant du nombre de positions au morpion.

Une familiarité avec les coefficients binomiaux et le binôme de Newton est un prérequis important pour suivre aisément ce tutoriel, même si le contenu devrait rester accessible avec quelques efforts dans le cas contraire.

Coefficients binomiaux, binôme de Newton et dénombrement

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

On peut les exprimer avec une formule relativement simple :

(nk)=n!k!(nk)!\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(x + y)^n avec nn un entier naturel.

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

(x+y)2=x2+2xy+y2=(20)x2+(21)xy+(22)y2(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=3n = 3, on peut vérifier que :

(x+y)3=x3+3x2y+3xy2+y3=(30)x3+(31)x2y+(32)xy2+(33)y3(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=k=0n(nk)xkynk(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 xx ou yy pour chaque parenthèse. Combien de fois je veux voir xx dans mon monôme, et combien de fois yy ? De combien de manière puis-je choisir mes parenthèses pour que ça arrive ?

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

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

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

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

Ensuite, si je veux former xy2xy^2, je dois choisir yy dans deux groupes de parenthèses parmi 3, ce qu’on note (32)\binom{3}{2}. La dernière est alors une parenthèse où on choisit xx. 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 kk parenthèses parmi les nn parenthèses.

Cela se généralise à tous les choix de ce type : (nk)\binom{n}{k} est le nombre de manières de choisir kk éléments parmi nn éléments indiscernables. (nk)\binom{n}{k} se lit d’ailleurs souvent « kk parmi nn », 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 a1a2ana_1 a_2 \dots a_n, avec aia_i correspondant à xx ou yy. 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=3n=3:

(x+y)3=xxx+xxy+xyx+yxx+xyy+yxy+yyx+yyy(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!n! ordres possibles (par exemple x1x2x3x_1x_2x_3, x2x1x3x_2 x_1 x_3, etc.). Cela correspond au nombre de permutations de nn éléments distincts.

Ce faisant, on surestime le nombre de termes. Si on a kk fois xx dans un terme, on a en fait k!k! ordres identiques quand on ne peut plus distinguer les différents xx. On réduit ainsi à n!k!\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 yy, qui est présent nkn-k fois si xx est présent kk fois et donc on aboutit à la formule du coefficient binomial :

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

Coefficients multinomiaux, multinômes et dénombrement

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 :

(nk1,k2,,km)=n!k1!k2!km!\binom{n}{k_1, k_2,\,\dots, k_m} = \frac{n!}{k_1!k_2! \dots k_m!}

avec k1+k2++km=nk_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 :

(x1+x2++xm)n=k1+k2++km=n(nk1,k2,,km)x2k1x2k2xmkm(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(x + y + z)^2.

(x+y+z)2=(22,0,0)x2+(21,1,0)xy+(21,0,1)xz+(20,2,0)y2+(20,1,1)yz+(n0,0,2)z2=x2+2xy+2xz+y2+2yz+z2\begin{aligned} (x + y + z)^2 &= \binom{2}{2, 0, 0} x^2 + \binom{2}{1, 1, 0} x y + \binom{2}{1, 0, 1} x z + \binom{2}{0, 2, 0} y^2 + \binom{2}{0, 1, 1} y z + \binom{n}{0, 0, 2} z^2 \\ &= x^2 + 2 x y + 2 x z + y^2 + 2 y z + z^2 \end{aligned}

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

Interprétation combinatoire

Le coefficient multinomial (nk1,k2,,km)\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 mm groupes de respectivement k1k_1, k2k_2, …, et kmk_m éléments, choisis parmi nn éléments et tels que tout élément soit dans un des groupes (car la somme des kik_i vaut nn).

Quand on regarde le trinôme suivant :

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

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

Autre exemple pour compter les x2y=x2y1z0x^2y = x^2y^1z^0, il faut choisir xx dans deux des parenthèses et yy 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!n! ordres possibles pour des séquences à nn lettres distinguables, et on divise ensuite par les k1!k_1!, puis k2!k_2!, etc. pour retirer les comptages multiples.

On retombe sur nos pattes !

Exemple : calcul d'un majorant pour le nombre de positions au morpion

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, 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 joueur 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 places les X vides, Y joueur 1 et Z joueur 2, pour les X, Y, Z décrit ci-dessus ?

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

Vide Jetons 1 Jetons 2 Formule du majorant Valeur du majorant
9 0 0 (99,0,0)\binom{9}{9, 0, 0} 1
8 1 0 (98,1,0)\binom{9}{8, 1, 0} 9
7 1 1 (97,1,1)\binom{9}{7, 1, 1} 72
6 2 1 (96,2,1)\binom{9}{6, 2, 1} 252
5 2 2 (95,2,2)\binom{9}{5, 2, 2} 756
4 3 2 (94,3,2)\binom{9}{4, 3, 2} 1260
3 3 3 (93,3,3)\binom{9}{3, 3, 3} 1680
2 4 3 (92,4,3)\binom{9}{2, 4, 3} 1260
1 4 4 (91,4,4)\binom{9}{1, 4, 4} 630
0 5 4 (90,5,4)\binom{9}{0, 5, 4} 126
Total - - - 6046

Et voilà, j’espère que vous avez maintenant une meilleure compréhension des coefficients binomiaux et multinomiaux en termes de combinatoire !

Références

Aucun commentaire

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte