analyse combinatoire

Ana, Bilal, Chloé, Diego et Emma veulent former une équipe de trois personnes. On pourrait écrire les groupes un à un, mais il faudrait éviter les doublons et n'en oublier aucun. L'analyse combinatoire remplace cette liste fragile par un raisonnement de dénombrement. Elle demande d'abord si l'ordre compte et si un même objet peut être repris. Ici, l'équipe Ana-Bilal-Chloé reste la même quel que soit l'ordre des trois noms : parmi les cinq personnes, il existe exactement dix équipes différentes.

L'analyse combinatoire étudie des configurations formées à partir d'un ensemble fini. Elle sert à les compter, à les énumérer sans oubli ni doublon et, parfois, à prouver qu'au moins une configuration vérifiant une propriété existe. Avant de calculer, il faut préciser le nombre d'objets disponibles, le nombre d'objets retenus, l'importance éventuelle de leur ordre et l'autorisation ou non des répétitions.

Notons n le nombre d'objets distincts disponibles et k le nombre de places à remplir. Sans répétition, une permutation ordonne les n objets, un arrangement ordonne k objets choisis parmi n, tandis qu'une combinaison choisit k objets sans tenir compte de l'ordre. Leurs nombres sont respectivement $n!n!$, $\frac{n!}{(n-k)!}\backslash frac\{n!\}\{(n-k)!\}$ et $\left(\genfrac{}{}{0px}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}\backslash binom\{n\}\{k\}=\backslash frac\{n!\}\{k!(n-k)!\}$, pour des entiers tels que $0\le k\le n0\; \backslash leq\; k\; \backslash leq\; n$.

Avec répétition, le même objet peut occuper plusieurs places : les formules changent et dépendent encore du rôle de l'ordre. Ces techniques interviennent notamment dans le calcul des probabilités, où l'on recense les issues avant de comparer les cas favorables à l'ensemble des cas possibles. Les coefficients $\left(\genfrac{}{}{0px}{}{n}{k}\right)\backslash binom\{n\}\{k\}$ apparaissent aussi dans la formule du binôme de Newton.

Ana, Bilal, Chloé, Diego et Emma forment une équipe de trois personnes. Les données sont les suivantes : cinq personnes distinctes, trois personnes à choisir, aucune répétition possible et aucun rôle particulier dans l'équipe. L'ordre des noms ne compte donc pas.

1. On reconnaît une combinaison : n vaut 5 et k vaut 3.
2. On applique la formule $\left(\genfrac{}{}{0px}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}\backslash binom\{n\}\{k\}=\backslash frac\{n!\}\{k!(n-k)!\}$.
3. On remplace les lettres par les données : $\left(\genfrac{}{}{0px}{}{5}{3}\right)=\frac{5!}{3!2!}\backslash binom\{5\}\{3\}=\backslash frac\{5!\}\{3!2!\}$.

4. Comme $5!=5\times 4\times 3\times 2\times 15!=5\backslash times4\backslash times3\backslash times2\backslash times1$, les facteurs communs se simplifient : $\left(\genfrac{}{}{0px}{}{5}{3}\right)=\frac{5\times 4}{2\times 1}=10\backslash binom\{5\}\{3\}=\backslash frac\{5\backslash times4\}\{2\backslash times1\}=10$. Il existe donc exactement dix équipes de trois personnes. La figure recense ces dix choix en marquant trois positions sur cinq pour chacun.

Un contrôle indépendant consiste à compter les couples complémentaires : choisir les trois membres de l'équipe revient à choisir les deux personnes qui restent. On obtient bien $\left(\genfrac{}{}{0px}{}{5}{3}\right)=\left(\genfrac{}{}{0px}{}{5}{2}\right)=10\backslash binom\{5\}\{3\}=\backslash binom\{5\}\{2\}=10$.

Pour former l'équipe d'Ana, Bilal, Chloé, Diego et Emma, on emploie une combinaison parce que seuls les membres retenus comptent. Si les trois personnes recevaient des rôles distincts de présidence, trésorerie et secrétariat, un arrangement conviendrait : échanger deux rôles produirait une autre attribution.

En probabilités, on dénombre les issues lorsque celles-ci peuvent être décrites par des configurations finies. Le rapport « cas favorables sur cas possibles » ne s'applique directement que si les issues comptées sont équiprobables ; sinon, il faut attribuer leurs probabilités propres.

En informatique, un dénombrement peut estimer le nombre de configurations qu'un programme devrait explorer. Une énumération exhaustive est utile si ce nombre reste praticable ; lorsque l'espace devient trop grand, il faut exploiter la structure du problème plutôt que générer toutes les possibilités.

Une combinaison ne tient pas compte de l'ordre. Dans l'équipe de trois personnes, Ana-Bilal-Chloé et Chloé-Ana-Bilal désignent le même groupe.

Un arrangement retient une partie des objets et tient compte de leur ordre. Attribuer trois rôles distincts parmi les cinq personnes donne plusieurs résultats dès que les mêmes personnes échangent leurs rôles.

Une permutation ordonne tous les objets disponibles. Placer les cinq personnes sur cinq sièges numérotés relève donc des permutations, et non du choix d'une équipe de trois. Le test décisif est double : utilise-t-on tous les objets, et l'ordre change-t-il la configuration ?

Le premier piège consiste à multiplier les choix sans vérifier si leur ordre crée des configurations distinctes. Pour l'équipe de trois personnes, le calcul $5\times 4\times 3=605\backslash times4\backslash times3=60$ compte chaque équipe six fois, une fois pour chacun des $3!=63!=6$ ordres de ses membres. Il faut donc diviser par 6 lorsque l'ordre ne compte pas.

La répétition doit être décidée avant le calcul. Une personne ne peut pas occuper deux places dans la même équipe, mais un code peut réutiliser un même symbole si la règle l'autorise. Appliquer une formule « sans répétition » au second cas supprime des configurations valides.

Aux valeurs charnières, il existe une seule manière de ne choisir aucun objet et une seule manière de choisir tous les objets : $\left(\genfrac{}{}{0px}{}{n}{0}\right)=\left(\genfrac{}{}{0px}{}{n}{n}\right)=1\backslash binom\{n\}\{0\}=\backslash binom\{n\}\{n\}=1$. En revanche, sans répétition, choisir plus de personnes qu'il n'en existe est impossible : pour $k>nk>n$, le nombre de choix vaut 0.

Enfin, compter correctement les issues ne les rend pas automatiquement équiprobables. Avant de transformer un dénombrement en probabilité, il faut vérifier que le modèle attribue bien la même probabilité à chaque issue élémentaire recensée.

L'article Les multiples facettes du dénombrement élargit les stratégies de comptage au-delà des trois formules élémentaires.

La fiche binôme de Newton montre où réapparaissent les coefficients de combinaison dans le développement d'une puissance.

La fiche arrangement approfondit le cas où l'on choisit une partie des objets tout en conservant leur ordre.

L'article Cheminement combinatoire propose un prolongement consacré aux raisonnements et parcours combinatoires.