Permutations and Combinations

# Permutations and Combinations ## Objectifs et prérequis Ce chapitre vise à maîtriser les principes fondamentaux du comptage, à comprendre la notation factorielle, à distinguer les permutations des combinaisons, à appliquer ces concepts dans divers contextes (avec répétition, objets identiques, arrangements circulaires, restrictions), et à résoudre des problèmes concrets liés au choix et à l'arrangement d'objets. Les prérequis incluent une bonne maîtrise des opérations arithmétiques de base, la compréhension des ensembles et des sous-ensembles, ainsi que la capacité à raisonner de manière logique et systématique. ## Introduction Les permutations et les combinaisons sont des outils essentiels en mathématiques discrètes, utilisés pour compter le nombre de façons d'arranger ou de sélectionner des objets sous diverses contraintes. Elles trouvent des applications dans de nombreux domaines : probabilités, informatique, génétique, cryptographie, et même dans la vie quotidienne (organisation d'événements, création de mots de passe, etc.). Ce chapitre développe progressivement ces concepts, en partant du principe fondamental de comptage jusqu'aux cas les plus complexes avec restrictions. ## I. Fundamental counting principles ### Définition et principe de multiplication Le principe fondamental de comptage stipule qu si une tâche peut être décomposée en une séquence d'étapes indépendantes, et que la première étape peut être réalisée de $m$ façons, la deuxième de $n$ façons, et ainsi de suite, alors le nombre total de façons d'accomplir la tâche est le produit $m \times n \times \cdots$. > **À retenir** : Principe de multiplication : Si une tâche consiste en $k$ étapes successives, où la $i$-ième étape peut être réalisée de $n_i$ façons indépendamment des autres, alors le nombre total de façons d'accomplir la tâche est $\prod_{i=1}^{k} n_i$. ### Principe d'addition Si une tâche peut être réalisée de deux manières mutuellement exclusives (c'est-à-dire qu'on ne peut pas les faire simultanément), et que la première manière peut être réalisée de $m$ façons et la seconde de $n$ façons, alors le nombre total de façons d'accomplir la tâche est $m + n$. > **À retenir** : Principe d'addition : Si une tâche peut être accomplie de $k$ façons mutuellement exclusives, où la $j$-ième façon peut être réalisée de $n_j$ façons, alors le nombre total de façons est $\sum_{j=1}^{k} n_j$. ### Exemple résolu **Exemple 1** : Un étudiant doit choisir un livre de mathématiques parmi 5, un livre de physique parmi 3, et un livre de chimie parmi 4. Combien de façons différentes peut-il choisir un livre de chaque matière ? **Solution** : Choix du livre de mathématiques : 5 façons Choix du livre de physique : 3 façons Choix du livre de chimie : 4 façons Comme les choix sont indépendants, on applique le principe de multiplication : $5 \times 3 \times 4 = 60$ Il y a donc 60 façons de choisir un livre de chaque matière. **Exemple 2** : Dans une classe, il y a 12 garçons et 15 filles. Combien de façons y a-t-il de choisir un élève pour représenter la classe, si le représentant doit être soit un garçon soit une fille ? **Solution** : Choix d'un garçon : 12 façons Choix d'une fille : 15 façons Comme les deux cas sont mutuellement exclusifs, on applique le principe d'addition : $12 + 15 = 27$ Il y a donc 27 façons de choisir un représentant. ### Exercices d'application corrigés **Exercice 1** : Un restaurant propose 6 entrées, 8 plats principaux et 5 desserts. Combien de menus différents (entrée + plat + dessert) peut-on composer ? **Solution** : $6 \times 8 \times 5 = 240$ Réponse : 240 menus. **Exercice 2** : Un code à 4 chiffres est formé en utilisant les chiffres de 0 à 9, avec répétition autorisée. Combien de tels codes existent-ils ? **Solution** : Chaque chiffre peut être choisi de 10 façons (0 à 9), et il y a 4 positions indépendantes : $10 \times 10 \times 10 \times 10 = 10^4 = 10\,000$ Réponse : 10 000 codes. **Exercice 3** : Un comité de 3 personnes doit être formé à partir d'un groupe de 10 personnes. Si le comité doit inclure soit le président soit le secrétaire (mais pas nécessairement les deux), combien de comités sont possibles ? (On suppose que le président et le secrétaire sont deux personnes distinctes.) **Solution** : On utilise le principe d'addition en considérant deux cas mutuellement exclusifs : Cas 1 : Le président est inclus, le secrétaire peut être inclus ou non. Cas 2 : Le président n'est pas inclus, mais le secrétaire doit l'être (pour éviter le double comptage quand les deux sont inclus). Mais une meilleure approche : nombre total de comités incluant le président OU le secrétaire = (comités avec président) + (comités avec secrétaire) - (comités avec les deux) Comités avec président : on choisit 2 autres personnes parmi les 9 restantes : $\binom{9}{2} = 36$ Comités avec secrétaire : de même, $\binom{9}{2} = 36$ Comités avec les deux : on choisit 1 autre personne parmi les 8 restantes : $\binom{8}{1} = 8$ Donc : $36 + 36 - 8 = 64$ Réponse : 64 comités. ## II. Factorial notation ! and its definition ### Définition du factoriel Le factoriel d'un entier naturel $n$, noté $n!$, est le produit de tous les entiers positifs de 1 à $n$. Par convention, $0! = 1$. > **À retenir** : Définition du factoriel : Pour tout entier naturel $n$, $n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$, avec $0! = 1$. ### Propriétés du factoriel - $n! = n \times (n-1)!$ pour $n \geq 1$ - $n!$ croît très rapidement avec $n$ - Le factoriel est défini uniquement pour les entiers non négatifs ### Exemple résolu **Exemple 3** : Calculer $5!$, $7!$ et $0!$. **Solution** : $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ $7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040$ $0! = 1$ (par définition) ### Exercices d'application corrigés **Exercice 4** : Calculer $6!$ et $4! \times 3!$. **Solution** : $6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ $4! = 24$, $3! = 6$, donc $4! \times 3! = 24 \times 6 = 144$ Réponse : $6! = 720$, $4! \times 3! = 144$ **Exercice 5** : Simplifier $\frac{8!}{6!}$. **Solution** : $\frac{8!}{6!} = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 8 \times 7 = 56$ Réponse : 56 **Exercice 6** : Trouver $n$ si $n! = 120$. **Solution** : On teste les valeurs : $1! = 1$ $2! = 2$ $3! = 6$ $4! = 24$ $5! = 120$ Donc $n = 5$ Réponse : $n = 5$ ## III. Definition and Types of permutation ### Définition de permutation Une permutation est un arrangement ordonné d'objets. Lorsque l'ordre compte, on parle de permutation. > **À retenir** : Une permutation est un arrangement dans lequel l'ordre des éléments est important. ### Types de permutations 1. **Permutation sans répétition** : Tous les objets sont distincts, et aucun objet n'est utilisé plus qu'une fois. 2. **Permutation avec répétition** : Certains objets peuvent être identiques, ou la répétition est autorisée dans le choix. 3. **Permutation circulaire** : Les objets sont disposés autour d'un cercle, où les rotations sont considérées comme identiques. ### Exemple résolu **Exemple 4** : Combien de façons y a-t-il d'arranger 4 livres différents sur une étagère ? **Solution** : Comme tous les livres sont distincts et l'ordre compte, on utilise la permutation sans répétition : Nombre de permutations de $n$ objets distincts pris $n$ à la fois : $n!$ Ici, $n = 4$, donc $4! = 24$ Réponse : 24 façons. ### Exercices d'application corrigés **Exercice 7** : Combien de mots de 3 lettres peuvent être formés à partir des lettres du mot "CAT" si aucune lettre ne peut être répétée ? **Solution** : Lettres distinctes : C, A, T (3 lettres) On veut des arrangements de 3 lettres prises 3 à la fois, sans répétition : $3! = 6$ Les mots possibles : CAT, CTA, ACT, ATC, TCA, TAC Réponse : 6 mots. **Exercice 8** : Combien de façons y a-t-il d'arranger 5 étudiants différents en ligne pour une photo ? **Solution** : $5! = 120$ Réponse : 120 façons. ## IV. Permutation with Repetition ### Définition Lorsque certains objets sont identiques, le nombre de permutations distinctes est réduit car l'échange d'objets identiques ne produit pas un nouvel arrangement. > **À retenir** : Le nombre de permutations distinctes de $n$ objets où il y a $n_1$ objets identiques d'un type, $n_2$ d'un autre, ..., $n_k$ d'un $k$-ième type (avec $n_1 + n_2 + \cdots + n_k = n$) est donné par : $$\frac{n!}{n_1! \cdot n_2! \cdot \cdots \cdot n_k!}$$ ### Exemple résolu **Exemple 5** : Combien de permutations distinctes peut-on former avec les lettres du mot "BANANA" ? **Solution** : Le mot "BANANA" comporte 6 lettres : - B : 1 fois - A : 3 fois - N : 2 fois Donc : $n = 6$, $n_A = 3$, $n_N = 2$, $n_B = 1$ Nombre de permutations distinctes : $$\frac{6!}{3! \cdot 2! \cdot 1!} = \frac{720}{6 \times 2 \times 1} = \frac{720}{12} = 60$$ Réponse : 60 permutations distinctes. ### Exercices d'application corrigés **Exercice 9** : Combien de permutations distinctes peut-on former avec les lettres du mot "MISSISSIPPI" ? **Solution** : "MISSISSIPPI" comporte 11 lettres : - M : 1 - I : 4 - S : 4 - P : 2 Donc : $$\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = \frac{39916800}{1152} = 34650$$ Réponse : 34 650 permutations distinctes. **Exercice 10** : Combien de nombres de 5 chiffres peuvent être formés avec les chiffres 1, 1, 2, 2, 3 (chacun utilisé exactement une fois) ? **Solution** : On a 5 chiffres : deux 1, deux 2, un 3 Nombre de permutations distinctes : $$\frac{5!}{2! \cdot 2! \cdot 1!} = \frac{120}{2 \times 2 \times 1} = \frac{120}{4} = 30$$ Réponse : 30 nombres. ## V. Permutation with some objects being alike Cette section est essentiellement une reformulation de la section IV, car "permutation with some objects being alike" désigne exactement le cas où il y a des objets identiques parmi un ensemble d'objets autrement distincts. La formule reste la même. > **À retenir** : Lorsque l'on arrange $n$ objets dont certains sont identiques, le nombre d'arrangements distincts est $\frac{n!}{n_1! n_2! \cdots n_k!}$, où $n_i$ est le nombre d'objets identiques du $i$-ième type. ### Exemple résolu (rappel) **Exemple 6** : Combien de façons y a-t-il d'arranger les boules suivantes : 3 boules rouges identiques, 2 boules bleues identiques et 1 boule verte ? **Solution** : Total de boules : $3 + 2 + 1 = 6$ Rouges : 3 identiques, Bleues : 2 identiques, Verte : 1 Nombre d'arrangements distincts : $$\frac{6!}{3! \cdot 2! \cdot 1!} = \frac{720}{6 \times 2 \times 1} = 60$$ Réponse : 60 façons. ### Exercices d'application corrigés **Exercice 11** : Combien de mots distincts peut-on former avec les lettres du mot "AABBC" ? **Solution** : Lettres : A (2 fois), B (2 fois), C (1 fois) Total : 5 lettres $$\frac{5!}{2! \cdot 2! \cdot 1!} = \frac{120}{2 \times 2 \times 1} = 30$$ Réponse : 30 mots distincts. **Exercice 12** : On a 4 stylos rouges identiques, 3 stylos bleus identiques et 2 stylos noirs identiques. Combien de façons d'en disposer un en ligne ? **Solution** : Total : $4 + 3 + 2 = 9$ stylos $$\frac{9!}{4! \cdot 3! \cdot 2!} = \frac{362880}{24 \times 6 \times 2} = \frac{362880}{288} = 1260$$ Réponse : 1260 façons. ## VI. Circular arrangements ### Définition Dans un arrangement circulaire, les objets sont placés autour d'un cercle. Deux arrangements sont considérés identiques si l'on peut obtenir l'un à partir de l'autre par une rotation. Contrairement aux arrangements linéaires, il n'y pas de position de départ fixe. > **À retenir** : Le nombre de permutations distinctes de $n$ objets distincts disposés autour d'un cercle est $(n-1)!$. ### Justification Dans un arrangement linéaire de $n$ objets distincts, il y a $n!$ possibilités. Dans un arrangement circulaire, chaque arrangement linéaire correspondant peut être obtenu en "coupant" le cercle à n'importe quel point, ce qui donne $n$ représentations linéaires pour un même arrangement circulaire. Donc, on divise par $n$ : $$\frac{n!}{n} = (n-1)!$$ ### Exemple résolu **Exemple 7** : Combien de façons y a-t-il d'asseoir 5 personnes différentes autour d'une table ronde ? **Solution** : Comme les arrangements circulaires considèrent les rotations comme identiques : $(5-1)! = 4! = 24$ Réponse : 24 façons. **Exemple 8** : Combien de façons y a-t-il d'asseoir 6 personnes autour d'une table ronde si deux personnes particulières doivent toujours s'asseoir côte à côte ? **Solution** : On traite les deux personnes qui doivent être côte à côte comme une seule entité "bloquée". On a alors : cette entité + les 4 autres personnes = 5 entités à arranger en cercle. Nombre d'arrangements circulaires de 5 entités : $(5-1)! = 4! = 24$ À l'intérieur de l'entité bloquée, les deux personnes peuvent s'arranger de $2!$ façons (AB ou BA). Donc total : $24 \times 2 = 48$ Réponse : 48 façons. ### Exercices d'application corrigés **Exercice 13** : Combien de façons y a-t-il d'arranger 7 clés différentes sur un anneau de clé (où les retournements ne sont pas considérés comme identiques, seulement les rotations) ? **Solution** : Sur un anneau, seules les rotations sont considérées comme identiques (pas les retournements, sauf si spécifié autrement — ici on suppose qu'on ne retourne pas l'anneau, donc seulement rotations). Donc : $(7-1)! = 6! = 720$ Réponse : 720 façons. **Exercice 14** : Combien de façons y a-t-il d'asseoir 4 hommes et 4 femmes autour d'une table ronde de sorte que les hommes et les femmes alternent ? **Solution** : On fixe une personne pour éliminer la symétrie de rotation. On fixe une femme à une position (pour référence). Alors, les positions restantes doivent alterner : après une femme vient un homme, puis une femme, etc. Comme on a fixé une femme, les 3 autres femmes doivent occuper les 3 positions restantes réservées aux femmes : $3!$ façons. Les 4 hommes doivent occuper les 4 positions réservées aux hommes : $4!$ façons. Donc total : $3! \times 4! = 6 \times 24 = 144$ Réponse : 144 façons. ## VII. Selection of objects from a group ### Définition de combinaison Une combinaison est une sélection d'objets où l'ordre n'a pas d'importance. On parle de "choix" ou de "sélection". > **À retenir** : Une combinaison est une sélection d'objets dans laquelle l'ordre des éléments sélectionnés n'a pas d'importance. ### Notation et formule Le nombre de façons de choisir $r$ objets parmi un ensemble de $n$ objets distincts, sans tenir compte de l'ordre, est noté $\binom{n}{r}$ ou $^nC_r$, et se calcule par : $$\binom{n}{r} = \frac{n!}{r!(n-r)!}$$ ### Propriétés - $\binom{n}{r} = \binom{n}{n-r}$ - $\binom{n}{0} = \binom{n}{n} = 1$ - $\binom{n}{r} = \frac{n}{r} \binom{n-1}{r-1}$ pour $r \geq 1$ - Somme des coefficients binomiaux : $\sum_{r=0}^{n} \binom{n}{r} = 2^n$ ### Exemple résolu **Exemple 9** : Combien de façons y a-t-il de choisir 3 livres parmi une étagère de 10 livres différents ? **Solution** : Comme l'ordre de sélection n'a pas d'importance, on utilise la combinaison : $$\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$$ Réponse : 120 façons. ### Exercices d'application corrigés **Exercice 15** : Combien de façons y a-t-il de choisir un comité de 4 personnes parmi un groupe de 12 ? **Solution** : $$\binom{12}{4} = \frac{12!}{4! \cdot 8!} = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = 495$$ Réponse : 495 façons. **Exercice 16** : Un étudiant doit répondre à 5 questions sur un examen qui en comporte 8. Combien de choix de questions a-t-il ? **Solution** : $$\binom{8}{5} = \binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$ Réponse : 56 choix. **Exercice 17** : Combien de diagonales a un polygone convexe à 7 côtés ? **Solution** : Un polygone à $n$ côtés a $\binom{n}{2}$ segments reliant deux sommets, dont $n$ sont les côtés du polygone. Donc nombre de diagonales : $\binom{n}{2} - n$ Pour $n = 7$ : $\binom{7}{2} = \frac{7 \times 6}{2} = 21$ Diagonales : $21 - 7 = 14$ Réponse : 14 diagonales. ## VIII. Permutation and combinations with Restrictions Cette section traite des problèmes où des conditions particulières restreignent les choix ou les arrangements (ex : certaines personnes doivent ou ne doivent pas être ensemble, certaines positions sont interdites, etc.). ### Stratégie générale 1. Identifier le nombre total d'arrangements ou de sélections sans restriction. 2. Identifier les cas qui violent la restriction. 3. Utiliser le principe d'inclusion-exclusion ou la méthode des cas pour soustraire les cas interdits. 4. Ou bien, compter directement les cas valides en les décomposant en sous-cas mutuellement exclusifs. ### Exemple résolu 1 : Permutation avec restriction d'adjacence **Exemple 10** : Combien de façons y a-t-il d'arranger 6 personnes différentes en ligne si deux personnes particulières, A et B, ne doivent pas être côte à côte ? **Solution** : Méthode : Total - arrangements où A et B sont côte à côte Total des permutations de 6 personnes : $6! = 720$ Nombre d'arrangements où A et B sont côte à côte : On traite A et B comme une seule entité bloquée. On a alors 5 entités à arranger : $5!$ façons. À l'intérieur du bloc, A et B peuvent être dans deux ordres : AB ou BA → $2!$ Donc : $5! \times 2! = 120 \times 2 = 240$ Nombre d'arrangements où A et B ne sont pas côte à côte : $720 - 240 = 480$ Réponse : 480 façons. ### Exemple résolu 2 : Combinaison avec restriction d'inclusion/exclusion **Exemple 11** : Un comité de 5 personnes doit être formé à partir de 8 hommes et 7 femmes. Combien de comités sont possibles s'il doit contenir au moins 2 femmes ? **Solution** : On peut utiliser la méthode du complément : total - comités avec moins de 2 femmes (c'est-à-dire 0 ou 1 femme). Total des comités de 5 personnes parmi 15 : $\binom{15}{5}$ Comités avec 0 femme (tous hommes) : on choisit 5 hommes parmi 8 : $\binom{8}{5}$ Comités avec exactement 1 femme : on choisit 1 femme parmi 7 et 4 hommes parmi 8 : $\binom{7}{1} \times \binom{8}{4}$ Donc : Nombre valide = $\binom{15}{5} - \left[ \binom{8}{5} + \binom{7}{1} \times \binom{8}{4} \right]$ Calculs : $\binom{15}{5} = \frac{15 \times 14 \times 13 \times 12 \times 11}{5 \times 4 \times 3 \times 2 \times 1} = 3003$ $\binom{8}{5} = \binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$ $\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$ $\binom{7}{1} \times \binom{8}{4} = 7 \times 70 = 490$ Donc : $3003 - (56 + 490) = 3003 - 546 = 2457$ Réponse : 2457 comités. ### Exemple résolu 3 : Permutation avec positions restreintes **Exemple 12** : Combien de façons y a-t-il d'arranger les lettres du mot "SUCCESS" de sorte que les deux S ne soient pas adjacents ? **Solution** : Le mot "SUCCESS" comporte 7 lettres : S (3 fois), U (1), C (2), E (1) On veut que les trois S ne soient pas adjacents deux à deux (c'est-à-dire qu'aucun deux S ne soient côte à côte). Méthode : placer d'abord les lettres non-S, puis insérer les S dans les espaces disponibles. Lettres non-S : U, C, C, E → 4 lettres, avec deux C identiques Nombre d'arrangements distincts de ces 4 lettres : $$\frac{4!}{2!} = \frac{24}{2} = 12$$ (UCCE, UCEC, UECC, CUCE, CUEC, CEUC, CCUE, CCEU, CECU, EUCC, ECUC, ECCU — mais on vérifie par formule : oui, 12) Lorsque l'on arrange ces 4 lettres en ligne, il y a 5 espaces où l'on peut insérer des S : _ L _ L _ L _ L _ (avant la première, entre chaque paire, et après la dernière) On doit choisir 3 de ces 5 espaces pour y placer un S chacun (comme les S sont identiques, l'ordre d'insertion n'a pas d'importance). Nombre de façons de choisir 3 espaces parmi 5 : $\binom{5}{3} = 10$ Comme les S sont identiques, une fois les espaces choisis, il n'y a qu'une seule façon de les placer. Donc nombre total d'arrangements valides : (nombre d'arrangements des non-S) × (nombre de façons de choisir les positions pour les S) $12 \times 10 = 120$ Réponse : 120 arrangements. ### Exercices d'application corrigés **Exercice 18** : Combien de façons y a-t-il d'arranger 5 garçons et 3 filles en ligne de sorte que aucune deux filles ne soient adjacentes ? **Solution** : On place d'abord les 5 garçons : ils créent 6 espaces : _ B _ B _ B _ B _ B _ On doit choisir 3 de ces 6 espaces pour y placer une fille chacune (comme les filles sont distinctes, l'ordre d'insertion importe). Nombre d'arrangements des garçons : $5! = 120$ Nombre de façons de choisir 3 espaces parmi 6 : $\binom{6}{3} = 20$ Nombre de façons d'arranger les 3 filles distinctes dans les espaces choisis : $3! = 6$ Donc total : $120 \times 20 \times 6 = 14\,400$ Réponse : 14 400 façons. **Exercice 19** : Combien de mots de 4 lettres peuvent être formés à partir des lettres du mot "EXAMEN" si aucune lettre ne peut être répétée et que le mot doit commencer par une voyelle ? **Solution** : Lettres de "EXAMEN" : E, X, A, M, E, N → mais attention : deux E identiques. Cependant, comme on ne peut pas répéter de lettres, on considère l'ensemble des lettres disponibles : {E, X, A, M, N} — mais il y a deux E, mais comme on ne répète pas, on ne peut utiliser qu'un seul E à la fois. En fait, pour des arrangements sans répétition, on considère l'ensemble des lettres distinctes disponibles : E, X, A, M, N → 5 lettres distinctes (même si il y a deux E dans le mot original, on ne peut pas utiliser deux E dans un même mot sans répétition, donc on traite l'E comme une seule option disponible pour le choix, mais on sait qu'il y a deux copies physiques — cependant, en combinaison sans répétition, on ne tient compte que des types, pas des multiplicités, tant qu'on ne dépasse pas la disponibilité. Ici, comme on ne prend qu'une seule E au maximum, et qu'il y en a deux disponibles, cela ne pose pas de problème : on peut choisir E comme l'une des lettres, et il y a suffisamment de copies. Donc ensemble de lettres utilisables sans répétition : {E, X, A, M, N} → 5 lettres distinctes. Voyelles : E, A → 2 voyelles Consonnes : X, M, N → 3 consonnes On veut des mots de 4 lettres, sans répétition, commençant par une voyelle. Étape 1 : Choisir la première lettre (voyelle) : 2 choix (E ou A) Étape 2 : Choisir les 3 lettres restantes parmi les 4 lettres restantes (puisqu'on a utilisé une lettre, et on ne répète pas) : Après avoir choisi la première lettre, il reste 4 lettres disponibles (sur les 5 initialement, moins celle utilisée). On doit choisir et arranger 3 de ces 4 lettres : nombre de permutations de 4 lettres prises 3 à la fois : $P(4,3) = 4 \times 3 \times 2 = 24$ Mais attention : cette approche suppose que après avoir fixé la première lettre, les 4 restantes sont toutes distinctes et disponibles. Vérifions : Si première lettre = E, alors lettres restantes : X, A, M, N → 4 lettres distinctes Si première lettre = A, alors lettres restantes : E, X, M, N → 4 lettres distinctes (note : il y avait deux E dans le mot original, mais on n'en a utilisé qu'un seul ici, donc il reste encore un E disponible — donc oui, 4 lettres distinctes) Donc dans les deux cas, 4 lettres distinctes restantes. Nombre de façons de choisir et arranger 3 lettres parmi 4 distinctes : $4 \times 3 \times 2 = 24$ Donc total : $2 \times 24 = 48$ Réponse : 48 mots. On peut aussi faire : Nombre de mots de 4 lettres sans répétition commençant par une voyelle = (nombre de choix pour la première lettre voyelle) × (nombre de permutations des 3 lettres restantes parmi les autres) = $2 \times P(4,3) = 2 \times 24 = 48$ **Exercice 20** : Un comité de 4 personnes doit être formé à partir de 6 hommes et 5 femmes. Combien de comités sont possibles s'il doit contenir plus d'hommes que de femmes ? **Solution** : Dans un comité de 4 personnes, "plus d'hommes que de femmes" signifie : - 4 hommes et 0 femme - 3 hommes et 1 femme (2 hommes et 2 femmes : égalité, pas plus d'hommes) (1 homme et 3 femmes : moins d'hommes) (0 homme et 4 femme : moins d'hommes) Donc on considère deux cas : Cas 1 : 4 hommes, 0 femme Nombre de façons : choisir 4 hommes parmi 6 : $\binom{6}{4} = \binom{6}{2} = 15$ Cas 2 : 3 hommes, 1 femme Nombre de façons : choisir 3 hommes parmi 6 : $\binom{6}{3} = 20$ choisir 1 femme parmi 5 : $\binom{5}{1} = 5$ Donc : $20 \times 5 = 100$ Total : $15 + 100 = 115$ Réponse : 115 comités. ## Synthèse du chapitre - Le principe de multiplication permet de compter le nombre de façons d'effectuer une séquence d'étapes indépendantes. - Le principe d'addition permet de compter le nombre de façons lorsque les cas sont mutuellement exclusifs. - Le factoriel $n!$ est le produit des entiers de 1 à $n$, avec $0! = 1$. - Une permutation est un arrangement où l'ordre compte ; une combinaison est une sélection où l'ordre ne compte pas. - Le nombre de permutations de $n$ objets distincts pris $r$ à la fois est $P(n,r) = \frac{n!}{(n-r)!}$. - Le nombre de combinaisons de $n$ objets distincts pris $r$ à la fois est $\binom{n}{r} = \frac{n!}{r!(n-r)!}$. - Pour les permutations avec répétition d'objets identiques : $\frac{n!}{n_1! n_2! \cdots n_k!}$. - Le nombre d'arrangements circulaires de $n$ objets distincts est $(n-1)!$. - Les problèmes avec restrictions se résolvent souvent par complémentarité ou par décomposition en cas mutuellement exclusifs. ## Glossaire - **Factoriel** : Produit de tous les entiers positifs de 1 à $n$, noté $n!$, avec $0! = 1$. - **Permutation** : Arrangement ordonné d'objets où l'ordre a de l'importance. - **Combinaison** : Sélection d'objets où l'ordre n'a pas d'importance. - **Principe de multiplication** : Si une tâche se décompose en étapes indépendantes, le nombre total de façons est le produit des nombres de façons pour chaque étape. - **Principe d'addition** : Si une tâche peut être réalisée de plusieurs façons mutuellement exclusives, le nombre total de façons est la somme des nombres de façons pour chaque cas. - **Permutation avec répétition** : Arrangement d'objets où certains sont identiques, réduisant le nombre d'arrangements distincts. - **Arrangement circulaire** : Disposition d'objets autour d'un cercle où les rotations sont considérées comme identiques. - **Restriction** : Condition qui limite les choix ou les arrangements possibles dans un problème de comptage.