Introduction
Combien de mots de passe de 4 chiffres existe-t-il ? De combien de façons peut-on former un comité de 3 personnes dans une classe de 30 ? Combien de résultats possibles pour 10 lancers de pièce ? Toutes ces questions demandent de compter sans lister. C'est l'objet du dénombrement.
Tu retrouveras ces outils en informatique (nombre de mots binaires, d'affectations possibles), en génétique (combinaisons de caractères), en théorie des jeux et surtout en probabilités : quand toutes les issues sont équiprobables, une probabilité est un quotient de deux dénombrements. Les ensembles considérés dans ce chapitre sont finis, et le nombre d'éléments d'un ensemble fini se note .
Les objets de base
Couples, triplets, k-uplets
Un couple est une liste ordonnée de deux éléments, un triplet une liste ordonnée de trois éléments. Plus généralement, un k-uplet (ou k-liste) est une liste ordonnée de éléments. L'ordre compte : . Les répétitions sont permises : est un couple.
Produit cartésien
Le produit cartésien de deux ensembles et est l'ensemble des couples avec et . On définit de même (triplets), et plus généralement le produit de ensembles. Quand tous les ensembles sont égaux à , on note l'ensemble des k-uplets d'éléments de .
Exemple
Avec et , l'ensemble contient les 6 couples , , , , , .
Les deux principes fondamentaux
Principe additif
Si sont des ensembles finis deux à deux disjoints (aucun élément commun à deux d'entre eux), alors
On l'utilise quand on choisit soit une option, soit une autre, et que les cas s'excluent. La condition de disjonction est essentielle : si les ensembles se chevauchent, on compte deux fois les éléments communs.
Exemple
Une classe compte 12 élèves qui font du judo et 9 qui font du théâtre, aucun ne faisant les deux. Le nombre d'élèves qui font l'une de ces activités est .
Principe multiplicatif
Pour des ensembles finis, , et plus généralement
On l'utilise quand on fait une première chose, puis une deuxième, puis... : le nombre total de résultats est le produit du nombre de choix à chaque étape. Un arbre de choix le visualise : chaque chemin de la racine à une feuille correspond à un k-uplet, et le nombre de chemins est le produit des nombres de branches.
Exemple
Un menu propose 3 entrées, 4 plats et 2 desserts. Il y a menus complets.
Nombre de k-uplets d'un ensemble
Si a éléments, alors . C'est le principe multiplicatif appliqué à fois le même ensemble.
Exemple
Un code de 4 chiffres (chaque chiffre pris parmi 0 à 9, répétitions permises) : codes.
Les parties d'un ensemble
Un ensemble à éléments possède exactement parties (en comptant la partie vide et lui-même).
Pourquoi ? Numérote les éléments . Une partie est entièrement décrite par un n-uplet de : la -ème composante vaut 1 si appartient à la partie, 0 sinon. Il y a donc autant de parties que de n-uplets de , soit .
Ce même nombre compte aussi :
- les mots de longueur écrits avec un alphabet de deux lettres ;
- les chemins d'un arbre à niveaux où chaque noeud a deux branches ;
- les issues d'une succession de épreuves de Bernoulli (chaque épreuve a deux issues, succès ou échec).
Exemple
Un ensemble de 5 éléments a parties.
K-uplets d'éléments distincts, factorielle et permutations
K-uplets d'éléments distincts
On veut maintenant des k-uplets dont les éléments sont tous différents (pas de répétition). Dans un ensemble à éléments, il y a choix pour la première composante, pour la deuxième (on ne peut pas reprendre le premier élément), pour la troisième, etc. Par le principe multiplicatif, le nombre de k-uplets d'éléments distincts est
pour .
Exemple
Un podium (or, argent, bronze) parmi 8 coureurs : podiums possibles.
Factorielle
Pour un entier , on pose , et par convention . Ainsi et . Le nombre de k-uplets d'éléments distincts d'un ensemble à éléments s'écrit aussi .
Permutations
Une permutation d'un ensemble fini à éléments est une façon de ranger ses éléments dans un certain ordre : c'est un n-uplet d'éléments distincts qui utilise tous les éléments. Leur nombre est .
Exemple
Les lettres du mot « MATH » peuvent être rangées de façons (les 4 lettres sont différentes).
Combinaisons
Définition
Une combinaison de éléments d'un ensemble à éléments est une partie de cet ensemble ayant éléments. Ici l'ordre ne compte pas et il n'y a pas de répétition : . Leur nombre se note (on lit « parmi »).
Formule
Pour :
Pourquoi ? Chaque partie à éléments peut être ordonnée de façons pour donner un k-uplet d'éléments distincts. Il y a donc fois plus de k-uplets d'éléments distincts que de parties à éléments, d'où .
Exemple
Former un comité de 3 personnes parmi 30 : .
Cas particuliers
Pour , la seule partie à 0 élément est la partie vide. Pour , il y a une partie par élément.
Symétrie
Pour :
Choisir les éléments que l'on garde revient à choisir les éléments que l'on écarte. Par exemple .
Représentation en mots et en chemins
Une partie à éléments d'un ensemble à éléments correspond à un mot de longueur sur l'alphabet qui contient exactement fois la lettre 1. Dans un arbre de niveaux à deux branches, c'est un chemin qui emprunte exactement fois la branche « 1 ». Donc est aussi le nombre de chemins réalisant succès lors de épreuves de Bernoulli.
Relation de Pascal et triangle de Pascal
La relation de Pascal
Pour :
Démonstration combinatoire. Fixe un élément de l'ensemble à éléments. Les parties à éléments de se répartissent en deux familles disjointes : celles qui contiennent (on choisit alors autres éléments parmi : possibilités) et celles qui ne contiennent pas (on choisit éléments parmi les autres : possibilités). Le principe additif donne la relation.
Démonstration par le calcul. On met au même dénominateur :
Le triangle de Pascal
La relation de Pascal permet de construire les coefficients ligne par ligne : chaque coefficient est la somme des deux situés au-dessus de lui, et les bords valent 1.
| 0 | 1 | |||||
| 1 | 1 | 1 | ||||
| 2 | 1 | 2 | 1 | |||
| 3 | 1 | 3 | 3 | 1 | ||
| 4 | 1 | 4 | 6 | 4 | 1 | |
| 5 | 1 | 5 | 10 | 10 | 5 | 1 |
On lit par exemple . La symétrie se voit : chaque ligne se lit pareil dans les deux sens.
Somme des coefficients
Démonstration par dénombrement. Les parties d'un ensemble à éléments sont au nombre de . On les classe selon leur nombre d'éléments , de 0 à : il y en a avec éléments. Ces familles sont deux à deux disjointes, donc le principe additif donne . Vérification sur la ligne : .
Méthode : bien choisir son outil
Pour résoudre un problème de dénombrement, représente la situation (ensemble, arbre, tableau, diagramme), puis reconnais l'objet à compter en te posant trois questions.
- L'ordre compte-t-il ? Un podium : oui. Un comité : non.
- Les répétitions sont-elles permises ? Un code : oui. Un tirage sans remise : non.
- Y a-t-il des cas exclusifs ? Alors on les sépare et on additionne.
| Situation | Objet | Nombre |
|---|---|---|
| Ordre important, répétitions permises | k-uplet de | |
| Ordre important, sans répétition | k-uplet d'éléments distincts | |
| Ranger tous les éléments | permutation | |
| Ordre sans importance, sans répétition | combinaison | |
| Sous-ensemble quelconque | partie |
Exemple travaillé. Une urne contient 5 boules rouges et 4 boules noires, toutes discernables. On tire simultanément 3 boules. Combien de tirages contiennent exactement 2 rouges ?
- Le tirage est simultané : l'ordre ne compte pas, donc on compte des parties.
- On choisit 2 rouges parmi 5 : façons.
- Puis 1 noire parmi 4 : façons.
- Choix successifs et indépendants : principe multiplicatif, tirages.
Pour comparaison, le nombre total de tirages de 3 boules parmi 9 est . La proportion de tirages à 2 rouges est .
Exemple avec cas exclusifs. Combien de tirages de 3 boules contiennent au moins 2 rouges ? Deux cas qui s'excluent : exactement 2 rouges ( tirages) ou exactement 3 rouges ( tirages). Par le principe additif : .
Algorithmes associés
Trois algorithmes illustrent ce chapitre.
- Générer la ligne du triangle de Pascal : on part de la ligne et on applique la relation de Pascal terme à terme.
- Générer les permutations d'un ensemble fini, ou en tirer une au hasard.
- Générer les parties à 2 ou 3 éléments d'un ensemble fini, avec deux ou trois boucles imbriquées qui évitent les répétitions.
Les erreurs classiques
- Confondre ordre et absence d'ordre. Choisir un bureau (président, trésorier) parmi 10 personnes donne , pas , car les rôles distinguent les deux personnes.
- Additionner au lieu de multiplier, ou l'inverse. Des étapes successives se multiplient ; des cas exclusifs s'additionnent.
- Appliquer le principe additif à des ensembles qui se chevauchent. Les éléments communs seraient comptés deux fois.
- Dénombrer « au moins un » cas par cas. Compte plutôt le total, puis retire les cas « aucun ». Pour un code à 3 chiffres contenant au moins un 7 : .
- Oublier que les répétitions sont permises : pour un code à 4 chiffres, c'est , pas .
- Écrire pour un arrangement partiel. Pour 3 places parmi 8, c'est , pas .
- Mal calculer : le numérateur a exactement facteurs, et .
- Oublier les cas extrêmes dans : la partie vide et l'ensemble entier comptent.