Séance 13-1 : Dénombrement (Cours)

Mathématiques : 1Bac SM

Séance 13-1 : Dénombrement (Cours)

Professeur : Mr CHEDDADI Haitam

Sommaire

I- Ensemble fini - Cardinal d'un ensemble fini

1-1/ Ensemble fini

1-2/ Propriétés du calcul sur les cardinaux

II- Principe fondamental de dénombrement - Cardinal d'un produit cartésien

2-1/ Principe fondamental du dénombrement

2-2/ Cardinal d'un produit cartésien

2-3/ Nombre d'applications d'un ensemble à un autre

2-4/ Nombre de parties d’un ensemble

III- Techniques de dénombrement

3-1/ Arrangements avec répétition

3-2/ Arrangements sans répétition

3-3/ Permutations d'un ensemble fini

3-4/ Combinaisons d'un ensemble fini

3-5/ Formule du binôme de newton

I- Ensemble fini - Cardinal d'un ensemble fini

1-1/ Ensemble fini

Définition

Un ensemble $E$ non vide est un ensemble fini s'il existe un entier naturel $n$ tel qu'il existe une bijection de $\{1, 2, . . ., n\}$ dans $E$ .

Dans ce cas, on dit que le cardinal de $E$ est $n$ , et l'on pose : $C a r d (E) = n$

Le cardinal de l'ensemble vide est $0$ .

Remarques

- Dénombrer un ensemble fini non vide $E$ , c'est déterminer le cardinal de $E$ , c'est-à-dire le nombre de ses éléments.

La définition précédente n'est pas rigoureuse puisqu'elle repose sur la notion intuitive de nombre d'éléments sans définir précisément celle-ci.

- Dans la pratique, on dénombre un ensemble fini non vide $E$ à l’aide des entiers naturels non nuis en attribuant successivement un numéro à chacun des éléments de $E$ . Le dernier entier utilisé est alors le cardinal de $E$ . On dit alors que l'on compte les éléments de $E$ .

- Trois conditions doivent être remplies pour que le dénombrement de E soit correct :

il ne faut compter que les éléments de $E$ ;
il ne faut pas en oublier ;
il ne faut pas compter certains éléments plusieurs fois.

Applications

On considère l'ensemble $A = \{E (\frac{11}{n}) / n \in ℕ *\}$ .

Montrer que l'ensemble $A$ est fini et déterminer son cardinal.

Soit $A$ et $B$ deux ensembles finis, et on pose : $n = C a r d B$

Soit $f$ une application surjective de $A$ sur $B$ telle que pour tout $b \in B$ : $C a r d f^{- 1} (\{b\}) = m$

Montrer que : $C a r d A = m n$

1-2/ Propriétés du calcul sur les cardinaux

Proposition

1) Si $A$ et $B$ sont deux ensembles finis, alors les ensembles $A \cup B$ et $A \cap B$ sont finis et de plus :

$C a r d (A \cup B) = C a r d A + C a r d B - C a r d (A \cap B)$

En particulier, si $A$ et $B$ sont disjoints, on a : $C a r d (A \cup B) = C a r d A + C a r d B$

2) Tout sous-ensemble $A$ d'un ensemble fini $E$ est un ensemble fini, et de plus :

$C a r d A \leq C a r d E$ et $C a r d (C_{E}^{A}) = C a r d E - C a r d A$

Remarques

- Si $A \subset E$ et $C a r d A = C a r d E$ , alors : $A = E$

- Si $A_{1}, A_{2}, . . . ., A_{n}$ sont des ensembles finis et deux à deux disjoints, alors :

$C a r d (A_{1} \cup A_{2} \cup . . . . \cup A_{n}) = {\sum C a r d (A_{i})}_{i = 1}^{n}$

Applications

Dans une classe de 38 élèves, on sait que :

31 étudient l'anglais, 24 l'espagnol et17 l'allemand ;
12 étudient à la fois l'anglais et l'allemand ;
9 étudient l'espagnol et l'allemand ;
4 étudient les trois langues simultanément.

Quel est le nombre d'élèves :

a) étudiant l'anglais et l'espagnol ;
b) étudiant l'anglais ou l'espagnol ;
c) étudiant uniquement l'allemand ;
d) étudiant l'allemand et l'anglais, mais pas l'espagnol ;
e) étudiant l'allemand ou l'anglais, mais pas l'espagnol.

On considère l'ensemble $E = \{a_{p}; a_{p + 1}; . . .; a_{n}\}$ où $0 \leq p \leq n$ et $a_{p}; a_{p + 1}; . . .; a_{n}$ sont deux à deux distincts.

Calculer le cardinal de l'ensemble $E$ .

Soit $A$ , $B$ et $C$ trois ensembles finis.

Montrer que :

$C a r d (A \cup B \cup C) = C a r d (A) + C a r d (B) + C a r d (C) - C a r d (A \cap B) - C a r d (B \cap C) - C a r d (A \cap C) + C a r d (A \cap B \cap C)$

II- Principe fondamental de dénombrement - Cardinal d'un produit cartésien

2-1/ Principe fondamental du dénombrement

Proposition

Si une situation de dénombrement nécessite $p$ choix $C_{1}, C_{2}, . . ., C_{p}$ et si :

le choix $C_{1}$ peut produire $n_{1}$ résultats possibles ;
le choix $C_{2}$ peut produire $n_{2}$ résultats possibles ;
et ainsi de suite ;

Alors la situation de dénombrement peut se faire de $n_{1} \times n_{2} \times . . . \times n_{p}$ manières différentes.

Applications

On considère les£chiffres suivants : 5 - 6 - 7 - 2 - 3

On veut former des entiers naturels de trois chiffres distincts parmi ces chiffres.

a- Quel est le nombre de cas possibles ?

b- Combien de nombres paires peut-on former ?

c- Combien des multiples de 5 peut-on former ?

Soit $E$ un ensemble fini non vide et $f$ une application surjective de $E$ dans $\{0; 1\}$ .

Montrer que si $f^{- 1} (\{1\}) = f^{- 1} (\{0\})$ , alors le cardinal de $E$ est pair.

2-2/ Cardinal d'un produit cartésien

Proposition

Soit $E$ et $F$ deux ensembles finis et non vides.

Alors : $C a r d (E \times F) = C a r d E \times C a r d F$

Applications

Quel est le nombre de numéros des téléphones mobiles qui commence par 061 ?

Soit $E_{i}$ avec ensemble non vide $(n \in ℕ *)$ .

Montrer par récurrence que :

$C a r d (E_{1} \times E_{2} \times . . . \times E_{n}) = (C a r d E_{1}) \times (C a r d E_{2}) \times . . . . \times (C a r d E_{n})$

2-3/ Nombre d'applications d'un ensemble à un autre

Proposition

Soit $E$ et $F$ deux ensembles finis et non vides. tels que $C a r d E = p$ et $C a r d F = n$ .

Le nombre d'applications de $E$ dans $F$ est : ${(C a r d F)}^{C a r d E} = n^{p}$

Applications

On considère les ensembles suivants : $E = \{x \in ℕ / 5 < x < 16\}$ et $F = \{x \in ℤ / |x| < 5\}$

Calculer le nombre d'applications de $E$ dans $F$ .

On lance un dé cubique dont les faces sont numérotées de 1 à 6 trois fois de suite, on obtient un triplet $(a; b; c)$ à l'issue des trois lancers.

a- Déterminer le nombre de triplets comportant uniquement des chiffres impairs.

b- Déterminer le nombre de triplets comportant des chiffres deux à deux distincts.

c- Déterminer le nombre de triplets comportant au moins une fois le chiffre 1.

2-4/ Nombre de parties d’un ensemble

Proposition

Soit $E$ un ensemble fini de cardinal $n$ et $P (E)$ l'ensemble des parties de $E$ .

Alors : $C a r d P (E) = 2^{n}$

III- Techniques de dénombrement

3-1/ Arrangements avec répétition

Définition

Soit $E$ un ensemble fini non vide de cardinal $n \geq 1$ et $p \in ℕ *$ .

Tout élément $(x_{1}; x_{2}; . . .; x_{p})$ du produit cartésien $E \times E \times . . . \times E = E^{p}$ s'appelle un arrangement avec répétition de $p$ éléments de $E$ (ou une p-liste de $E$ ).

Situation caractéristique

Un arrangement avec répétition de $p$ éléments peut s'interpréter comme un tirage de $p$ boules, une à une (successivement), avec remise, dans une urne en contenant n boules (l'ordre compte).

Nous sommes donc dans un cas où l'ordre dans lequel les éléments sont choisis intervient et où les répétitions sont autorisées.

Proposition

Soit $E$ un ensemble fini non vide de cardinal $n \geq 1$ et $p \in ℕ *$ .

Le nombre d'arrangements avec répétition de $p$ éléments de $E$ est : $n^{p}$

3-2/ Arrangements sans répétition

Définition

Soit $E$ un ensemble fini non vide de cardinal $n \geq 1$ et $p \in ℕ *$ tel que $1 \leq p \leq n$ .

Tout élément $(x_{1}; x_{2}; . . .; x_{p})$ du produit cartésien $E \times E \times . . . \times E = E^{p}$ tel que les éléments $x_{1}; x_{2}; . . .; x_{p}$ sont deux à deux distincts s'appelle un arrangement sans répétition de $p$ éléments dans $E$ .

Situation caractéristique

Un arrangement sans répétition de $p$ éléments parmi $n$ éléments peut s'interpréter comme un tirage de $p$ boules, une à une (successivement), sans remise, dans une urne en contenant $n$ (l'ordre compte).

Nous sommes donc dans un cas où l'ordre dans lequel les éléments sont choisis intervient et où les répétitions ne sont pas autorisées.

Proposition

Soit $E$ un ensemble fini non vide de cardinal $n \geq 1$ et $p \in ℕ *$ tel que $1 \leq p \leq n$ .

Le nombre d'arrangements sans répétition de $p$ éléments de $E$ est le nombre noté $A_{n}^{p}$ donné par :

$A_{n}^{p} = n (n - 1) (n - 2) . . . (n - p + 1)$

Remarques

Soit $E$ et $F$ deux ensembles finis comportant respectivement $p$ et $n$ éléments $(1 \leq p \leq n)$ .

$E = \{a_{1}; a_{2}; . . .; a_{p}\}$ et $F = \{b_{1}; b_{2}; . . .; b_{n}\}$

Se donner une application injective de $E$ dans $F$ revient à se donner une p-liste d'éléments distincts de $F$ formée par les images respectives de $a_{1}; a_{2}; . . .; a_{p}$ .

Le nombre d'applications injectives d'un ensemble $E$ à $p$ éléments dans un ensemble $F$ à $n$ éléments est alors :

$A_{n}^{p} = \frac{n!}{(n - p)!} = n (n - 1) (n - 2) . . . (n - p + 1)$

Applications

Une urne contient 10 boules noires numérotées de 1 à 10, cinq boules blanches numérotées de 11 à 15, et trois boules rouges numérotées de 16 à 18.

On tire cinq boules successivement sans remise.

Quel est le nombre de séries de tirages possibles ?

Quel est le nombre de séries de tirages commençant par une boule rouge et composés uniquement de boules "paires" ?

3-3/ Permutations d'un ensemble fini

Définition

Soit $E$ un ensemble fini non vide de cardinal $n \in ℕ *$ .

On appelle permutation de E toute bijection de $E$ dans $E$ .

Autrement dit, une permutation est un arrangement sans répétition de tous les éléments de $E$ .

Situation caractéristique

Une permutation d'un ensemble à $n$ éléments peut s'interpréter comme un tirage de $n$ boules, une à une (successivement), sans remise, dans une urne en contenant $n$ (l'ordre compte).

Nous sommes donc dans un cas où l'ordre dans lequel les éléments sont choisis intervient et où les répétitions ne sont pas autorisées.

Proposition

Soit $E$ un ensemble fini non vide de cardinal $n \in ℕ *$ .

Le nombre de permutations des éléments de $E$ est le nombre noté $n!$ « se lit : factoriel n », et défini par :

$n! = n \times (n - 1) \times (n - 2) \times . . . \times 2 \times 1$

Remarques

- On convient que $0! = 1$ et $A_{n}^{0} = 1$ .

- On a pour tout $(n; p) \in ℕ^{2}$ tel quel $1 \leq p \leq n$ : $A_{n}^{p} = \frac{n!}{(n - p)!}$

En particulier, on a $A_{n}^{1} = n$ et $A_{n}^{n} = n!$ .

Applications

On dispose de quatre couleurs : vert, jaune, rouge et bleu pour colorier les quatre cases du motif suivant avec des couleurs distinctes :

Combien de coloriages différents sont possibles ?

3-4/ Combinaisons d'un ensemble fini

Définition

Soit $E$ un ensemble fini non vide de cardinal $n \geq 1$ et $p \in ℕ *$ tel que $p \leq n$ .

Une combinaison de $p$ éléments pris parmi les $n$ éléments de $E$ est une partie dont le cardinal est $p$ .

Situation caractéristique

Une combinaison de $p$ éléments parmi $n$ éléments peut s'interpréter comme un tirage de $p$ boules, de manière simultanée, dans une urne en contenant $n$ (l'ordre ne compte pas).

Nous sommes donc dans un cas où l'ordre dans lequel les éléments sont choisis n'a pas d'importance et où les répétitions ne sont pas autorisées.

Proposition

Le nombre de combinaisons de $p$ éléments pris parmi $n$ éléments distincts est le nombre d'ensembles de $p$ objets pris parmi les $n$ objets de départ.

Ce nombre est noté $C_{n}^{p}$ , et on a : $C_{n}^{p} = \frac{A_{n}^{p}}{p!} = \frac{n!}{p! (n - p)!}$

Proposition

Soit $n$ et $p$ deux entiers naturels tels que : $p < n$

On a les propriétés suivantes :

1) La symétrie : $C_{n}^{p} = C_{n}^{n - p}$

2) Formule de Pascal : $C_{n}^{p} + C_{n}^{p + 1} = C_{n + 1}^{p + 1}$

Triangle de pascal

La formule de Pascal permet de calculer les valeurs des (appelés coefficients binomiaux) par récurrence, en les répartissant sous forme d'un tableau triangulaire.

Pour obtenir un coefficient du tableau, on fait la somme de celui qui est au-dessus de lui, et de celui qui est à gauche de ce dernier.

3-5/ Formule du binôme de newton

Proposition

Soit $a$ et $b$ deux réels et $n$ un entier naturel non nul.

On a alors la formule suivante dite « Formule du binôme de Newton » : ${(a + b)}^{n} = \sum_{k = 0}^{n} C_{n}^{k} a^{k} b^{n - k}$

Remarques

Pour tous réels $a$ et $b$ , on a : ${(a - b)}^{n} = {(a + (- b))}^{n} = \sum_{k = 0}^{n} C_{n}^{k} {(- 1)}^{k} a^{n - k} b^{k}$

Applications

Développer :

${(a + b)}^{6}; {(a - b)}^{7}; {(a - 2 b)}^{5}; {(1 + a - b)}^{4}$

Calculer les sommations suivantes :

$\sum_{k = 0}^{n} C_{n}^{k}; \sum_{k = 0}^{n} {(- 1)}^{k} C_{n}^{k}; \sum_{k = 0}^{n} k C_{n}^{k}; \sum_{k = 0}^{n} (k + 1) C_{n}^{k}$

Quel est le coefficient de $a^{7} b^{3}$ dans le développement de ${(a - b)}^{10}$ ?

Retour