Expliqué : Permutations vs. Combinaisons
Ouais, je parle de ces boutons mystiques sur votre calculatrice (nCr et nPr) sur lesquels vous appuyez gracieusement et qui crachent la bonne réponse. Magique.
.
Les deux concepts sont assez simples donc cela ne devrait pas prendre trop de temps à expliquer. Je vais expliquer les différences ; quand les utiliser ; et ce que calcule exactement votre calculatrice lorsque vous les saisissez (l’équation).
Donc, la meilleure façon d’illustrer leur cas d’utilisation est à travers deux exemples :
Exemple 1 : Il y a 10 athlètes qui participent à une course où le gagnant de la première place recevra une médaille d’or, le gagnant de la deuxième place recevra une médaille d’argent et le gagnant de la troisième place recevra une médaille de bronze. S’ils gagnent une médaille, ils monteront sur le podium à plusieurs niveaux. Les autres ne reçoivent rien… pas même un trophée de participation… parce que c’est l’Amérique… et si vous n’êtes pas le premier, vous êtes le dernier.
Question 1 : combien de possibilités y a-t-il pour le podium ?
Question 2 : combien de possibilités y a-t-il pour qui gagne une médaille ?
Quand utiliser nPr et quand utiliser nCr ?
Quand les utiliser :
les deux questions peuvent paraître similaires, mais il existe une différence fondamentale qui va dicter l’équation à utiliser.
La question 1 (podium) tient compte de la pertinence de l’ordre :
Si Bob, Lacy et Sarah sont sur le podium, Bob arrivant en premier n’est pas la même chose que Bob arrivant en deuxième. Il s’agit d’un résultat différent. L’ordre est pertinent, vous utiliserez donc nPr.
nPr (permutations) est utilisé lorsque l’ordre est important.
La question 2 ne tient pas compte de l’ordre du podium, elle demande simplement qui gagne une médaille. La question ne délimite pas entre or, argent ou bronze, ce sont toutes des médailles et c’est tout ce qui compte. Lorsque l’ordre n’a pas d’importance, vous utilisez nCr.
nCr (combinaisons) est utilisé lorsque l’ordre n’a pas d’importance.
Ce qu’ils font réellement :
Maintenant que vous comprenez, je l’espère, quand utiliser lequel, passons à ce qu’ils font réellement.
nPr
Comme mentionné, nPr trouve toutes les permutations qui existent dans un ensemble donné pour un sous-ensemble donné. Dans notre exemple particulier, il va chercher combien de résultats différents peuvent résulter de la course qui aboutirait à une permutation de podium (ordre différent).
.
Dans notre course :
Ok, nous avons donc décomposé un peu plus le bouton magique, mais vous vous demandez peut-être maintenant… pourquoi cette équation, et pourquoi tous ces chiffres me crient dessus ! !!! – que signifie le !
! ou autrement connu sous le nom de factorielle est simplement un moyen pratique d’exprimer une série de multiplication.
En particulier :
Illustrons en reprenant notre exemple :
n = 15 (car il y a 15 athlètes)
n ! = 15 ! = 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
C’est ce que calcule votre calculatrice lorsque vous saisissez le bouton !
15 ! = 1 307 674 368 000
Ce nombre représente le nombre maximum d’ordres différents qui peuvent se produire à partir d’une liste. Notre liste compte 15 coureurs, et il y a 1 307 674 368 000 façons différentes d’organiser leur placement. Le nombre multiplié est décroissant car au fur et à mesure qu’un chiffre est placé, cette place est maintenant occupée.
Si le coureur 1 se place en 15ème position, il ne reste que 14 autres places à atterrir pour tous les coureurs restants, si le coureur 2 se place en 14ème position, il ne reste plus que 13 places pour tous les coureurs. Comme la plupart des choses, il est plus facile de l’expliquer en mettant les chiffres à l’échelle :
Exemple plus simple (vous pouvez sauter si vous saisissez déjà) :
Disons qu’il y a quatre sièges disponibles, et 4 amis qui cherchent à s’asseoir. Pour le premier siège, il y a quatre issues potentielles (n’importe lequel des quatre amis peut l’attraper), une fois qu’il a été pris, le deuxième siège n’a que trois issues potentielles différentes (n’importe lequel des 3 amis non assis peut l’attraper), le troisième siège n’a que deux possibilités, et le dernier siège par défaut n’a qu’une seule option – le pauvre bougre qui ne s’est pas encore assis.
En conséquence, mathématiquement, il y a 4 x 3 x 2 x 1 issues potentielles.
Si la course demandait simplement de combien de façons différentes l’ordre de la course peut changer, on n’utiliserait pas nPr, on utiliserait factorielle( !)… mais ce n’est pas le cas… on demande combien de fois le podium peut changer ce qui regarde spécifiquement les trois premiers coureurs, pas tous. Par conséquent, nous n’utilisons pas la factorielle. La factorielle a un champ d’application trop large.
Parce qu’elle est trop large, nous devons la réduire. Nous n’examinons que les trois premières positions, et non les 12 autres. Dit autrement, si l’ordre des trois premières change, alors on considère qu’il s’agit d’une nouvelle permutation, mais si l’ordre des trois premières reste le même, (même si l’ordre des 12 autres change) alors on ne considère pas qu’il s’agit d’une nouvelle permutation.
Parce que 12 positions ne sont pas pertinentes, nous devons réduire leur importance dans l’équation.
C’est pourquoi nous obtenons
.
La façon la plus simple de supprimer la pertinence des 12 positions restantes est de diviser le nombre de possibilités complet( !) par le nombre de possibilités pour les positions non pertinentes. Comme indiqué précédemment, il existe 12 positions non pertinentes pour notre podium.
donc 15 ! divisé par (15 -3) !
Cela équivaut à une écriture de sortie :
.
ce qui équivaut à 15 x 14 x 13 car tous les autres chiffres s’annulent.
15 x 14 x 13 également = 2730
Maintenant, regardons nCr :
Ouf, cela a pris beaucoup de temps pour passer les permutations, ce tour devrait être plus rapide car j’ai déjà parlé des factorielles maintenant.
Comme mentionné, nCr, c’est trouver toutes les combinaisons qui existent dans un ensemble donné pour un sous-ensemble donné lorsque l’ordre n’a pas d’importance. Dans notre exemple, il cherche le nombre de combinaisons différentes qui peuvent se produire pour gagner la médaille (c’est-à-dire. finir dans les trois premiers)
.
Maintenant, dès le départ, vous remarquerez qu’il y a moins de combinaisons que de permutations (455 < 2730). Cela est logique car les combinaisons marquent ABC et ACB comme étant identiques, alors que la permutation différencie les deux. Examinons ce que fait votre calculatrice lorsque vous appuyez sur le bouton.
Maintenant la première chose que vous devriez remarquer est que l’équation est assez similaire à l’équation des permutations, sauf qu’il y a plus de choses ajoutées au dénominateur (c’est k !(n-r) !, et pas seulement (n-r)!
Selon l’énoncé précédent, cela a du sens, car ajouter plus au dénominateur donnera un résultat plus petit (par ex. 10/2) < 10/5), et nous avons établi que les combinaisons seront plus petites que les permutations.
Si vous avez fait attention/mon écriture a un sens, nous devrions déjà savoir pourquoi vous ajoutez (n-r) ! à l’équation. Si ce n’est pas le cas, faites ctrl/commande +f « portée trop large » et relisez ce passage.
Nous ajoutons r ! au dénominateur parce qu’il y a r ! façons que les médaillés restent les mêmes, alors que leur ordre change.
Pour chaque ensemble de trois médaillés, on peut les mélanger 3 ! fois pour créer une nouvelle permutation (3 ! = 6 fois)… mais nous ne nous soucions pas de cette permutation. Ces 6 permutations différentes ne sont en fait qu’une seule combinaison d’athlètes, et nous voulons donc l’extraire de notre réponse. La façon la plus simple de le faire est de l’ajouter au dénominateur pour qu’elle soit retirée du numérateur.
.
Ce n’est pas un hasard si 455 x 3 ! = 2730.
En tout cas, c’est tout ce que j’ai pour aujourd’hui. J’espère que cela a du sens.
Ciao,