Leçons de niveau 13

Combinatoire/Combinaisons sans répétition

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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 ).

Début de la boite de navigation du chapitre
Combinaisons sans répétition
Icône de la faculté
Chapitre no 7
Leçon : Combinatoire
Chap. préc. :Permutations avec répétition
Chap. suiv. :Combinaisons avec répétition

Exercices :

Combinaisons
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Combinatoire : Combinaisons sans répétition
Combinatoire/Combinaisons sans répétition
 », n'a pu être restituée correctement ci-dessus.

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.

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[modifier | modifier le wikicode]

Définition[modifier | modifier le wikicode]

Wikipédia possède un article à propos de « Combinaison (mathématiques) ».

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Nous obtenons donc finalement :

.

Ou encore :

Début d’un théorème


Fin du théorème


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.