Principe multiplicatif et permutations

Calculer une probabilité en situation d'équiprobabilité revient à compter des issues. Or énumérer à la main devient vite impossible : il y a 2 598 960 mains de cinq cartes. Le dénombrement fournit les formules qui remplacent l'énumération.

Le principe multiplicatif

C'est le socle de tout le chapitre :

Si un choix se fait en plusieurs étapes indépendantes, le nombre total de possibilités est le produit du nombre de possibilités à chaque étape.

Un menu : 3 entrées, 4 plats, 2 desserts

             entrée      plat      dessert
               3     ×     4    ×     2      =  24 menus

L'arbre le rend visible : chaque branche du premier niveau se dédouble au second, et ainsi de suite.

            /--- plat1 --- dessert1
   entrée1 <                dessert2
            \--- plat2 --- ...
   entrée2 ...
   entrée3 ...
                        3 × 4 × 2 = 24 feuilles

Les tirages avec remise

Quand on répète k fois un choix parmi n possibilités, en pouvant répéter, le principe multiplicatif donne directement :

n × n × ... × n  =  n^k
   (k facteurs)

Code PIN à 4 chiffres :  10 × 10 × 10 × 10 = 10⁴ = 10 000 codes
Mot de 3 lettres :       26³ = 17 576

La factorielle et les permutations

Ranger n objets distincts dans un ordre, c'est choisir le premier parmi n, le deuxième parmi les n - 1 restants, et ainsi de suite :

n × (n-1) × (n-2) × ... × 2 × 1  =  n!        (« factorielle n »)

Ces rangements s'appellent les permutations de n objets.

Anagrammes du mot MATHS (5 lettres distinctes) :  5! = 120

0! = 1        1! = 1        2! = 2        3! = 6
4! = 24       5! = 120      6! = 720      10! = 3 628 800

La convention 0! = 1 n'est pas arbitraire : il y a exactement une façon de ne rien ranger, et cette valeur est celle qui rend toutes les formules suivantes cohérentes.

La factorielle explose : 20! dépasse déjà 2 × 10¹⁸. C'est pourquoi tout problème qui exige d'énumérer des permutations devient rapidement hors de portée, même pour un ordinateur — c'est le cas du fameux problème du voyageur de commerce.

Quand des objets sont identiques

Si certains objets se répètent, plusieurs rangements deviennent indiscernables. On divise alors par les permutations internes de chaque groupe :

Anagrammes de BANANE (6 lettres : A trois fois ? non — A×2, N×2, B, E)

        6!            720
   -----------  =  -------  =  180 anagrammes distinctes
    2! × 2!           4

En résumé

• Principe multiplicatif : des étapes indépendantes se multiplient.
• Tirage avec remise, k fois parmi n : n^k possibilités.
• Permutations de n objets distincts : n! rangements.
• 0! = 1, par convention cohérente avec toutes les formules.
• La factorielle explose : 20! dépasse déjà 10¹⁸.
• Objets identiques : on divise par les permutations internes de chaque groupe.