Dans cette fiche explicative, nous allons apprendre comment utiliser les permutations pour résoudre des problèmes de dénombrement.
Une permutation est utilisée pour compter le nombre de façons différentes dont nous pouvons ordonner un sous-ensemble d’une collection d’éléments. Par exemple, disons que nous voulons ranger 3 lettres différentes de l’alphabet français. Premièrement, nous devons choisir 3 lettres différentes, puis nous pouvons les mettre dans un certain ordre. Cela conduit à des combinaisons telles que BJA, EMQ, XPG, etc. Nous ne pouvons pas utiliser des combinaisons comme BVB car la lettre B est répétée. D’un autre côté, BJA, AJB et JBA compteront toutes comme des combinaisons distinctes malgré le fait qu’elles utilisent les mêmes 3 lettres. Dans les permutations, l’ordre des éléments est important.
Rappelons la formule des permutations, qui représente le nombre de combinaisons distinctes d’un sous-ensemble d’une collection d’éléments.
Définition : Permutation
Étant donnés des entiers positifs ou nuls et satisfaisant , la permutation représente le nombre de façons d’ordonner objets parmi l’ensemble de objets distincts. Sa formule est donnée par
Commençons par un exemple où nous utiliserons une permutation pour compter le nombre de combinaisons distinctes.
Exemple 1: Dénombrer en utilisant des permutations
Soit et . Déterminez la valeur de , où est le nombre d’éléments dans .
Réponse
Dans cet exemple, nous voulons compter le nombre d’éléments distincts dans l’ensemble , où les éléments de l’ensemble sont les paires ordonnées des éléments de l’ensemble . On note que les paires ordonnées dans l’ensemble ne peuvent pas contenir 2 éléments identiques.
Pour former une paire ordonnée d’éléments distincts, on peut d’abord sélectionner 2 éléments de l’ensemble puis mettre les 2 éléments sélectionnés dans un certain ordre. Ainsi, le nombre de paires ordonnées est égal au nombre de façons différentes de mettre 2 éléments distincts de l’ensemble dans un certain ordre. Cela nous conduit à la notion de permutations.
Rappelons que, étant donnés des entiers positifs ou nuls et satisfaisant , la permutation représente le nombre de façons d’ordonner objets parmi un ensemble de objets distincts. Sa formule est donnée par
Puisque contient tous les entiers compris entre 7 et 16, le nombre d’éléments dans est donné par
Cela nous donne . Nous voulons mettre 2 éléments dans un certain ordre ; par conséquent, . Ensuite, le nombre de façons d’ordonner 2 éléments d’une collection de 10 éléments au total est donné par , qui est égal à . On peut calculer
Par conséquent, .
Dans les problèmes de comptage en conditions réelles, il est parfois difficile de savoir s’il faut utiliser la règle de permutation et comment l’utiliser. Pour utiliser la règle de permutation dans un scénario réel, nous devons identifier une suite d’événements dans des permutations conduisant aux mêmes résultats que le scénario donné.
Comment : Résoudre des problèmes de comptage du monde réel à l’aide de règles de permutation
Étant donné un problème de comptage du monde réel, nous pouvons construire une suite d’événements qui a le même nombre d’issues que dans le scénario réel donné en procédant comme suit :
- Sélectionner objets distincts de l’ensemble de objets distincts où
- Ordonner les objets sélectionnés
Ensuite, le nombre de résultats dans le scénario réel est donné par .
Dans l’exemple suivant, nous appliquerons la méthode ci-dessus à un problème de comptage réel en utilisant des permutations afin de compter le nombre de combinaisons possibles d’un groupe de personnes.
Exemple 2: Dénombrer en utilisant des permutations
Déterminez le nombre de façons différentes pour 4 joueurs de s’asseoir sur 11 sièges dans une rangée.
Réponse
Dans cet exemple, nous devons compter le nombre de façons différentes pour que 4 joueurs puissent s’asseoir sur 11 sièges dans une rangée. Nous pouvons résoudre ce problème en utilisant des permutations pour compter le nombre de combinaisons possibles pour les joueurs. Rappelons que, étant donnés des entiers positifs ou nuls et satisfaisant , la permutation représente le nombre de façons d’ordonner objets distincts d’un ensemble de objets distincts. En d’autres termes, nous devons trouver une suite d’événements en
- sélectionnant objets distincts de l’ensemble de objets distincts,
- ordonnant les objets sélectionnés.
Pour déterminer la disposition des sièges pour 4 joueurs, nous pouvons d’abord choisir 4 sièges parmi 11 sièges distincts. Après avoir choisi les 4 sièges à occuper, nous pouvons ordonner les 4 sièges sélectionnés. L’ordre des sièges sélectionnés peut être interprété comme suit. Disons que les 4 joueurs sont numérotés 1, 2, 3 et 4. Après avoir ordonné les 4 sièges, le joueur 1 est assis sur le premier siège, le joueur 2 est assis sur le deuxième siège, et ainsi de suite.
Nous pouvons voir que, selon cette logique, nous pouvons couvrir tous les sièges possibles pour 4 joueurs. Ainsi, le nombre de places assises différentes est donné par la permutation . Rappelons que la formule de permutation est donnée par
On remplace et , on calcule
Par conséquent, il y a 7 920 façons pour 4 joueurs de s’asseoir sur 11 sièges dans une rangée.
Identifier une suite d’événements conduisant aux mêmes issues peut être délicat. Considérons un autre exemple où nous compterons le nombre de résultats différents en utilisant cette méthode.
Exemple 3: Résoudre des problèmes impliquant des permutations et des combinaisons
Combien y a-t-il d’anagrammes uniques du mot ERROR ?
Réponse
Dans cet exemple, nous devons déterminer le nombre d’anagrammes uniques du mot ERROR. En d’autres termes, nous devons déterminer le nombre de combinaisons différents en utilisant toutes les lettres de ce mot. Si le mot avait eu cinq lettres distinctes, alors nous aurions pu appliquer la règle de la factorielle pour conclure qu’il y a combinaisons distinctes, ou anagrammes, de ce mot. Cependant, ce n’est pas le cas ici, car la lettre R apparaît trois fois dans ce mot.
Nous pouvons appliquer la règle de permutation à ce problème de comptage en identifiant une suite d’événements conduisant au même nombre d’issues. Rappelons que, étant donné des entiers positifs ou nuls et satisfaisant , la permutation représente le nombre de façons d’ordonner objets distincts de l’ensemble de objets distincts. En d’autres termes, nous devons trouver une suite d’événements en
- sélectionnant objets distincts de l’ensemble de objets distincts,
- ordonnant les objets sélectionnés.
Toute anagramme du mot ERROR doit être un mot de cinq lettres contenant un E, un O et trois R. On peut définir la suite des évènements comme suit.
Nous notons que comme les trois R ne sont pas distincts, l’ordre dans lequel ils apparaissent n’a pas d’importance. Ainsi, le nombre de permutations ne dépend que des emplacements de E et de O. Les trois emplacements restants peuvent être remplis par trois R. Comme le mot contient cinq lettres et que les deux lettres peuvent être placées dans n’importe quel ordre, nous considérons des permutations de deux lettres parmi cinq positions possibles.
Par exemple, si nous avons choisi et ordonné (5e rang, 3e rang), alors de cela résultera l’anagramme RRORE. Une anagramme ERORR correspondrait à la commande (1er rang, 3e rang). Nous pouvons voir que cette suite d’événements conduit à chaque anagramme du mot ERROR. Ainsi, le nombre de ces anagrammes est donné par la permutation . Rappelons que la formule de permutation est donnée par
On remplace et , puis on calcule
Par conséquent, il y a 20 anagrammes uniques du mot ERROR.
Nous pouvons également appliquer le principe fondamental du dénombrement (également connu sous le nom de principe multiplicatif) avec des permutations pour déterminer le nombre de résultats différents dans un scénario donné. Rappelons le principe du dénombrement.
Théorème : Principe fondamental du dénombrement
Si on a deux évènements indépendants et de sorte que le nombre d’issues possibles pour l’évènement est et le nombre d’issues possibles pour l’évènement est , le nombre total d’issues possibles distinctes de ces deux évènements mis ensemble est le produit .
Deux évènements sont indépendants si le résultat d’un évènement ne change pas le nombre d’issues possibles de l’autre évènement. De plus, le principe fondamental du dénombrement fonctionne lorsqu’il y a plus de deux évènements. En bref, nous pouvons multiplier le nombre d’issues possibles pour chaque évènement, à condition qu’ils soient indépendants.
Dans l’exemple suivant, nous appliquerons le principe fondamental du dénombrement et les permutations pour déterminer le nombre de résultats différents.
Exemple 4: Applications du principe du dénombrement (principe multiplicatif) et permutations
Une entreprise marque ses produits avec des codes commençant par 3 lettres françaises suivies de 8 chiffres non nuls. Lequel des éléments suivants représente le nombre de codes pouvant être créés sans répétition de lettre ou de chiffre ?
Réponse
Dans cet exemple, nous voulons compter le nombre de codes différents qui peuvent être créés sans répétition de lettre ou de chiffre. On nous dit qu’un code doit commencer par 3 lettres françaises et être suivi de 8 chiffres non nuls. Nous pouvons créer un code en ordonnant d’abord 3 lettres françaises, puis en ordonnant 8 chiffres non nuls pour qu’il n’y ait pas de répétition.
On rappelle le principe fondamental du dénombrement : étant donné deux évènements indépendants et de sorte que le nombre d’issues possibles pour l’évènement est et le nombre d’issues possibles pour l’évènement est , le nombre total d’issues possibles distinctes de ces deux évènements ensemble est le produit . On rappelle également que deux évènements sont indépendants si l’issue d’un évènement ne change pas le nombre d’issues possibles de l’autre évènement.
Pour appliquer le principe fondamental du dénombrement, posons l’événement correspondant aux 3 lettres françaises ordonnées et l’événement correspondant aux 8 chiffres non nuls ordonnés. Nous pouvons voir qu’un ordre spécifique de 3 lettres françaises n’affecte pas le nombre de combinaisons différentes de 8 chiffres non nuls. Par conséquent, et sont des évènements indépendants. Nous devons maintenant trouver le nombre d’issues de chaque événement séparément, puis les multiplier pour obtenir le nombre total de façons de former des codes.
Déterminons le nombre de façons différentes d’ordonner 3 lettres françaises. Rappelons que, étant donné des entiers positifs ou nuls et satisfaisant , la permutation représente le nombre de façons d’ordonner objets parmi un ensemble de objets distincts. Sa formule est donnée par
Puisqu’il y a 26 lettres dans l’alphabet français, il y a façons différentes d’ordonner 3 lettres différentes de l’alphabet français. De plus, comme il y a 9 chiffres différents de zéro, il y a façons différentes d’ordonner 8 chiffres distincts non nuls.
En appliquant le principe multiplicatif, le nombre de codes pouvant être créés sans répétition de lettre ou de chiffre est
C’est l’option D.
Considérons un autre exemple où nous devons appliquer à la fois le principe multiplicatif et les règles de la permutation pour compter différents résultats.
Exemple 5: Applications du principe du dénombrement (principe multiplicatif) et permutations
Déterminez le nombre de façons de sélectionner 2 barres de chocolat au lait en premier et 2 barres de chocolat noir ensuite dans un paquet de 10 barres de chocolat au lait et 8 barres de chocolat noir, en considérant que les éléments sont distincts, la sélection est sans remise et l’ordre de la sélection importe.
Réponse
Dans cet exemple, nous voulons compter le nombre de façons de sélectionner 2 barres de chocolat au lait et 2 barres de chocolat noir, l’ordre de sélection est important et cette sélection est sans remise.
On rappelle le principe fondamental du dénombrement : étant donné deux évènements indépendants et de sorte que le nombre d’issues possibles pour l’évènement est et le nombre d’issues possibles pour l’évènement est , le nombre total d’issues possibles distinctes de ces deux évènements ensemble est le produit . On rappelle également que deux évènements sont indépendants si l’issue d’un évènement ne change pas le nombre d’issues possibles de l’autre évènement.
Pour appliquer le principe fondamental du dénombrement, soit l’évènement correspondant à la sélection de 2 barres de chocolat au lait et l’évènement correspondant à la sélection de 2 barres de chocolat noir. Nous devons garder à l’esprit que l’ordre de sélection est important, tant pour les barres de chocolat au lait que pour les barres de chocolat noir. Nous pouvons voir qu’un ordre particulier de sélection pour 2 barres de chocolat au lait n’affecte pas le nombre de façons différentes de sélectionner 2 barres de chocolat noir. Par conséquent, et sont des évènements indépendants. Nous devons maintenant trouver le nombre de chaque événement séparément, puis les multiplier pour obtenir le nombre total de façons de sélectionner des barres de chocolat.
Déterminons d’abord le nombre de façons différentes de sélectionner 2 barres de chocolat au lait, où l’ordre de sélection est important et la sélection est sans remise. Rappelons que, étant donné des entiers positifs ou nuls et satisfaisant , la permutation représente le nombre de façons d’ordonner objets parmi un ensemble de objets distincts. Sa formule est donnée par
Puisqu’il y a 10 barres de chocolat au lait dans la boîte, il y a combinaisons ordonnées différentes pour accomplir cette tâche. On peut calculer
Ensuite, trouvons le nombre de façons différentes de sélectionner 2 barres de chocolat noir, où l’ordre de sélection est important et la sélection est sans remise. Puisqu’il y a 8 barres de chocolat noir dans le paquet, il y a combinaisons ordonnées différentes pour réaliser cette tâche. On peut calculer
En appliquant le principe multiplicatif, le nombre de résultats différents de l’événement donné est
Nous rappelons que les permutations peuvent aussi être utilisées pour décrire le nombre de combinaisons circulaires à partir d’une collection d’éléments distincts.
Théorème : Dénombrer des combinaisons circulaires
Le nombre de façons différentes d’organiser objets dans un motif circulaire d’un ensemble de objets distincts est
En particulier, le nombre de façons différentes d’ordonner objets distincts dans un motif circulaire est
Dans notre dernier exemple, nous appliquerons cette formule pour compter le nombre de combinaisons circulaires.
Exemple 6: Dénombrer des combinaisons circulaires
Vrai ou faux : Dans un magasin de fleurs, il y a 40 320 façons d’organiser 8 fleurs dans un cercle.
Réponse
Rappelons que le nombre de façons différentes d’ordonner objets distincts dans un motif circulaire est
Dans cet exemple, nous voulons trouver le nombre de combinaisons circulaires différentes pour 8 fleurs ; par conséquent, . Cela conduit à
Ce nombre est différent du nombre indiqué dans le problème. Nous pouvons voir que le nombre donné dans le problème est , qui correspond au nombre de façons différentes de disposer 8 fleurs en ligne droite. Ce nombre ne tient pas compte du fait que certaines combinaisons circulaires sont considérées comme identiques en raison de l’invariance du cercle par rotation.
Par conséquent, l’affirmation donnée est fausse.
Terminons par résumer quelques concepts importants de cette fiche explicative.
Points clés
- Étant donnés des entiers positifs ou nuls et satisfaisant , la permutation représente le nombre de façons d’ordonner objets parmi un ensemble de objets distincts. Sa formule est donnée par
- On peut résoudre un problème de dénombrement en utilisant des permutations s’il est équivalent aux évènements suivants : Pour les entiers et satisfaisant ,
- sélectionner objets distincts de l’ensemble de objets distincts,
- ordonner les objets sélectionnés.
- Le nombre de façons différentes d’organiser objets dans un motif circulaire d’un l’ensemble de objets distincts est En particulier, le nombre de façons différentes d’ordonner objets distincts dans un motif circulaire est
