Combinatoire/Combinaisons sans répétition

Avant de commencer...

Il est important de comprendre les arrangements sans répétition et les permutations sans répétition et d’avoir fait une partie des exercices associés à ces chapitres (ici et là).

Début de la boite de navigation du chapitre

Une combinaison correspond au choix d'un groupe de k objets parmi un groupe de n objets. Contrairement aux arrangements, l’ordre dans lequel les objets sont pris n'a pas d'importance. Par exemple, choisir 3 députés parmi un groupe de candidats est plutôt une combinaison qu'un arrangement car il n'y a aucun ordre explicite ou implicite dans ce choix. Un député est un député et il n'y a pas de raison de distinguer les trois postes. En revanche, si l’on doit choisir un ministre de l'agriculture, un ministre de l'éducation et un ministre des mathématiques, il s'agit d'un arrangement parce que ces trois postes sont différents.

fin de la boite de navigation du chapitre

Pour fixer les idées, voici d'autres exemples qui illustrent la différence entre arrangement et combinaison. Les deux premiers concernent des arrangements et des combinaisons sans répétition, les deux derniers avec répétition :

Exemples

Combinaison	Arrangement
Choix de sept joueurs pour une équipe de handball.	Choix de sept joueurs pour une équipe de handball, avec leurs postes.
Choix de quatre personnes pour une corvée.	Choix de quatre personnes pour faire quatre corvées différentes.
Répartitions de 8 objets identiques dans 3 tiroirs différents.	Répartitions de 8 objets différents dans 3 tiroirs différents.
Choix de 3 docteurs honoris causa	Remise de 3 récompenses distinctes

Il est évidemment sous-entendu que ces choix se font parmi un ensemble fini de n possibilités.

Introduction

Définition

Une combinaison est donc le choix d'un sous-ensemble de k objets parmi n objets. Ici, nous considérons uniquement le cas des combinaisons sans répétition, ce qui signifie qu'aucun objet ne peut apparaître plus d'une fois.

Comme dans le cas des arrangements sans répétition, k doit forcément être plus petit que n, pour les mêmes raisons.

Le tableau présent en introduction le montre : la plupart de temps, la même situation peut être envisagée à la fois comme une combinaison et comme un arrangement selon la façon de voir un problème. Par exemple, le choix de joueurs pour constituer une équipe de handball peut être considéré comme une combinaison si on se contente de choisir les 7 joueurs, mais comme un arrangement si on veut en plus leur attribuer un poste (cela marche avec n’importe quel sport d'équipe). Plusieurs arrangements peuvent correspondre à une seule combinaison ; dans notre exemple, c’est le cas de deux équipes constituées des mêmes joueurs mais jouant à des postes différents.

Exemple introductif

Encore une fois, nous allons revenir à nos sempiternels cinq chevaux. Cette fois-ci, notre parieur invétéré veut déterminer les 3 premiers de la course sans deviner leur ordre. Combien y a-t-il de possibilités ?

Déjà, cela va sans dire mais cela va mieux en le disant, il faut noter que la méthode utilisée pour les permutations sans répétition et les arrangements sans répétition ne marche plus. Dans ces cas-ci, on pouvait envisager chacun des k choix séparément et successivement, déterminer le nombre de possibilités à chaque choix et ensuite calculer le résultat final en multipliant ces nombres. Mais cela n'est plus possible car dans les cas des combinaisons, l’ordre des choix n'a plus d'importance. Nous pouvons voir sur l'arbre des décisions repris du chapitre 3, qui représentait ce raisonnement, que plusieurs branches finales correspondent à la même combinaison.

Pour résoudre notre problème, nous allons envisager le problème des arrangements d'un autre problème. Oui, j’ai bien écrit des arrangements ; nous savons déjà qu’il y en a 60, mais cela nous permettra d'y voir plus clair. Le choix d'un podium peut en effet être décrit de cette manière :

• d'abord, nous choisissons les trois chevaux sur le podium (ce qui correspond à choisir une combinaison de chevaux) ;
• ensuite, nous les classons pour obtenir tous les arrangements possibles.

Avec cette méthode, on peut être sûr que :

• tous les arrangements sont comptés ;
• aucun arrangement n'est pris deux fois. En effet, à chaque arrangement correspond une seule combinaison, et une seule classification.

La première des deux étapes est celle que nous essayons de comprendre. En revanche, la seconde vous est bien connue depuis longtemps : il s'agit d'une bête permutation sans répétition. Il s'agit en effet de classer 3 chevaux. Il y a donc six permutations pour chaque combinaison. Comme il y a 60 arrangements, on en déduit qu’il doit y avoir 10 combinaisons possibles.

Conclusion

Nous obtenons donc finalement :

${\text{Nombre d'arrangements}}={\text{Nombre de combinaisons}}\times {\text{Nombres de permutations}}$.

Ou encore :

Début d’un théorème

Théorème

Le nombre de combinaisons (sans répétition) de k éléments pris dans un ensemble à n éléments est :

${\binom {n}{k}}={\frac {A_{n}^{k}}{k!}}={\begin{cases}0&{\text{ si }}k>n,\\{\frac {n!}{k!\,(n-k)!}}&{\text{ si }}0\leq k\leq n.\end{cases}}$

Fin du théorème

Démonstration

On calcule le nombre d'arrangements de k éléments pris dans l'ensemble à n éléments, de deux façons différentes.

• Il existe $A_{n}^{k}$ listes ordonnées de k éléments pris parmi n.
• Mais on peut aussi choisir d'abord le sous-ensemble des k éléments parmi n ($n \choose k$ choix possibles) puis ordonner l'ensemble pour constituer une liste ($k!$ ordres possibles). Il existe donc ${n \choose k}\times k!$ listes ordonnées de k éléments pris parmi n.

En confrontant ces deux expressions, on obtient l'expression annoncée pour $n \choose k$.

 

Remarque

Les coefficients binomiaux sont reliés par la formule de Pascal et interviennent dans la formule du binôme : voir Sommation/Formule du binôme.