Principe multiplicatif et $p$-listes

Compter sans tout énumérer

En combinatoire, on cherche à dénombrer (compter) le nombre de façons de réaliser une situation, sans avoir à lister tous les cas un par un.

### Principe additif

Si une situation se décompose en plusieurs cas qui s'excluent mutuellement (on ne peut pas être dans deux cas à la fois), le nombre total de possibilités est la somme du nombre de possibilités de chaque cas.

Exemple : dans une classe, il y a 12 filles et 15 garçons. Choisir un délégué (fille OU garçon) offre $12+15=27$ possibilités.

### Principe multiplicatif

> Principe multiplicatif : si une situation se décompose en une succession de $k$ étapes indépendantes, comportant respectivement $n_1, n_2, \dots, n_k$ possibilités, alors le nombre total de façons de réaliser la situation complète est :
>

Exemple : pour s'habiller, on choisit un pantalon parmi 4, un t-shirt parmi 6 et une paire de chaussures parmi 3. Le nombre de tenues possibles est $4\times 6\times 3 = 72$.

### Listes avec répétition ($p$-listes)

On considère un ensemble $E$ à $n$ éléments. Une $p$-liste (ou $p$-uplet) d'éléments de $E$ est une liste ordonnée de $p$ éléments de $E$, où les répétitions sont autorisées (un même élément peut être choisi plusieurs fois).

> Nombre de $p$-listes : le nombre de $p$-listes d'un ensemble à $n$ éléments est :
>

Cela vient directement du principe multiplicatif : il y a $p$ étapes (choisir le 1er élément, le 2e, ..., le $p$-ième), et à chaque étape on a $n$ choix possibles, indépendamment des choix précédents.

### Exemple complet

Énoncé : un digicode utilise des codes à 4 chiffres, chaque chiffre étant choisi parmi $0,1,\dots,9$ (répétitions autorisées). Combien de codes différents existe-t-il ?

Résolution : ici $n=10$ (les 10 chiffres possibles) et $p=4$ (la longueur du code). Le nombre de codes est :

Il existe donc $10\,000$ codes à 4 chiffres possibles, de "0000" à "9999".

### Autres exemples classiques

- Mots de passe de longueur $p$ utilisant un alphabet de $n$ caractères (lettres, chiffres, symboles) : $n^p$ mots de passe possibles.
- Lancers successifs d'un dé à 6 faces, répété $p$ fois : $6^p$ résultats possibles (les répétitions sont permises puisqu'on peut obtenir la même face plusieurs fois).
- Tirages avec remise dans une urne à $n$ boules, $p$ tirages successifs : $n^p$ tirages possibles.

### Méthode

1. Identifier si la situation est une succession d'étapes indépendantes (principe multiplicatif) ou un choix entre cas exclusifs (principe additif).
2. Si c'est une $p$-liste avec répétition possible, repérer $n$ (taille de l'ensemble) et $p$ (nombre de choix successifs).
3. Appliquer la formule $n^p$ ou le produit des nombres de possibilités à chaque étape.