Méthodes de dénombrement : les permutations

Une permutation est une façon de ranger tous les objets d'un ensemble dans un ordre : avec \( n \) objets distincts, il y a \( n! = n \times (n-1) \times \dots \times 2 \times 1 \) rangements possibles.

Objectifs

Utiliser le principe multiplicatif et un arbre de choix.
Connaître et calculer la factorielle \( n! \).
Dénombrer les permutations de \( n \) objets distincts.
Dénombrer les permutations avec des objets répétés (anagrammes).
Traiter des rangements avec contraintes (objets côte à côte, autour d'une table).

1. Le principe multiplicatif

Principe multiplicatif : si un choix se fait en plusieurs étapes successives, avec \( n_1 \) possibilités à la première étape, \( n_2 \) à la deuxième (quel que soit le premier choix), etc., le nombre total de possibilités est le produit \( n_1 \times n_2 \times \dots \).

2. Permutations d'objets distincts

Un arbre de choix montre toutes les possibilités : 3 choix pour la 1^re place, puis 2 pour la 2^e, puis 1 seul pour la dernière.

flowchart LR
  D[Debut] --> A1[Awa]
  D --> K1[Kofi]
  D --> N1[Nadia]
  A1 --> A1K[Kofi puis Nadia]
  A1 --> A1N[Nadia puis Kofi]
  K1 --> K1A[Awa puis Nadia]
  K1 --> K1N[Nadia puis Awa]
  N1 --> N1A[Awa puis Kofi]
  N1 --> N1K[Kofi puis Awa]

On obtient \( 3 \times 2 \times 1 = 6 \) rangements : ce sont les 6 permutations des trois amis.

Définition et formule

Une permutation de \( n \) objets distincts est une façon de les ranger tous dans un ordre donné. Le nombre de permutations est :

\[ n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1 \]

On lit « factorielle \( n \) ». Par convention, \( 0! = 1 \). On a aussi \( n! = n \times (n-1)! \).

\( n \)	1	2	3	4	5	6	7
\( n! \)	1	2	6	24	120	720	5 040

La méthode des cases

Pour la première place, les 4 objets sont disponibles : 4 choix.

Un objet est déjà placé : il reste 3 choix pour la deuxième place.

Il reste 2 choix pour la troisième place.

Le dernier objet va à la dernière place : 1 choix. On multiplie : 24 rangements.

Exemple résolu

Kouni veut ranger 5 livres différents sur une étagère. Combien de rangements possibles ?

On range tous les livres, dans un ordre, et ils sont tous différents : c'est une permutation de 5 objets.

\[ 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \]

Il y a 120 rangements possibles.

Six élèves doivent passer au tableau l'un après l'autre. Combien d'ordres de passage sont possibles ?

C'est une permutation de 6 élèves : \( 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 \).

Que vaut \( \dfrac{7!}{5!} \) ?

\( \dfrac{7!}{5!} = \dfrac{7 \times 6 \times 5!}{5!} = 7 \times 6 = 42 \). On simplifie avant de calculer.

3. Permutations avec répétition : les anagrammes

Si l'on range \( n \) objets dont \( n_1 \) sont identiques entre eux, \( n_2 \) identiques entre eux, etc., le nombre de rangements différents est :

\[ \frac{n!}{n_1! \times n_2! \times \dots} \]

On divise par \( n_1! \) car les \( n_1 \) objets identiques peuvent s'échanger de \( n_1! \) façons sans rien changer au rangement.

Exemple résolu 1 : ABIDJAN

ABIDJAN a 7 lettres : A, B, I, D, J, A, N. La lettre A apparaît 2 fois, les autres une fois.

Si toutes les lettres étaient différentes : \( 7! = 5\,040 \).

On divise par \( 2! = 2 \) pour les deux A : \[ \frac{7!}{2!} = \frac{5\,040}{2} = 2\,520 \text{ anagrammes} \]

Exemple résolu 2 : MAMADOU

Combien d'anagrammes du prénom MAMADOU ? Cherche d'abord !

Voir la solution

7 lettres : M deux fois, A deux fois, D, O et U une fois.

\[ \frac{7!}{2! \times 2!} = \frac{5\,040}{4} = 1\,260 \]

Combien d'anagrammes possède le mot BRYON ?

Les 5 lettres B, R, Y, O, N sont toutes différentes : \( 5! = 120 \).

4. Permutations avec contraintes

Objets qui doivent rester ensemble : la méthode du « bloc »

On colle les objets inséparables en un seul bloc, on permute les blocs, puis on permute l'intérieur du bloc.

Awa et Kofi forment un bloc. Il y a donc 4 « éléments » à ranger : le bloc et les 3 camarades. Cela donne \( 4! = 24 \) rangements.

Dans le bloc, Awa peut être à gauche ou à droite de Kofi : \( 2! = 2 \) façons.

Principe multiplicatif : \( 24 \times 2 = 48 \) photos où Awa et Kofi sont côte à côte, sur \( 5! = 120 \) au total.

Autour d'une table ronde

Autour d'une table ronde, seules les positions des personnes les unes par rapport aux autres comptent : faire tourner tout le monde d'une chaise ne change rien. On fixe donc une personne à sa place et on range les autres : il y a \( (n-1)! \) dispositions.

Exemple : 6 membres d'une famille autour d'une table pour le repas de fête. Combien de dispositions ? Cherche d'abord !

Voir la solution

On place la grand-mère Adjoa à une chaise fixe, puis on range les 5 autres :

\[ (6-1)! = 5! = 120 \text{ dispositions} \]

Combien de mots (même sans sens) peut-on former avec les lettres A, B, C, D, E si les lettres A et B doivent être côte à côte ?

Bloc AB plus C, D, E : \( 4! = 24 \) rangements, fois \( 2 \) pour AB ou BA : \( 48 \).

Erreurs fréquentes

Récapitulatif

Principe multiplicatif

Des choix successifs se multiplient : \( n_1 \times n_2 \times \dots \)

Factorielle

\( n! = n \times (n-1) \times \dots \times 1 \), et \( 0! = 1 \).

Permutation

Rangement de tous les objets dans un ordre ; \( n! \) pour \( n \) objets distincts.

Anagrammes avec lettres répétées

\( \dfrac{n!}{n_1! \times n_2! \times \dots} \)

Table ronde

\( (n-1)! \) dispositions : on fixe une personne et on range les autres.