Dénombrement

Le dénombrement consiste à déterminer combien d’éléments se trouvent dans un ensemble fini d’objets. Il a débuté avec l’étude des jeux de hasard, où les calculs de probabilité—comme trouver la chance de gagner—dépendent du dénombrement des résultats. Lorsque tous les résultats sont également probables, la probabilité d’un événement est simplement le rapport entre les résultats favorables et le nombre total de résultats possibles. C’est pourquoi le dénombrement est une compétence clé en probabilité, mais ses applications vont bien au-delà—il est essentiel dans de nombreux domaines des mathématiques.
Lorsque nous comptons sur nos doigts, nous gérons de petits ensembles. Ce chapitre vous apprendra à dénombrer des ensembles bien trop grands ou compliqués pour être comptés avec les doigts.

Principes de base du dénombrement

Méthode Modélisation d'un tirage aléatoire d'un sac

Un problème de sac représente un tirage aléatoire de boules dans un sac. Le sac contient $n$ boules, numérotées de 1 à $n$, indistinguables au toucher, ce qui rend le tirage aléatoire.

Sac avec 4 boulesIl y a deux critères clés pour distinguer ces tirages :

L’ordre dans lequel les boules sont tirées. Si l’ordre compte, c’est un "tirage avec ordre" ; sinon, c’est un "tirage sans ordre". Par exemple, tirer les boules 7, 33 et 24 s’écrit $(7,33,24)$ avec ordre et $\{7,33,24\}$ sans ordre. Notez que $\{7,33,24\} = \{33,24,7\}$, mais $(7,33,24) \neq (33,24,7)$.
La remise. Si chaque boule est remise dans le sac avant le tirage suivant, c’est un "tirage avec remise" ; sinon, c’est un "tirage sans remise".

Exemple

Dans une course de chevaux avec 10 chevaux, combien de façons différentes peut-on parier sur les trois premiers dans l’ordre exact (tiercé) ? Modélise cela comme un tirage dans un sac.

Correction

Cela devient : "Combien de façons peut-on tirer 3 boules d’un sac de 10 boules numérotées de $1$ à $10$, avec ordre et sans remise ?"
Par exemple, si le résultat de la course est le cheval numéro 3 premier, le cheval numéro 1 deuxième, et le cheval numéro 6 troisième, cela correspond au tirage de la boule numéro 3 en premier, de la boule numéro 1 en deuxième et de la boule numéro 6 en troisième, noté $ (3,1,6) $.

Proposition Principe de multiplication

S’il y a $m$ façons différentes de faire une chose, et pour chacune de celles-ci, $n$ façons différentes de faire une autre chose indépendamment, le principe de multiplication dit qu’il y a $m \times n$ façons de faire les deux choses à la suite.

Exemple

Trois villes, $X$, $Y$ et $Z$, sont reliées par des routes comme indiqué. Combien de façons différentes peut-on aller de $X$ à $Z$ via $Y$ ?

Correction

Pour chacune des 3 routes de $X$ à $Y$, il y a 2 routes de $Y$ à $Z$. Par le principe de multiplication, il y a $3 \times 2 = 6$ façons différentes d’aller de $X$ à $Z$ via $Y$.

Proposition Principe d'addition

Le principe d’addition dit : si vous avez $n$ façons de faire une chose et $m$ façons de faire une autre chose, et que vous ne pouvez pas faire les deux en même temps, alors le nombre total de façons de faire l’une ou l’autre est $n + m$.

Exemple

Une personne va faire du shopping dans un magasin aujourd’hui, soit dans la partie nord, soit dans la partie sud de la ville. Dans le nord, elle peut aller dans un centre commercial, un magasin de meubles ou une bijouterie (3 options). Dans le sud, elle peut aller dans un magasin de vêtements ou un magasin de chaussures (2 options).
Combien de magasins différents peut-elle choisir ?

Correction

Par le principe d’addition, il y a $3 + 2 = 5$ magasins différents à choisir.

Factoriels

Définition Factoriel

Pour tout entier positif $n$, $n!$ (lu "$n$ factoriel") est le produit des $n$ premiers entiers positifs : $$n! = n \times (n-1) \times \dots \times 2 \times 1.$$ Par convention, on définit $0! = 1$.

Exemple

Calcule $4!$.

Correction

$\begin{aligned}[t]4! &= 4 \times 3 \times 2 \times 1\\ &= 24\end{aligned}$

Proposition

$$n(n-1)(n-2) \dots (n-p+1) = \frac{n!}{(n-p)!}$$

Preuve

$$\begin{aligned}n(n-1)(n-2) \dots (n-p+1) &= \frac{n(n-1)(n-2) \dots (n-p+1)(n-p)(n-p-1) \dots 2 \times 1}{(n-p)(n-p-1) \dots 2 \times 1} \\ &= \frac{n!}{(n-p)!}\end{aligned}$$

Exemple

Exprime $10 \times 9 \times 8 \times 7$ sous forme factorielle.

Correction

$$\begin{aligned}10 \times 9 \times 8 \times 7 &= \dfrac{10 \times 9 \times 8 \times 7 \times 6!}{6!} \\ &= \dfrac{10!}{6!} \end{aligned}$$

Définition Coefficient binomial

Pour tous entiers $n \geqslant p \geqslant 0$, le coefficient binomial $\binom{n}{p}$ est défini par $$\binom{n}{p} = \frac{n!}{p!(n-p)!}$$

Tirages avec ordre et avec remise

Définition p-liste

Une p-liste est une sélection de $p$ éléments parmi un ensemble de $n$ éléments, où l'ordre de sélection a de l'importance et les éléments peuvent être répétés. Elle peut être représentée par un p-uplet dont les composantes peuvent être identiques. Cela correspond à un tirage de $p$ boules dans un sac de $n$ boules, avec remise et avec ordre.

Exemple

Le couple $(1,1)$ est une 2-liste de l'ensemble $\{1,2,3\}$. Notez que $(1,2)$ est une 2-liste différente de $(2,1)$ car l'ordre est différent. Au total, il y a 9 2-listes de cet ensemble, comme le montre le diagramme : $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(2,3)$, $(3,1)$, $(3,2)$ et $(3,3)$.

Proposition Nombre de p-listes

Le nombre de p-listes de $p$ éléments parmi un ensemble de $n$ éléments est donné par la formule :$$n^p$$

Preuve

Pour le premier élément de la liste, il y a $n$ choix. Comme les éléments peuvent être répétés (avec remise), il y a également $n$ choix pour le deuxième élément, et ainsi de suite pour les $p$ éléments. Par le principe de multiplication, le nombre total de listes est $n \times n \times \dots \times n$ ($p$ fois), soit $n^p$.

Exemple

Combien de codes PIN à 4 chiffres différents peut-on créer en utilisant les chiffres de 0 à 9 ?

Correction

Chaque chiffre peut être l'une des 10 options, et la répétition est autorisée. C'est une 4-liste d'un ensemble de 10. Le nombre de PINs possibles est $10^4 = 10\,000$.

Tirages avec ordre et sans remise

Définition Arrangement

Un arrangement est une sélection de $p$ éléments parmi un ensemble de $n$ éléments, où l'ordre de sélection a de l'importance et les éléments ne peuvent pas être répétés. Il peut être représenté par un p-uplet dont les composantes sont distinctes. Cela correspond à un tirage de $p$ boules dans un sac de $n$ boules, sans remise et avec ordre.

Exemple

Le couple $(1,3)$ est un arrangement de 2 éléments de l'ensemble $\{1,2,3\}$. Notez que $(3,1)$ est un arrangement différent. Au total, il y a 6 arrangements de 2 éléments de cet ensemble, comme le montre le diagramme : $(1,2)$, $(2,1)$, $(1,3)$, $(3,1)$, $(2,3)$ et $(3,2)$.

Proposition Nombre d'arrangements

Le nombre d’arrangements de $p$ éléments parmi un ensemble de $n$ éléments est donné par la formule :$$A_n^p = \frac{n!}{(n-p)!}$$

Preuve

Pour le premier élément, il y a $n$ choix. Comme les éléments ne peuvent être répétés, il y a $n-1$ choix pour le deuxième, $n-2$ pour le troisième, et ainsi de suite, jusqu'à $n-p+1$ choix pour le $p$-ième élément. Par le principe de multiplication, le nombre total d'arrangements est $n \times (n-1) \times \cdots \times (n-p+1) = \frac{n!}{(n-p)!}$.

Exemple

Dans une course de chevaux avec 10 chevaux, combien de façons différentes peut-on parier sur les trois premiers dans l’ordre exact (tiercé) ?

Correction

Ceci est un arrangement de 3 chevaux parmi 10. Le nombre de façons est $A_{10}^3 = \frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720$.

Définition Permutation

Une permutation est un arrangement de tous les $n$ éléments d'un ensemble ($p=n$).

Exemple

Le triplet $(1, 2, 3)$ est une permutation de l'ensemble $\{1, 2, 3\}$. Au total, il y a $3! = 6$ permutations de cet ensemble : $(1, 2, 3)$, $(1, 3, 2)$, $(2, 1, 3)$, $(2, 3, 1)$, $(3, 1, 2)$ et $(3, 2, 1)$.

Proposition Nombre de permutations

Le nombre de permutations d'un ensemble de $n$ éléments est $A_n^n = n!$.

Preuve

Cela découle directement de la formule des arrangements en posant $p=n$ :$A_n^n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = n!$.

Exemple

Combien de façons y a-t-il pour asseoir 100 invités sur 100 chaises lors d’un mariage ?

Correction

C'est le nombre de permutations de 100 invités, soit $100! \approx 9.33 \times 10^{157}$.

Tirages sans ordre et sans remise

Définition Combinaison

Une combinaison est une sélection de $p$ éléments parmi un ensemble de $n$ éléments, où l'ordre de sélection n'a pas d'importance. Elle peut être représentée par un sous-ensemble de $p$ éléments. Cela correspond à un tirage de $p$ boules dans un sac de $n$ boules, sans remise et sans ordre.

Exemple

L'ensemble $\{1,3\}$ est une combinaison de 2 éléments de l'ensemble $\{1,2,3\}$. Notez que $\{3,1\}$ est la même combinaison. Au total, il y a 3 combinaisons de 2 éléments de cet ensemble : $\{1,2\}$, $\{1,3\}$ et $\{2,3\}$. Chaque combinaison correspond à $2! = 2$ arrangements.

Proposition Nombre de combinaisons

Le nombre de combinaisons de $p$ éléments parmi un ensemble de $n$ est donné par le coefficient binomial :$$\binom{n}{p} = \frac{n!}{p!(n-p)!}$$

Preuve

Pour toute combinaison de $p$ éléments, il existe $p!$ façons de les arranger. Par conséquent, le nombre d'arrangements ($A_n^p$) est égal au nombre de combinaisons ($\binom{n}{p}$) multiplié par $p!$.$$A_n^p = \binom{n}{p} \times p! \implies \frac{n!}{(n-p)!} = \binom{n}{p} \times p!$$En divisant par $p!$, on obtient la formule des combinaisons.

Exemple

Combien de façons différentes y a-t-il pour choisir 5 numéros pour un tirage de Lotto à partir de 49 numéros ?

Correction

L'ordre des numéros n'a pas d'importance, c'est donc une combinaison. Le nombre de façons est $\binom{49}{5} = 1\,906\,884$.

Tableau récapitulatif des formules de dénombrement

Ce tableau résume les formules pour sélectionner $p$ éléments parmi un ensemble de $n$ éléments.

	Avec Remise	Sans Remise
L'ordre compte (p-liste/Arrangement)	$n^p$	$A_n^p = \dfrac{n!}{(n-p)!}$
L'ordre ne compte pas (Combinaison)	$\binom{n+p-1}{p}$	$\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$

Applications aux Probabilités

La principale motivation pour le développement des techniques de dénombrement fut la résolution de problèmes de probabilités. Pour une expérience où tous les résultats sont équiprobables, la probabilité d'un événement $E$ est définie par le rapport du nombre de cas favorables au nombre de cas possibles.

Méthode Résoudre un problème de probabilité avec le dénombrement

Pour trouver la probabilité d'un événement, suivez ces étapes :

Identifier l'expérience : Déterminer quel processus aléatoire a lieu (ex: tirer des cartes, lancer des dés, sélectionner des personnes).
Modéliser les issues : Déterminer si la sélection implique l'ordre et/ou la remise. Cela déterminera quelle formule de dénombrement utiliser.
Calculer le nombre total d'issues ($\Cardfr{U}$): Utiliser la formule appropriée du tableau récapitulatif pour trouver la taille de l'univers.
Calculer le nombre de cas favorables ($\Cardfr{E}$): Définir l'événement d'intérêt et utiliser les règles de dénombrement pour trouver son cardinal.
Calculer la probabilité : Appliquer la formule d'équiprobabilité, $P(E) = \frac{\Cardfr{E}}{\Cardfr{U}}$.

Exemple

Dans une course de 10 chevaux, vous pariez sur les trois premiers dans l'ordre exact (le tiercé). Si vous faites un seul pari, quelle est la probabilité de gagner ?

Correction

Appliquons la méthode en 5 étapes pour résoudre les problèmes de probabilité avec le dénombrement.

Identifier l'expérience : Une course se déroule avec 10 chevaux, et l'événement d'intérêt est le résultat ordonné des trois premiers.
Modéliser les issues : On sélectionne 3 chevaux parmi 10. Comme l'ordre d'arrivée est exact, l'ordre compte. Un cheval ne peut pas occuper plus d'une place, donc c'est sans remise. Le modèle est un arrangement.
Calculer le nombre total d'issues ($\Cardfr{U}$): Le nombre total d'arrivées possibles pour les trois premières places est le nombre d'arrangements de 3 chevaux parmi 10.$$ \Cardfr{U} = A_{10}^3 = \frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720 $$Il y a 720 tiercés possibles.
Calculer le nombre de cas favorables ($\Cardfr{E}$): Pour gagner, votre pari doit correspondre à l'unique ordre d'arrivée correct. Il n'y a donc qu'un seul cas favorable.$$ \Cardfr{E} = 1 $$
Calculer la probabilité : En utilisant la formule d'équiprobabilité :$$ P(\text{Gagner}) = \frac{\Cardfr{E}}{\Cardfr{U}} = \frac{1}{720} $$

La probabilité de gagner avec un seul pari est de 1 sur 720.