Dénombrement
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteObjectifs du chapitre
1. Ensembles et cardinaux
Définition
Soit E un ensemble fini.
On appelle cardinal de l'ensemble E et on note $\text{card}(E)$ le nombre d'éléments de E.
Exemple
Si E = {a ; b ; c ; d}, alors $\text{card}(E) = 4$.
Définition
Soit E un ensemble quelconque. On dit que F est une partie de E (ou un sous-ensemble de E) si et seulement si tous les éléments de F appartiennent également à E.
On note alors F $\subset$ E ( F « inclus » dans E).
Exemple
Si E = { a ; b ; c ; d }, F = { b ; c } et G = { d }
alors F $\subset$ E, G $\subset$ E mais G $\not\subset$ F.
Remarque
L'ensemble vide $\varnothing$ et l'ensemble E lui-même sont des parties de E.
Théorème
Le nombre de parties d'un ensemble de $ n $ éléments est $ 2^n $.
Exemple
L'ensemble E = { a ; b ; c } possède $2^3$ = 8 sous-ensembles :
$\varnothing$, { a }, { b }, { c }, { a ; b }, { a ; c }, { b ; c }, { a ; b ; c }.
Définition (Réunion de deux ensembles)
Soient A et B deux ensembles quelconques.
La réunion des ensembles A et B, notée A $\cup$ B, est l'ensemble des éléments qui appartiennent à A ou à B (ou aux deux ensembles).
Exemple
Si A = { a ; b ; c } et B = { a ; c ; d ; e }
alors A $\cup$ B = { a ; b ; c ; d ; e }.
Définition (Intersection de deux ensembles)
Soient A et B deux ensembles quelconques.
L'intersection des ensembles A et B, notée A $\cap$ B, est l'ensemble des éléments qui appartiennent à la fois à A et à B.
Exemple
Si on reprend l'exemple précédent : A = { a ; b ; c } et B = { a ; c ; d ; e }
alors A $\cap$ B = { a ; c }.
Définition (Produit cartésien)
Soient A et B deux ensembles non vides.
Le produit cartésien de A par B, noté A $\times$ B (A « croix » B), est l'ensemble des couples (a ; b) où a $\in$ A et b $\in$ B.
Remarque
- un couple s'écrit avec des parenthèses et un ensemble avec des accolades.
- l'ordre a de l'importance dans un couple ( c'est-à-dire que les couples (a ; b) et (b ; a) sont différents ).
- on définit de même le produit cartésien de 3 ensemble ou plus. A $\times$ B $\times$ C est l'ensemble des triplets (a ; b ; c) où a $\in$ A, b $\in$ B et c $\in$ C.
- on définit également A $ ^p $ = A $\times$ A $\times$...$\times$ A (p fois). Cet ensemble est composé de toutes les listes ordonnées de p éléments de A.
Exemple
Si A = { a ; b } et B = { 1 ; 2 ; 3 }
alors A $\times$ B = { (a ; 1) ; (a ; 2) ; (a ; 3) ; (b ; 1) ; (b ; 2) ; (b ; 3)}
et A$ ^2 $ = { (a ; a) ; (a ; b) ; (b ; a) ; (b ; b) }.
Propriété (Principe additif)
Si A et B sont deux ensembles finis disjoints (c'est-à-dire que A $\cap$ B = $\varnothing$), alors :
$\text{card}(A \cup B) = \text{card}(A) + \text{card}(B)$
Remarque
Dans le cas où A et B ne sont pas nécessairement disjoints, on a la formule plus générale :
$\text{card}(A \cup B) = \text{card}(A) + \text{card}(B) - \text{card}(A \cap B)$
Propriété (Principe multiplicatif)
Si A et B sont deux ensembles finis non vides, alors :
$\text{card}(A \times B) = \text{card}(A) \times \text{card}(B)$
Exemple
Si l'on reprend l'exemple précédent A = { a ; b }, B = { 1 ; 2 ; 3 }
et A $\times$ B = { (a ; 1) ; (a ; 2) ; (a ; 3) ; (b ; 1) ; (b ; 2) ; (b ; 3)}
alors :
$\text{card}(A) = 2$, $\text{card}(B) = 3$ et
$\text{card}(A \times B) = 2 \times 3 = 6$ ($A \times B$ contient 6 couples !)
Propriété
Soit E un ensemble fini de cardinal $ n $ et $ p $ un entier naturel non nul.
Le nombre de p-uplets d'éléments de E (avec répétition possible) est :
Exemple
On lance deux dés à six faces. L'ensemble des résultats possibles pour un dé est E = {1 ; 2 ; 3 ; 4 ; 5 ; 6}.
L'ensemble des résultats possibles pour deux dés est $E^2$, soit l'ensemble des couples.
Le nombre de résultats est donc $6^2$ = $\mathbf{36}$.
2. Permutations et p-uplets
Définition
Soit E un ensemble fini de cardinal $ n $.
Une permutation de E est une liste ordonnée comportant les $ n $ éléments de E sans répétition.
Exemple
Soit E={ a ; b ; c}
E admet 6 permutations qui sont : (a ; b ; c), (a ; c ; b), (b ; a ; c), (b ; c ; a), (c ; a ; b) et (c ; b ; a).
Remarque
- dans les notations avec parenthèses du type ( a ; b ; c ) l'ordre est pris en compte. (il s'agit d'une liste ordonnée)
- dans les notations avec accolades du type { a ; b ; c } l'ordre n'est pas pris en compte. (il s'agit d'un ensemble)
Théorème
Le nombre de permutations d'un ensemble fini E à n éléments est le nombre n ! ( factorielle n ) défini par :
$ n! = n\times \left(n - 1\right)\times . . .\times 1 $
Remarque
- par convention on pose 0 ! = 1
- pour tout entier $ n > 0 $ : $ n! = n\times \left(n - 1\right)! $
Exemple
Si l'on reprend l'exemple précédent on vérifie bien que :
$ 3! = 3\times 2\times 1=6 $
Définition
Soit E un ensemble quelconque.
Un p-uplet de E est une liste ordonnée de p éléments de E.
Exemple
Soit E = { a ; b ; c } :
( a ; c ; a ; b ; a ) est un 5-uplet de E.
Remarque
- un p-uplet de E est un élément de E$ ^p $ = E $\times$ E $\times$...$\times$ E (p fois) ;
- un 2-uplet est un couple ;
- un 3-uplet est un triplet, etc.
Définition
Soit E un ensemble fini de cardinal n et p un entier naturel inférieur ou égal à n.
Un arrangement de p éléments de E est un p-uplet formé de p éléments distincts de E.
Exemple
Soit A = { a ; b ; c ; d },
( a ; b ; c ) et ( b ; a ; d ) sont deux arrangements de 3 éléments de A.
( a ; b ; a ) n'est pas un arrangement car il possède deux éléments identiques.
Remarque
Une permutation d'un ensemble de n éléments n'est autre qu'un arrangement de n éléments de cet ensemble ( par exemple ( b ; a ; d ; c ) est une permutation de l'ensemble A de l'exemple précédent ).
Propriété
Soit E un ensemble fini de cardinal n et p un entier naturel inférieur ou égal à n.
Le nombre d'arrangements de p éléments de E est le nombre :
Exemple
8 coureurs participent à une course. Le nombre de podiums possibles ( un podium = les trois premières places en tenant compte de l'ordre d'arrivée ) est :
$ A_8^3 = 8 \times 7 \times 6 = 336. $
3. Combinaisons
Définition
Soit E un ensemble fini à $ n $ éléments et $ p $ un entier tel que $ 0\leqslant p\leqslant n $ .
Une combinaison de p éléments de E est une partie de E contenant p éléments.
Remarque
Une partie est un ensemble donc l'ordre n'est pas pris en compte
Exemple
Soit E={a;b;c}
E admet 3 combinaisons à 2 éléments qui sont : {a;b}, {a;c}, {b;c}
Théorème
Le nombre de combinaisons de p éléments d'un ensemble à n éléments est le nombre noté $ \begin{pmatrix} n \\ p \end{pmatrix} $ (on lit « $ p $ parmi $ n $ » ) égal à :
Exemple
- Dans l'exemple ci-dessus on a bien : $ \begin{pmatrix} 3 \\ 2 \end{pmatrix}=\dfrac{3!}{2!\times 1!}=\dfrac{6}{2}=3 $
Au poker une « main » est formée de 5 cartes parmi 52. Il y a donc :
$ \begin{pmatrix} 52 \\ 5 \end{pmatrix}=\dfrac{52!}{47!\times 5!}=\dfrac{52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}=2\,598\,960 $ combinaisons
Propriété (Symétrie)
Pour tout entier naturel $ n $ et tout entier $ p $ tel que $ 0 \leqslant p \leqslant n $ :
Exemple
$\begin{pmatrix} 10 \\ 8 \end{pmatrix} = \begin{pmatrix} 10 \\ 2 \end{pmatrix} = \dfrac{10 \times 9}{2 \times 1} = $ $\mathbf{45}$
Propriété
Pour tout entier naturel $ n $ :
$ \begin{pmatrix} n \\ 0 \end{pmatrix}=1 $et
$ \begin{pmatrix} n \\ n \end{pmatrix}=1 $.
Pour tout entier naturel $ n $ et tout entier naturel $ k $ ($ 0\leqslant k < n $) :
$ \begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} $.
Remarque
Ces propriétés permettent de calculer les combinaisons de proches en proches, grâce au Triangle de Pascal.
La figure ci-dessous représente ce triangle pour $ n\leqslant 10 $
Pour construire ce triangle on procède de la manière suivante :
- On place des «1 » dans la colonne $ k=0 $.
- On place des «1 » sur la diagonale (qui correspond à $ k=n $).
On utilise la formule $ \begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} $ pour calculer les autres coefficients.
Par exemple, pour trouver $ \begin{pmatrix} 7 \\ 4 \end{pmatrix}=35 $ on fait la somme des deux coefficients $ \begin{pmatrix} 6 \\ 3 \end{pmatrix}=20 $ et $ \begin{pmatrix} 6 \\ 4 \end{pmatrix}=15 $ de la ligne précédente.
Propriété
Pour tout entier naturel $ n $ :
Démonstration
Soit E un ensemble de cardinal $ n $.
- $\begin{pmatrix} n \\ 0 \end{pmatrix}$ représente le nombre de parties de E ayant 0 élément ;
- $\begin{pmatrix} n \\ 1 \end{pmatrix}$ représente le nombre de parties de E ayant 1 élément ;
- $ \cdots $
- $ \begin{pmatrix} n \\ n \end{pmatrix} $ représente le nombre de parties de E ayant $ n $ éléments.
- Le total de ces combinaisons représente le nombre total de parties de E soit $2^n$ d'après un résultat vu au paragraphe 1.
4. Formule du binôme de Newton
Théorème (Formule du binôme de Newton)
Soient $ a $ et $ b $ deux nombres réels et $ n $ un entier naturel. Alors :
Autrement dit :
Remarque
Les coefficients $ \begin{pmatrix} n \\ k \end{pmatrix} $ qui apparaissent dans ce développement sont exactement les coefficients binomiaux : ce sont les nombres de la ligne $ n $ du triangle de Pascal. Pour développer $ \left(a+b\right)^n $, il suffit donc de lire la ligne $ n $ du triangle, puis de faire décroître la puissance de $ b $ de $ n $ à $ 0 $ tandis que celle de $ a $ croît de $ 0 $ à $ n $. La relation de Pascal $ \begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} $ permet de passer d'une ligne à la suivante sans aucun calcul de factorielle.
Développement de $(a+b)^4$
La ligne $ n=4 $ du triangle de Pascal est : $ 1\ ;\ 4\ ;\ 6\ ;\ 4\ ;\ 1 $.
On obtient donc :
On peut vérifier la cohérence avec la somme des coefficients : $ 1+4+6+4+1=16=2^4 $, ce qui correspond bien à la valeur de $ \left(a+b\right)^4 $ pour $ a=b=1 $.
Développement de $(1+x)^n$
En posant $ a=x $ et $ b=1 $, le développement se simplifie car toutes les puissances de $ b $ valent $ 1 $ :
Par exemple, pour $ n=5 $ (ligne $ 1\ ;\ 5\ ;\ 10\ ;\ 10\ ;\ 5\ ;\ 1 $ du triangle) :
En particulier, pour $ x=1 $, on retrouve $ \begin{pmatrix} 5 \\ 0 \end{pmatrix}+\begin{pmatrix} 5 \\ 1 \end{pmatrix}+\cdots+\begin{pmatrix} 5 \\ 5 \end{pmatrix}=2^5=32 $, en accord avec la formule de la somme des coefficients binomiaux.
Les questions essentielles
1. Comment dénombrer des résultats avec des choix successifs ?
Identifier les choix indépendants et multiplier les nombres de possibilités entre eux (principe multiplicatif). Si les $ p $ choix portent sur le même ensemble de $ n $ éléments avec répétition, le résultat est $ n^p $.
Voir la fiche méthode : Dénombrer à l'aide du principe multiplicatif
2. Comment calculer une factorielle et dénombrer des permutations ?
On calcule $ n! = n \times (n-1) \times \cdots \times 1 $. Ce nombre donne le nombre de façons de ranger tous les éléments d'un ensemble de $ n $ éléments dans un certain ordre.
Voir la fiche méthode : Calculer une factorielle et dénombrer des permutations
3. Comment calculer le nombre d'arrangements ?
On utilise la formule $ A_n^p = n \times (n-1) \times \cdots \times (n-p+1) $ lorsque l'on choisit $ p $ éléments parmi $ n $ en tenant compte de l'ordre et sans répétition.
Voir la fiche méthode : Calculer le nombre d'arrangements
4. Comment calculer un coefficient binomial ?
On applique la formule $ \begin{pmatrix} n \\ p \end{pmatrix} = \dfrac{n!}{p!(n-p)!} $. Penser à utiliser la symétrie $ \begin{pmatrix} n \\ p \end{pmatrix} = \begin{pmatrix} n \\ n-p \end{pmatrix} $ pour simplifier le calcul lorsque $ p $ est grand.
Voir la fiche méthode : Calculer un coefficient binomial
5. Comment utiliser le triangle de Pascal ?
Construire le triangle ligne par ligne en plaçant des 1 aux extrémités et en additionnant les deux nombres situés au-dessus pour chaque case intérieure. Lire le coefficient souhaité à la ligne $ n $, colonne $ p $.
Voir la fiche méthode : Utiliser le triangle de Pascal
6. Comment choisir la bonne formule de dénombrement ?
Se poser deux questions : l'ordre compte-t-il ? La répétition est-elle possible ? La réponse oriente vers les p-uplets ($ n^p $), les permutations ($ n! $), les arrangements ($ A_n^p $) ou les combinaisons ($ \begin{pmatrix} n \\ p \end{pmatrix} $).
Voir la fiche méthode : Choisir la bonne formule de dénombrement