Langage de programmation - Mathématiques appliquées

Permutations et factorielles

Les permutations et les factorielles sont des notions fondamentales de la combinatoire, une branche des mathématiques consacrée au dénombrement des différentes façons d'organiser, de sélectionner ou de répartir des éléments. Elles permettent de déterminer combien d'ordres distincts peuvent être obtenus à partir d'un ensemble de valeurs, de personnes, de caractères ou d'objets. Ces concepts interviennent fréquemment en informatique lorsqu'un programme doit examiner plusieurs arrangements possibles, générer des séquences, résoudre un problème d'optimisation ou évaluer le nombre de solutions envisageables.

La factorielle représente le produit de tous les entiers positifs inférieurs ou égaux à une valeur donnée. Elle est directement liée aux permutations, puisque le nombre de façons différentes d'ordonner n éléments distincts est égal à n!. La croissance extrêmement rapide de cette fonction explique pourquoi certains algorithmes combinatoires deviennent impossibles à exécuter dès que la taille des données augmente légèrement. La compréhension des permutations et des factorielles est donc essentielle pour étudier la combinatoire, les probabilités, les coefficients binomiaux, la récursivité et l'analyse de la complexité des algorithmes.

La factorielle

La factorielle d'un entier naturel n est le produit de tous les entiers positifs compris entre 1 et n.

Elle est représentée par un point d'exclamation placé après le nombre :

Sa définition est :

n! = 1 × 2 × 3 × ... × n

Par exemple :

1! = 1

2! = 1 × 2 = 2

3! = 1 × 2 × 3 = 6

4! = 1 × 2 × 3 × 4 = 24

5! = 1 × 2 × 3 × 4 × 5 = 120

La factorielle peut également être représentée à l'aide de la notation de produit :

n! = π_i=1ⁿ i

La factorielle de zéro

Par convention, la factorielle de zéro vaut :

0! = 1

Cette définition peut sembler inhabituelle, puisqu'aucun entier positif n'est multiplié. Elle repose cependant sur la notion de produit vide, dont la valeur est définie comme étant 1.

Cette convention permet également de conserver la relation récursive :

n! = n × (n - 1)!

Pour n = 1, on obtient :

1! = 1 × 0!

Puisque :

1! = 1

il est nécessaire que :

0! = 1

La définition de 0! simplifie également de nombreuses formules combinatoires.

Définition récursive

La factorielle peut être définie de manière récursive :

0! = 1

n! = n × (n - 1)! pour n > 0

Par exemple :

5! = 5 × 4!

4! = 4 × 3!

3! = 3 × 2!

2! = 2 × 1!

1! = 1 × 0!

En remplaçant progressivement les expressions, on obtient :

5! = 5 × 4 × 3 × 2 × 1 = 120

Cette définition illustre parfaitement le fonctionnement d'un algorithme récursif.

Algorithme récursif de la factorielle

L'algorithme suivant calcule une factorielle par récursivité :

MODULE Factorielle(n)

   SI n = 0 ALORS
      RETOURNER 1
   FIN SI

   RETOURNER n × Factorielle(n - 1)

Le cas n = 0 constitue le cas d'arrêt. Sans celui-ci, la fonction continuerait à s'appeler indéfiniment.

Cette méthode est simple et correspond directement à la définition mathématique. Elle utilise toutefois un appel de fonction supplémentaire pour chaque valeur comprise entre n et 0.

Algorithme itératif de la factorielle

La factorielle peut également être calculée avec une boucle :

MODULE Factorielle(n)

   résultat ← 1

   BOUCLE POUR i ← 2 JUSQU'A n
      résultat ← résultat × i
   FIN BOUCLE POUR

   RETOURNER résultat

La variable résultat doit être initialisée à 1, puisque cette valeur est l'élément neutre de la multiplication.

Cette version est généralement plus économique en mémoire que la version récursive, car elle ne nécessite pas l'empilement de plusieurs appels de fonction.

Exemple en Java

L'exemple suivant présente une version itérative et une version récursive du calcul de la factorielle :


public class FactorielleSample {
 
    public static long factorielleIterative(int n) {
        if (n < 0) {
            throw new IllegalArgumentException(
                "La factorielle n'est pas définie pour un entier négatif."
            );
        }
 
        long resultat = 1;
 
        for (int i = 2; i <= n; i++) {
            resultat *= i;
        }
 
        return resultat;
    }
 
    public static long factorielleRecursive(int n) {
        if (n < 0) {
            throw new IllegalArgumentException(
                "La factorielle n'est pas définie pour un entier négatif."
            );
        }
 
        if (n == 0) {
            return 1;
        }
 
        return n * factorielleRecursive(n - 1);
    }
 
    public static void main(String[] args) {
        System.out.println("5! = "
            + factorielleIterative(5));
 
        System.out.println("10! = "
            + factorielleRecursive(10));
    }
}

Le programme retourne :

5! = 120 10! = 3628800

Croissance de la factorielle

La fonction factorielle croît extrêmement rapidement.

n	n!
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5 040
8	40 320
9	362 880
10	3 628 800
15	1 307 674 368 000
20	2 432 902 008 176 640 000

Cette croissance est plus rapide qu'une fonction exponentielle comme 2? ou 10? lorsque n devient suffisamment grand.

Elle entraîne rapidement un dépassement de capacité dans les types numériques ordinaires.

Par exemple, un entier signé de 32 bits ne peut représenter correctement les factorielles que jusqu'à :

12! = 479001600

car :

13! = 6227020800

dépasse sa valeur maximale.

Un entier signé de 64 bits peut représenter exactement les factorielles jusqu'à :

20!

mais pas :

21!

Pour calculer des factorielles plus importantes, il faut employer un type multiprécision comme BigInteger.

Les permutations

Une permutation est un arrangement ordonné de tous les éléments d'un ensemble.

Deux arrangements sont considérés comme différents lorsque l'ordre de leurs éléments est différent.

Par exemple, les permutations des trois lettres A, B et C sont :

ABC
ACB
BAC
BCA
CAB
CBA

Il existe donc 6 ordres possibles.

Comme :

3! = 6

le nombre de permutations de trois éléments distincts correspond bien à la factorielle de 3.

Nombre de permutations de n éléments

Pour n éléments distincts, le nombre de permutations possibles est :

P(n) = n!

Cette formule peut être expliquée à l'aide du principe multiplicatif.

Pour la première position, il existe n choix possibles.

Après avoir sélectionné le premier élément, il reste :

n - 1

choix pour la deuxième position.

Il reste ensuite :

Après avoir sélectionné le premier élément, il reste :

n - 2

choix pour la troisième position, et ainsi de suite.

Le nombre total d'arrangements est donc :

n × (n - 1) × (n - 2) × ... × 1

soit :

Exemple de permutations

Supposons que quatre personnes doivent prendre place sur quatre sièges.

Pour le premier siège, quatre personnes peuvent être choisies.

Pour le deuxième siège, il reste trois possibilités.

Pour le troisième siège, il reste deux possibilités.

Pour le dernier siège, une seule personne demeure.

Le nombre total d'ordres est donc :

4 × 3 × 2 × 1

soit :

4! = 24

Il existe donc 24 façons différentes de placer les quatre personnes.

Permutations partielles

Il n'est pas toujours nécessaire d'utiliser tous les éléments disponibles.

Une permutation partielle, également appelée arrangement, consiste à choisir et à ordonner r éléments parmi un ensemble de n éléments distincts.

Le nombre d'arrangements est donné par :

P(n,r) = n! / (n-r)!

où :

n représente le nombre total d'éléments ;
r représente le nombre d'éléments sélectionnés ;
l'ordre des éléments est important.

Par exemple, si l'on souhaite attribuer les trois premières positions d'une compétition à trois personnes parmi dix participants :

P(10,3) = 10! / 7!

En simplifiant :

P(10,3) = 10 × 9 × 8

Le résultat est :

720

Il existe donc 720 podiums différents.

Différence entre permutation et combinaison

Dans une permutation, l'ordre est important.

Ainsi :

ABC

et :

BAC

sont considérés comme deux résultats différents.

Dans une combinaison, l'ordre n'est pas important. Les groupes :

ABC

et :

BAC

représentent alors la même sélection.

Opération	Sélection	Ordre important
Permutation complète	Tous les éléments	Oui
Arrangement	Une partie des éléments	Oui

Combinaison Une partie des éléments Non

Cette distinction est fondamentale dans la résolution des problèmes de dénombrement.

Permutations avec répétition autorisée

Lorsque les éléments peuvent être réutilisés, chaque position dispose du même nombre de choix.

Si une séquence contient r positions et que chaque position peut recevoir l'une des n valeurs possibles, le nombre de séquences est :

n^r

Par exemple, un code de quatre chiffres utilisant les valeurs de 0 à 9 peut produire :

10⁴ = 10000

codes différents, lorsque les répétitions sont autorisées.

Les codes comprennent alors toutes les valeurs de :

0000

à :

9999

Il s'agit de séquences ordonnées avec répétition, et non de permutations classiques sans répétition.

Permutations d'éléments identiques

Lorsque certains éléments sont identiques, la formule n! compte plusieurs fois les mêmes arrangements.

Le nombre de permutations distinctes devient :

n! / (n₁! × n₂! × ... × n_k!)

où :

n représente le nombre total d'éléments ;
n₁, n₂, ..., n_k représentent les nombres de répétitions de chaque catégorie d'éléments.

Par exemple, le mot :

MAMAN

contient cinq lettres, avec :

deux lettres M ;
deux lettres A ;
une lettre N.

Le nombre de permutations distinctes est :

5! / (2! × 2!)

soit :

120 / 4 = 30

Il existe donc 30 arrangements distincts des lettres du mot «MAMAN».

Permutations circulaires

Une permutation circulaire organise les éléments autour d'un cercle.

Dans ce cas, les arrangements obtenus uniquement par rotation sont considérés comme identiques.

Pour n éléments distincts, le nombre de permutations circulaires est :

(n - 1)!

Par exemple, quatre personnes placées autour d'une table ronde peuvent être organisées de :

(4 - 1)! = 3! = 6

façons différentes.

Dans une disposition linéaire, il aurait existé :

4! = 24

arrangements.

Cette différence vient du fait qu'une rotation complète autour de la table ne crée pas un nouvel ordre relatif entre les personnes.

Génération des permutations

Un programme peut générer toutes les permutations d'un ensemble en choisissant successivement chacun des éléments disponibles.

Une approche récursive consiste à :

sélectionner un élément ;
le placer dans la position courante ;
générer les permutations des éléments restants ;
recommencer avec chaque élément disponible.

Un algorithme simplifié est le suivant :

MODULE GenererPermutations(tableau, position)

   SI position = longueur(tableau) ALORS
      AFFICHER tableau
      RETOURNER
   FIN SI

   POUR i ← position JUSQU'A longueur(tableau) - 1

   ÉCHANGER tableau[position] ET tableau[i]
   GenererPermutations(tableau, position + 1)
   ÉCHANGER tableau[position] ET tableau[i]

   FIN POUR

Le deuxième échange rétablit le tableau dans son état précédent. Cette opération est appelée retour arrière ou backtracking.

Exemple de génération en Java

L'exemple suivant affiche toutes les permutations d'un tableau de caractères :


public class PermutationsSample {
 
    public static void permuter(
        char[] valeurs,
        int position
    ) {
        if (position == valeurs.length) {
            System.out.println(
                new String(valeurs)
            );
            return;
        }
 
        for (
            int i = position;
            i < valeurs.length;
            i++
        ) {
            echanger(valeurs, position, i);
 
            permuter(valeurs, position + 1);
 
            echanger(valeurs, position, i);
        }
    }
 
    private static void echanger(
        char[] valeurs,
        int a,
        int b
    ) {
        char temporaire = valeurs[a];
        valeurs[a] = valeurs[b];
        valeurs[b] = temporaire;
    }
 
    public static void main(String[] args) {
        char[] valeurs = {'A', 'B', 'C'};
 
        permuter(valeurs, 0);
    }
}

Le programme produit :

ABC ACB BAC BCA CBA CAB

L'ordre exact d'affichage dépend de la manière dont les échanges sont effectués.

Complexité de la génération des permutations

La génération de toutes les permutations de n éléments nécessite de produire n! résultats.

La complexité temporelle ne peut donc pas être inférieure à :

O(n!)

Si chaque permutation doit être copiée ou affichée, son traitement nécessite également jusqu'à n opérations. La complexité totale peut alors être exprimée par :

O(n × n!)

Cette croissance devient rapidement considérable.

Nombre d'éléments	Nombre de permutations
5	120
8	40 320
10	3 628 800
12	479 001 600
15	1 307 674 368 000
20	2 432 902 008 176 640 000

Un programme peut facilement générer les permutations de cinq ou huit éléments. En revanche, parcourir toutes les permutations de vingt éléments est irréaliste dans la plupart des environnements informatiques.

Algorithmes de complexité factorielle

Certains problèmes sont naturellement associés à une complexité factorielle.

Par exemple, une méthode naïve permettant de résoudre le problème du voyageur de commerce peut examiner toutes les permutations des villes afin de trouver le trajet le plus court.

Pour n villes, le nombre de circuits possibles augmente approximativement comme :

De même, un programme de recherche exhaustive peut examiner toutes les façons :

d'ordonner des tâches ;
d'organiser des personnes ;
d'attribuer des positions ;
de visiter des sommets ;
d'arranger des symboles.

Les algorithmes factoriels sont généralement utilisables uniquement avec de très petites valeurs de n.

Approximation de Stirling

Pour les grandes valeurs de n, le calcul exact de la factorielle peut être remplacé par une approximation.

L'approximation de Stirling est :

n! ≈ √(2πn) × (n/e)ⁿ

où :

π représente la constante pi ;
e représente la base du logarithme naturel.

Cette approximation devient de plus en plus précise lorsque n augmente.

Elle est particulièrement utile pour :

estimer la taille d'une factorielle ;
calculer son nombre de chiffres ;
analyser des algorithmes ;
simplifier des expressions combinatoires ;
effectuer des calculs probabilistes.

Nombre de chiffres d'une factorielle

Le nombre de chiffres décimaux de n! peut être obtenu sans calculer directement toute la factorielle.

La formule est :

⌊log₁₀(n!)⌋ + 1

Comme :

log(n!) =
log(1) + log(2) + ... + log(n)

il est possible de calculer :

⌊∑_i=1ⁿ log₁₀(i)⌋ + 1

Cette méthode évite de manipuler directement un entier gigantesque.

Par exemple :

10! = 3628800

possède :

chiffres.

Factorielle et fonction Gamma

La factorielle est normalement définie pour les entiers naturels. Elle peut toutefois être généralisée aux nombres réels et complexes à l'aide de la fonction Gamma.

La relation est :

n! = Γ(n + 1)

Par exemple :

Γ(6) = 5! = 120

La fonction Gamma permet donc de prolonger la notion de factorielle à des valeurs non entières, à l'exception de certains nombres négatifs.

Elle est utilisée en probabilités, en statistiques, en physique mathématique et dans plusieurs bibliothèques scientifiques.

Applications

Les permutations et les factorielles interviennent dans de nombreux domaines :

combinatoire ;
probabilités ;
statistiques ;
cryptographie ;
génération de mots de passe ;
ordonnancement de tâches ;
recherche exhaustive ;
intelligence artificielle ;
optimisation ;
résolution de casse-têtes ;
analyse des algorithmes ;
théorie des graphes ;
tests logiciels ;
bio-informatique.

Elles sont également utilisées dans les coefficients binomiaux, les distributions de probabilités et les formules de dénombrement.

Avantages

Les permutations et les factorielles présentent plusieurs avantages :

elles permettent de compter les arrangements possibles ;
elles traduisent simplement le principe multiplicatif ;
elles facilitent l'étude des problèmes combinatoires ;
elles sont faciles à définir récursivement ;
elles permettent d'évaluer la taille d'un espace de recherche ;
elles constituent une base essentielle des probabilités.

Limites et précautions

Plusieurs précautions doivent néanmoins être prises :

la factorielle croît extrêmement rapidement ;
les types numériques ordinaires débordent après de faibles valeurs ;
un algorithme de complexité factorielle devient rapidement inutilisable ;
la récursivité peut provoquer un dépassement de la pile ;
les éléments répétés doivent être pris en compte dans le dénombrement ;
il faut distinguer les permutations, les arrangements et les combinaisons ;
il faut préciser si les répétitions sont autorisées ;
les calculs portant sur de très grandes factorielles nécessitent des entiers multiprécision ou des logarithmes.

Remarque

Les permutations et les factorielles permettent de mesurer le nombre de façons différentes d'organiser des éléments et d'évaluer la taille d'un espace de recherche. Elles montrent également qu'un problème apparemment simple peut devenir extrêmement difficile lorsque le nombre de données augmente. Une croissance en n! dépasse rapidement les capacités pratiques d'un ordinateur, ce qui oblige les programmeurs à utiliser des méthodes d'optimisation, des heuristiques, de la programmation dynamique ou des techniques de réduction de l'espace de recherche. Ces notions constituent une préparation essentielle à l'étude des coefficients binomiaux, des combinaisons, des probabilités et de l'analyse de la complexité des algorithmes.

Dernière mise à jour : Jeudi, le 16 juillet 2026

Section courante

A propos

Section administrative du site

Permutations et factorielles

La factorielle

La factorielle de zéro

Définition récursive

Algorithme récursif de la factorielle

Algorithme itératif de la factorielle

Exemple en Java

Croissance de la factorielle

Les permutations

Nombre de permutations de n éléments

Exemple de permutations

Permutations partielles

Différence entre permutation et combinaison

Combinaison Une partie des éléments Non

Permutations avec répétition autorisée

Permutations d'éléments identiques

Permutations circulaires

Génération des permutations

Exemple de génération en Java

Complexité de la génération des permutations

Algorithmes de complexité factorielle

Approximation de Stirling

Nombre de chiffres d'une factorielle

Factorielle et fonction Gamma

Applications

Avantages

Limites et précautions

Remarque