DÉNOMBREMENT
1 - PRINCIPE ADDITIF
Définition
Soit \(\text{A}\) un ensemble fini . Le nombre d'éléments de \(\text{A}\) s'appelle le cardinal de \(\text{A}\) et est noté \(Card(\text{A})\).
Propriété admise
Si \(\text{A}_{1}\), \(\text{A}_{2}\), ... \(\text{A}_n\) sont \(n\) ensembles deux à deux disjoints, alors :
\(Card(\text{A}_1 \cup \text{A}_2\cup ... \cup \text{A}_{n-1} \cup \text{A}_n)=Card(\text{A}_1)+Card(\text{A}_2)+...+Card(\text{A}_{n-1})+Card(\text{A}_n)\)
Définition - Rappel
Si \({\text{A} \cap \text{B}} = \emptyset\), on dit que les ensembles \(\text{A}\) et \(\text{B}\) sont disjoints.
Remarque
Si des ensembles forment une partition d'un autre ensemble, ils sont alors deux à deux disjoints.
Ainsi, si \(\text{A}\) est une partie d'un ensemble \(\text{E}\), alors \(Card(\overline{\text{A}})=Card(E)-Card(A)\)
Exemple : Combien y a-t-il de carrés sur la figure ci-dessous ?
On note \(E\) l'ensemble de tous ces carrés et \(\text{A}_{1}\), \(\text{A}_{2}\), \(\text{A}_{3}\) et \(\text{A}_{4}\) respectivement l'ensemble de ces carrés ayant pour côtés 1, 2, 3 et 4 carreaux.
Les sous-ensembles \(\text{A}_{1}\), \(\text{A}_{2}\), \(\text{A}_{3}\), \(\text{A}_{4}\) constituent une partition de E (puisqu'ils n'ont pas d'éléments en commun et que leur réunion est égale à E).
D'après le principe additif, on a :
\(Card(\text{E})=Card(\text{A}_{1})+Card(\text{A}_{2})+Card(\text{A}_{3})+Card(\text{A}_{4})=16+9+4+1=30\)
Remarque
Si \(\text{A}\) et \(\text{B}\) sont quelconques (c'est-à-dire pas nécessairement disjoints), alors :
2 - PRODUIT CARTÉSIEN
Définition
Soit \(\text{A}\) et \(\text{B}\) deux ensembles finis et non vides.
Le produit cartésien de \(\text{A}\) par \(\text{B}\) noté \(\text{A} \times \text{B}\) est l'ensemble des couples \((x;y)\) formés d'un élément \(x\) de \(\text{A}\) suivi d'un élément \(y\) de \(\text{B}\).
On définit de la même façon le produit cartésien de \(3, 4, ..., n\) ensembles.
Ce qui consiste à distribuer tous les éléments de \(\text{A}\) par rapport à chaque élément de \(\text{B}\).
On peut écrire : \(\text{A} \times \text{B}=\left\{ (x;y) \; | x \in \text{A} \; \text{et} \; y \in \text{B} \right\}\)
Exemple : Soit \(\text{A} = \left\{ {1;2;3} \right\}\) et \(\text{B} = \left\{ a;b \right\}\).
On a \(\text{A} \times \text{B} = \left\{ (1;a);(2;a);(3;a);(1;b);(2;b);(3;b) \right\}\) et \(\text{B} \times \text{A} = \left\{ (a,1);(a;2);(a;3);(b,1);(b;2);(b;3) \right\}\)
Remarques
-
\({\text{A} \times \text{B}} \neq {\text{B} \times \text{A}}\) : l'ordre d'un produit cartésien est important
-
Si \(\text{A} = \emptyset\) ou \(\text{B} = \emptyset\), alors \(\text{A} \times \text{B} = \emptyset\)
-
Le produit d'un ensemble infini par un ensemble infini est infini. (\(\mathbb{R} \times \mathbb{R} = \mathbb{R}^2\) représente l'ensemble de tous les couples de nombres réels)
Définition
Soit \(\text{A}\) est un ensemble fini et non vide et \(k\) est un entier naturel non nul.
On note :
\(\text{A}^k = \text{A} \times \text{A} \times \ldots \times \text{A}\) (\(k\) facteurs)
Les éléments de \(\text{A}^k\) sont des couples, des triplets, des quadruplets...
De façon générale, on parle de k-uplet (ou k-listes) ordonnés.
Les coordonnées dans le plan ou dans l'espace offrent de bons exemples d'emploi.
Exemple: On dispose de trois dés tétraédriques (un bleu, un rouge, un jaune) dont les faces sont marquées de 1 à 4.
On jette les trois dés et on note dans l'ordre le résultat obtenu sur le dé bleu, puis rouge, puis jaune.
Si \(\text{A} = \left\{ 1;2;3;4 \right\}\) alors , \(\text{A}^3\) est l'ensemble de tous les résultats possibles.
3 - PRINCIPE MULTIPLICATIF
Propriétés
-
Soit \(\text{A}\) et \(\text{B}\) deux ensembles finis et non vides . On a alors \(Card(A \times B)=Card(A) \times Card(B)\).
-
Soit \(\text{A}\) un ensemble fini et non vide et \(k\) un entier naturel non nul. Si \(Card(\text{A})=n\), alors \(Card(\text{A}^{k})=n^{k}\).
Résultat immédiat en utilisant la distributivité
Exemple: On reprend l'exemple précédent.
\(Card(\text{A}^{3}) = 4^{3} = 64\)
Il y a donc 64 résultats possibles pour l'expérience envisagée.
Dans la pratique, ce principe s'applique souvent en utilisant un schéma à cases :
Si une situation comporte \(k\) étapes offrant respectivement \(n_1\), \(n_2\),... ,\(n_k\) possibilités alors le nombre total d'issues est :
Exemple: Un code comporte deux lettres distinctes suivies d'un chiffre non nul. Combien peut-on former de codes distincts ?
D'après le principe multiplicatif, on a :
Lettre 1 Lettre 2 Chiffre 26 25 10 Exemple: Nombre de parties d'un ensemble à \(n\) éléments (Exemple à connaître)
Soit \(\text{A}\) un ensemble tel que \(Card(A)=n\) . Combien de parties différentes contient \(\text{A}\) ?
Il suffit pour chaque élément de se poser la question appartient-il ( noté 1 ) ou non ( noté 0 ) à la partie choisie.
D'après le principe multiplicatif, on a :
Élément 1 Élément 2 ... Élément \(n\) 2 2 ... 2 \(2 \times 2 \times \ldots \times 2 = 2^{n}\)
On peut aussi faire l'analogie avec le nombre d'entiers écrits en binaire sur \(n\) bits:
\[\overbrace{1010...001}^{n \text{bits}}\]
4 - ARRANGEMENTS ET PERMUTATIONS
Définition
Soit un ensemble \(\text{A}\) de cardinal \(n\) et un entier \(k \leqslant n\).
Un arrangement de \(k\) éléments choisis parmi \(n\) est un \(k\)-uplet d'éléments distincts de \(\text{A}\).
Exemple : Soit un ensemble \(\text{A} = \left\{ 1;2;3;4;5;6 \right\}\)
Un arrangement de 3 éléments de \(\text{A}\) sera par exemple \((1;4;2)\) ou \((1;6;3)\).
\((1;4;4)\) n'est pas un arrangement, c'est un 3-uplet (un triplet) dont les éléments qui le composent ne sont pas distincts.
Propriété
Soit un ensemble \(\text{A}\) de cardinal \(n\) et un entier \(k \leqslant n\).
Le nombre d'arrangements de \(k\) éléments de \(\text{A}\) est :
On le note \(\text{A}_{n}^{k}\).
\(\text{A}_{n}^{k}\) est le produit de \(k\) entiers consécutifs décroissants à partir de \(n\).
Preuve :
Ce résultat se montre facilement avec un schéma à cases :
D'après le principe multiplicatif, si on compte le nombre de possibilités pour chaque élément, on a :
| Élément 1 | Élément 2 | ... | Élément \(k\) |
|---|---|---|---|
| \(n\) | \(n-1\) | ... | \(n-k+1\) |
Exemple : \(\text{A}_{8}^{3} = 8 \times 7 \times 6 = 336\)
Remarque
On utilise les arrangements en cas de choix successifs de \(p\) éléments pris parmi \(n\), sans répétition.
Définition
Soit un ensemble \(\text{A}\) de cardinal \(n\).
Une permutation de \(\text{A}\) est un arrangement de \(\text{E}\) ayant \(n\) éléments.
Exemple : Soit un ensemble \(\text{A} = \left\{ 1;2;3;4;5;6 \right\}\)
\((1;3;2;6;5;4)\) et \((6;5;4;2;1;3)\) sont deux permutations de \(\text{A}\).
Définition
On note \(n!\) (lire « factorielle n » ) le produit des \(n\) premiers entiers naturels non nuls.
Par convention, on pose \(0! = 1\).
On a alors \(\text{A}_{n}^k=\dfrac{n!}{(n - k)!}\)
Propriété
Soit un ensemble \(\text{A}\) de cardinal \(n\).
Le nombre de permutations de \(\text{A}\) est \(n!\).
Immédiat, car une permutation est un arrangement de \(\text{A}\) ayant \(n\) éléments.
Remarques
On utilise les permutations dans les cas où on veut ordonner tous les éléments d'un ensemble sans répétition.
5 - COMBINAISONS
Définition
Soit \(\text{A}\) un ensemble de cardinal \(n\).
Une partie à \(k\) éléments de \(\text{A}\) est une combinaison de \(k\) éléments de \(\text{A}\).
Exemple : Soit un ensemble \(\text{A} = \left\{ 1;2;3;4;5;6 \right\}\)
\(\left\{ 2;5;6 \right\}\) et \(\left\{ 1;4;5 \right\}\) sont deux combinaisons à 3 éléments de \(\text{A}\).
Remarque
Le fait d'utiliser des accolades signifie que l'ordre d'écriture n'est pas important.
Propriété
Soit un ensemble \(\text{A}\) de cardinal \(n\) et un entier \(k \leqslant n\).
Le nombre de combinaisons de \(k\) éléments de \(\text{A}\) est :
\(\dfrac{n \times (n - 1) \times \ldots \times (n - k + 1)}{k!} = \dfrac{n!}{(n - k)! \; k!}\)
On le note \(\begin{pmatrix} n \\ k \end{pmatrix}\) (notation que nous utiliserons) ou parfois \(\text{C}_{n}^{k}\).
\(\begin{pmatrix} n \\ k \end{pmatrix}\) se lit " \(k\) parmi \(n\) ".
On l'appelle coefficient binomial.
Preuve :
Dénombrons les arrangements de \(k\) éléments d'un ensemble fini \(\text{A}\) de cardinal \(n\).
Un arrangement est caractérisé par :
-
Le choix d'une partie de \(\text{A}\) à \(k\) éléments (il y a \(\begin{pmatrix} n \\ k \end{pmatrix}\) choix de telles parties)
-
La façon d'ordonner les \(k\) éléments de la partie choisie ( il y a \(k!\) façons)
On en déduit que : \(\text{A}_{n}^{k} = {k!}\begin{pmatrix} n \\ k \end{pmatrix} \Leftrightarrow \begin{pmatrix}n \\ k \end{pmatrix} = \dfrac{\text{A}_{n}^k}{k!}\)
Exemple : Soit un ensemble \(\text{A} = \left\{ 1;2;3;4;5;6 \right\}\)
Il y a \(\begin{pmatrix} 6 \\ 3 \end{pmatrix} = \dfrac{6!}{3!3!} = 20\) combinaisons à 3 éléments de \(\text{A}\).
Remarques
L'ensemble des parties d'un ensemble \(\text{A}\) à \(n\) éléments est constitué des parties à 0 élément, 1 élément, 2 éléments, ..., \(n\) éléments.
Ainsi le nombre de parties de \(\text{A}\) est \(\sum\limits_{k = 0}^{n}\begin{pmatrix} n \\ k \end{pmatrix}\). Or nous avons déjà vu que le nombre de parties de \(\text{A}\) est \(2^{n}\).
On en déduit que \(\sum\limits_{k = 0}^{n}\begin{pmatrix} n \\ k \end{pmatrix}=2^{n}\)
Propriété
-
Pour tout entier naturel \(n\), et pour tout entier \(k\) tel que \(0 \leq k \leq n\), on a : \(\begin{pmatrix} n \\ k \end{pmatrix}=\begin{pmatrix} n \\ {n-k} \end{pmatrix}\)
-
De plus, si \(n \geq 1\) et \(1 \leq k \leq n-1\) , alors : \(\begin{pmatrix} n + 1 \\ k + 1 \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k + 1 \end{pmatrix}\)
Preuve : deuxième point exigible
Pour chacune de ces propriétés, deux démonstrations sont proposées : une démonstration par le calcul et une démonstration par une méthode combinatoire.
Démonstration par une méthode combinatoire :
\(\begin{pmatrix} n \\ k \end{pmatrix}\) représente le nombre parties de \(k\) éléments d'un ensemble A à \(n\) éléments.
Or, à chaque partie on peut associer de façon unique une autre partie : son complémentaire.
Et le complémentaire d'une partie à \(k\) éléments comporte \(n-k\) éléments.
Donc dénombrer les parties à \(k\) éléments revient à dénombrer les parties complémentaires à \(n-k\) éléments et il y en a \(\begin{pmatrix} n \\ n - k \end{pmatrix}\).
Démonstration par le calcul :
\(\begin{pmatrix} n \\ n - k \end{pmatrix}=\dfrac{n!}{(n-k)!(n-(n-k))!} = \dfrac{n!}{(n-k)!k!}=\begin{pmatrix} n \\ k \end{pmatrix}\)
Démonstration par une méthode combinatoire :
Soit \(\text{A}\) un ensemble à \(n + 1\) éléments avec \(n \geqslant 1\).
Soit \(a\) un élément fixé de \(\text{A}\). Remarquons que les parties à \(k + 1\) éléments de \(\text{A}\) se partagent en deux catégories :
-
celles ne contenant pas \(a\) (il y en \(\begin{pmatrix} n \\ k + 1 \end{pmatrix}\) ), car fabriquer une telle partie revient à choisir \(k + 1\) éléments parmi \(n\).
-
celles contenant \(a\) (il y en a \(\begin{pmatrix} n \\ k \end{pmatrix}\) ), car fabriquer une telle partie revient à choisir \(k\) éléments parmi \(n\).
Or ces deux catégories constituent une partition de l'ensemble des parties à \(k\) éléments de \(\text{A}\).
D'après le principe additif, on a donc : \(\begin{pmatrix}n + 1 \\ k + 1 \end{pmatrix}=\begin{pmatrix}n \\k \end{pmatrix} + \begin{pmatrix} n \\ k + 1 \end{pmatrix}\)
Démonstration par le calcul :
\(\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ {k + 1} \end{pmatrix}=\dfrac{n!}{k!(n - k)!} + \dfrac{n!}{(k + 1)!{(n - k - 1)!}}\)
\(\phantom{\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ {k + 1} \end{pmatrix}}=\dfrac{(n + 1)!}{(k + 1)!(n - k)!} \times \left({\dfrac{k + 1}{n + 1} + \dfrac{n - k}{n + 1}}\right)\)
\(\phantom{\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ {k + 1} \end{pmatrix}}=\dfrac{(n + 1)!}{(k + 1)!(n - k)!} \times \dfrac{n + 1}{n + 1}\)
\(\phantom{\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ {k + 1} \end{pmatrix}}=\dfrac{(n + 1)!}{(k + 1)!(n - k)!}\)
\(\phantom{\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ {k + 1} \end{pmatrix}}=\dfrac{(n + 1)!}{(k + 1)!(n+1 - (k+1))!}\)
\(\phantom{\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ {k + 1} \end{pmatrix}}=\begin{pmatrix} {n + 1} \\ {k + 1} \end{pmatrix}\)
6 - TRIANGLE DE PASCAL
La deuxième formule permet de calculer les nombres \(\left(\begin{matrix} n \\ k \end{matrix}\right)\) de proche en proche en formant le tableau suivant appelé triangle de Pascal.
-
\(\begin{pmatrix} n \\ k \end{pmatrix}\) n'est différent de \(0\) que pour \(k \leqslant n\) ; on ne remplit donc pas les cases situées au-dessus de la diagonale.
-
Tous les nombres de la diagonale sont obtenus en utilisant le résultat \(\begin{pmatrix} n \\ n \end{pmatrix}=1\).
-
Tous les nombres de la première colonne sont obtenus en utilisant la formule \(\begin{pmatrix} n \\ 0 \end{pmatrix}=1\).
-
Tous les autres nombres sont obtenus en utilisant le résultat :
« Tout nombre du tableau est la somme du nombre placé au-dessus de lui et du nombre précédant ce dernier dans le tableau »
ou encore :
\[\begin{pmatrix}n + 1 \\ k + 1 \end{pmatrix}=\begin{pmatrix}n \\k \end{pmatrix} + \begin{pmatrix} n \\ k + 1 \end{pmatrix}\]