Cardinal d’ensembles
Union d’ensembles
Un ensemble \(A\) est une collection d’objets distincts que l’on appelle ses éléments.
- On dit qu’un objet \(x\) appartint à \(A\) si \(x\) est un élément de \(A\). On note \(x\in A\).
- On dit qu’un ensemble \(B\) est inclus dans \(A\) si tout élément de \(B\) est aussi un élément de \(A\). On note \(B \subset A\).
Par ailleurs, il ne faut pas confondre \(2\) et \(\{2\}\) : \(2\) désigné l’élément alors que \(\{2\}\) désigne l’ensemble qui contient un seul élément, 2. On a ainsi \(2 \in A\) et \(\{2\} \subset A\).
Soit \(A\) un ensemble ayant un nombre fini d’éléments. On appelle Cardinal de \(A\), noté \(\mathrm{Card}(A)\), \(\sharp A\) ou \(|A|\) le nombre d’éléments de \(A\).
Soit \(A\) et \(B\) deux ensembles
- L’union de \(A\) et \(B\) est l’ensemble noté \(A\cup B\) qui contient tous les éléments qui sont au moins dans l’ensemble \(A\) ou dans l’ensemble \(B\).
- L’intersection de \(A\) et \(B\) est l’ensemble noté \(A\cap B\) qui contient les éléments qui sont à la fois dans \(A\) et dans \(B\).
- Deux ensembles sont disjoints s’ils n’ont aucun élément en commun, autrement dit, \(A\cap B = \varnothing\).
Soit \(n\) un entier naturel non nul et \(A_1\), \(A_2\), …, \(A_n\) des ensembles deux à deux disjoints.
\[ \mathrm{Card}(A_1 \cup A_2 \cup \ldots \cup A_n)= \mathrm{Card}(A_1) + \mathrm{Card}(A_2)+\ldots + \mathrm{Card}(A_n)= \sum_{i=1}^n \mathrm{Card}(A_1)\]
Produit cartésien
Soit \(A\) et \(B\) deux ensembles.
- On appelle produit cartésien de \(A\) et \(B\), noté \(A \times B\) (\(A\) « croix » \(B\)), l’ensemble composé des couples \((a;b)\) avec \(a \in A\) et \(b \in B\).
- Le produit cartésien \(A\times A\) est également noté \(A^2\).
- Les éléments de \(A \times B\) sont \((2;3)\), \((2;5)\), \((5;3)\), \((5;5)\), \((9;3)\) et \((9;5)\).
- Les éléments de \(B \times A\) sont \((3:2)\), \((3;5)\), \((3;9)\), \((5;2)\), \((5;5)\), \((5;9)\).
- Les éléments de \(B^2\) sont \((3;3)\), \((3;5)\), \((5;3)\) et \((5;5)\).
La notion de produit cartésien s’étend naturellement à plus de deux ensembles.
- Soit \(n\) un entier naturel supérieur ou égal à 2. le produit cartésien de \(n\) ensembles \(A_1\), \(A_2\), …, \(A_n\) est l’ensemble des \(n\)-uplets \((a_1;a_2;\ldots;a_n)\) avec \(a_1 \in A_1\), \(a_2 \in A_2\), … \( a_n \in A_n\).
- Le produit cartésien \(A \times A \times … \times A\) où \(A\) apparaît \(n\) fois est noté \(A^n\). Ses éléments sont appelés les \(n\)-uplets de \(A\).
Exemple : On considère les ensembles \(A=\{1;2;4\}\), \(B=\{3;7;14\}\) et \(C=\{1;3\}\).
- \((1;7;3) \in A \times B \times C\) puisque \(1 \in A\), \(7 \in B\) et \(3 \in C\).
- \((3;7;7;3;14) \in B^5\) puisque \(3\), \(7\) et 14 sont dans l’ensemble \(B\).
La notion de produit cartésien s’étend également à des ensembles infinis. Par exemple, \((1; \pi) \in \mathbb{N} \times \mathbb{R}\).
Le terme de produit cartésien doit son nom au mathématicien René Descartes. Celui-ci est en effet le premier à avoir décrit les points du plan à l’aide de leurs coordonnées dans un repère : un point est ainsi décrit par un couple de réels \((x;y)\) de \(\mathbb{R} \times \mathbb{R}\), ou tout simplement \(\mathbb{R}^2\). De la même manière, les points de l’espace sont décrits par un triplet \((x;y;z) \in \mathbb{R}^3\).
Soit \(A\) et \(B\) des ensembles finis.
- \(\mathrm{Card} (A \times B)=\mathrm{Card}(A) \times \mathrm{Card} (B)\).
- Plus généralement, soit \(n\) un entier naturel, \(A_1\), \(A_2\), …, \(A_n\) des ensembles finis. \[\mathrm{Card}(A_1 \times A_2 \times \ldots \times A_n)=\mathrm{Card}(a_1) \times \mathrm{Card}(A_2) \times \ldots \times \mathrm{Card}(A_n)\]
- En particulier, \(\mathrm{Card}(A^n)=[\mathrm{Card}(A)]^n\).
On traduit ainsi le fait que si l’on souhaite construire un élément \((a_1;a_2;\ldots;a_n)\) de l’ensemble \(A_1 \times A_2 \times \ldots \times A_n\), on a \(\mathrm{Card}(A_1)\) choix pour \(a_1\), \(\mathrm{Card}(A_2)\) choix pour \(a_2\) etc.
Exemple : On reprend les ensembles \(A=\{1;2;4\}\), \(B=\{3;7;14\}\) et \(C=\{1;3\}\).
- \(\mathrm{Card}(A \times B)= 3 \times 3 = 9\)
- \(\mathrm{Card}(A \times B \times C) = 3 \times 3 \times 2 = 18\)
- \(\mathrm{Card}(A^4)=3^4=81\)
- \(\mathrm{Card}(C^{10})=2^{10}=1024\)
Le produit cartésien est utilisé pour dénombrer des situations où l’ordre des symboles (chiffres, lettres, signes…) est important et où ces symboles peuvent être utilisés plusieurs fois.
- Pour les chiffres, on a 6 choix possibles pour le prmier, 6 pour le deuxième, 6 pour le troisième et 6 pour le quatrième, soit \(6\times 6 \times 6 \times 6 = 6^4 = 1296\) possibilités
- Pour les lettres, il y a 4 choix pour la première et 4 pour la seconde soit \(4 \times 4 = 16\) possibilités.
- En tout, il y a donc \(1296 \times 16 = 20736\) digicodes possibles
Formellement, si l’on note \(A_1=\{1;2;3;4;5;6\}\) et \(A_2=\{A;B;C;D\}\), un digicode est un élément de \(A_1^4 \times A_2 ^2\). Son cardinal est donc \(\mathrm{Card}(A_1)^4 \times \mathrm{Card}(A_2)^2 = 6^4 \times 4^2 = 20736\).
Arrangements et permutations
Soit \(n\) un entier naturel non nul. On note \(n!\) (factorielle de \(n\)) le produit de tous les entiers de 1 à \(n\) \[n!=n\times (n-1) \times \ldots \times 2 \times 1\]
Par ailleurs, on convient que \(0!=1\).
Soit \(A\) un ensemble fini de cardinal \(n\) et \(k\) un entier inférieur ou égal à \(n\). Un \(k\)-arrangement de \(A\) est un \(k\)-uplet d’éléments distincts de \(A\).
Lorsque \(k=n\), on parle de permutation de \(A\).
- \((7;10;3)\) est un 3-arrangement de \(A\).
- \((10;5;4;1)\) est un 4-arrangement de \(A\).
- En revanche, \((7;10;1;7)\) n’est pas un arrangement de \(A\) car l’élément \(7\) y apparaît deux fois.
- \((3;7;4;5;1;10)\) est par ailleurs une permutation de \(A\) puisque tous les éléments de \(A\) y apparaissent.
Soit \(A\) un ensemble fini de cardinal \(n\) et \(k\) un entier inférieur ou égal à \(n\). Le nombre de \(k\)-arrangements de \(A\) vaut \(\dfrac{n!}{(n-k)!}\).
En particulier, le nombre de permutation de \(A\) vaut \(n!\).
- \(n\) choix pour le premier élément
- \(n-1\) choix pour le deuxième
- …
- \(n-(k+1)\) pour le \(k\)-ième
Le nombre de \(k\) arrangements de \(A\) vaut donc \(n \times (n-1) \times \ldots \times n-(k+1)\), ce que l’on peut réécrire en
\[ n \times (n-1) \times \ldots \times n-(k+1) \times \dfrac{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}=n \times (n-1) \times \ldots \times n-(k+1) \times \dfrac{(n-k)!}{(n-k)!}\]
d’où
\[n \times (n-1) \times \ldots \times n-(k+1) \times \dfrac{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}=\dfrac{n!}{(n-k)!}\]
Les arrangements sont utilisés pour dénombres des situations où l’ordre des objets (chiffres, nombres, lettres, signes,…) est important mais où chaque objet ne peut être utilisé qu’une seule fois.
- On a 8 choix pour le premier cheval arrivé
- Il reste 7 choix pour le deuxième, 6 pour le troisième et 5 pour le quatrième.
- Le nombre total de paris est donc \(8 \times 7 \times 6 \times 5 = 1680\).
Formellement, si on nomme \(A\) l’ensemble des chevaux de la course, un quarté dans l’ordre est un 4-arrangement de \(A\).
Prenons au hasard et de manière uniforme 23 personnes nées en 2019. Pour simplifier, on suppose que leur date de naissance est également uniforme sur l’année. Quelle est la probabilité que deux personnes parmi ces 23 soient nées le même jour ?
Nous allons plutôt, pour répondre à cette question, nous intéresser à l’événement complémentaire : quelle est la probabilité que tout le monde soit né un jour différent ?
Puisque les personnes sont choisies au hasard et que la date de naissance est supposée uniforme, il suffit d’utiliser la formule \(\dfrac{\text{Nombre de cas favorables}}{\text{Nombre de cas total}}\).
- Un cas est ici favorable lorsque les dates de naissances des 23 personnes sont différentes. Le nombre de cas favorables est donc le nombre de 23-arrangements de l’ensemble des jours (365 éléments). Il y en a \(\dfrac{365!}{(365-23)!}\) soit \(\dfrac{365!}{342!}\).
- Le nombre de cas total est un 23-uplet de l’ensemble des jours : chaque personne a une date de naissance, sans restriction. Il y en a donc \(365^{23}\).
Ainsi, la probabilité que tout le monde soit né un jour différent vaut \(\dfrac{365!}{342! \times 365^{23}}\simeq 0.4927\). En passant au complémentaire, il y a donc \(50,73\%\) de chances que, dans un groupe de 23 personnes prises au hasard, au moins deux personnes soient nées le même jour !
Combinaisons d’un ensemble fini
Une partie ou combinaison d’un ensemble fini \(A\) est un ensemble inclus dans \(A\). L’ensemble des parties de \(A\) est noté \(\mathcal{P}(A)\).
Si \(A\) est de cardinal \(n\), le nombre de parties de \(A\) est \(2^n\).
Pour cela, à chaque partie de \(A\), on fait correspondre un élément de \(\{0;1\}^n\) de telle sorte que deux parties différentes de \(A\) sont associés à deux \(n\)-uplets différents de \(\{0;1\}\). On dit qu’on réalise une bijection entre \(\mathcal{P}(A)\) et \(\{0;1\}^n\).
L’idée : Pour chaque élément de \(A\), on a deux choix pour construire une partie de \(A\) : soit cet élément appartient à la partie que l’on construit, soit il ne lui appartient pas. On a donc
- 2 choix pour le premier élément de \(A\)
- 2 choix pour le deuxième élément…
- …
- 2 choix pour le \(n\)-ième élément de \(A\).
Ainsi, le cardinal de \(\mathcal{P}(A)\) vaut \(2\times 2 \times \ldots \times 2 = 2^n\).
De manière formelle : Notons \(a_1\), \(a_2\) , …, \(a_n\) les éléments de \(A\).
Soit \(B\) une partie de \(A\). On construit un \(n\)-uplet \((b_0;b_1;…;b_n)\) de \(\{0;1\}\) comme suit : pour tout entier naturel \(i\) entre 1 et \(n\).
- \(b_i=1\) si \(a_i \in B\),
- \(b_1=0\) sinon.
Chaque partie de \(A\) est ainsi associé de manière unique à un \(n\)-uplet de \(\{0;1\}\) et réciproquement. Les cardinaux de \(\mathcal{P}(A)\) et \(\{0;1\}^n\) sont donc égaux.
Soit \(A\) un ensemble fini à \(n\) éléments et \(k\) un entier naturel \(n\). Le nombre de combinaisons à \(k\) éléments de \(A\) est noté \(\dbinom{n}{k}\) et se lit « \(k\) parmi \(n\) ». Les nombres \(\dbinom{n}{k}\) sont appelés coefficients binomiaux
Soit \(n\) et \(k\) deux entiers naturels.
- Si \(k > n\), \(\dbinom{n}{k}=0\)
- Sinon, \(\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}\)
On sait qu’il y a \(\dfrac{n!}{(n-k)!}\) \(k\)-arrangements de \(A\). Cependant, plusieurs \(k\)-arrangements utilisent les mêmes éléments de \(A\) (par exemple, les couples (1;2) et (2;1) utilisent les nombres 1 et 2). Etant donné une partie de \(A\) à \(k\) éléments, on peut construire \(k!\) arrangements différents : on a \(k\) choix pour le premier élément, \(k-1\) pour le deuxième, etc.
Ainsi, le nombre de \(k\)-arrangements est \(k!\) fois plus grand que la nombre de combinaisons à \(k\) éléments. Ainsi, le nombre de combinaisons à \(k\) élements est égale au nombre de \(k\)-arrangements divisé par \(k!\), soit \(\dfrac{n!}{k!(n-k)!}\).
Exemple : Soit \(A=\{1;2;3;4\}\). Le nombre de combinaisons de \(A\) à deux élémens vaut \(\dbinom{4}{2}=\dfrac{4!}{2!(4-2)!}=\dfrac{4!}{2!2!}=\dfrac{24}{2 \times 2}=6\). Ces combinaisons sont \(\{1;2\}\), \(\{1;3\}\), \(\{1;4\}\), \(\{2;3\}\), \(\{2;4\}\) et \(\{3;4\}\).
Les combinaisons sont utilisées pour dénombrer les situations où l’ordre des objets n’est pas important – lorsque l’on tire simultanément plusieurs personnes par hasard – et qu’un objet ne peut être utilisé qu’une seule fois.
L’ordre de distribution des cartes n’a pas d’importance ici : recevoir un as en première carte ou en deuxième carte n’a pas d’influence, on utilise donc les combinaisons.
- La main est composée de 2 as, choisis parmi 4, ce qui donne \(\dbinom{4}{2}=\dfrac{4!}{2!(4-2)!}=\dfrac{4!}{2!2!}=\dfrac{24}{4}=6\) possibilités
- Il reste 3 cartes à déterminer, choisis parmi les 28 cartes qui ne sont pas des as. Cela donne \(\dbinom{28}{3}=\dfrac{28!}{3!(28-3)!}=\dfrac{28!}{3!25!}=\dfrac{28\times 27 \times 26}{3 \times 2 \times 1}=3276\)
- Au total, cela fait \(6\times 3276 =19656\) mains de 5 cartes contenant exactement 2 as.
Soit \(n\) un entier naturel non nul.
- Pour tout entier naturel \(k \leqslant n\), \(\dbinom{n}{k}=\dbinom{n}{n-k}\)
- \(\dbinom{n}{0}=\dbinom{n}{n}=1\)
- Si \(n\geqslant 1\), \(\dbinom{n}{1}=\dbinom{n}{n-1}=n\)
- Si \(n\geqslant 2\), \(\dbinom{n}{2}=\dbinom{n}{n-2}=\dfrac{n(n-1)}{2}\)
Démonstration avec la formule :
- Pour tout entier naturel \(k\leqslant n\), \(\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}=\dfrac{n!}{(n-k)!(n-(n-k))!}=\dbinom{n}{n-k}\).
- D’après le premier point, on a bien \(\dbinom{n}{0}=\dbinom{n}{n-0}=\dbinom{n}{n}\). Or, \(\dbinom{n}{0}=\dfrac{n!}{0!n!}=\dfrac{n!}{n!}=1\)
- D’après le premier point, on a bien \(\dbinom{n}{1}=\dbinom{n}{n-1}\).Or, \(\dbinom{n}{1}=\dfrac{n!}{1!(n-1)!}=\dfrac{n!}{(n-1)!}=\dfrac{n \times (n-1)!}{(n-1)!}=n\)
- D’après le premier point, on a bien \(\dbinom{n}{2}=\dbinom{n}{n-2}\).Or, \(\dbinom{n}{2}=\dfrac{n!}{2!(n-2)!}=\dfrac{n!}{2(n-2)!}=\dfrac{n(n-1) \times (n-2)!}{2(n-1)!}=\dfrac{n(n-1)}{2}\)
Démonstration combinatoire
- Choisir \(k\) objets parmi \(n\) revient à exclure \(n-k\) objets parmi ces \(n\) objets.Ainsi, \(\dbinom{n}{k}=\dbinom{n}{n-k}\)
- Il n’existe qu’un seul ensemble à 0 élément, il s’agit de l’ensemble vide \(\varnothing\). De la même manière, si \(A\) est un ensemble à \(n\) éléments, la seule partie de \(A\) ayant \(n\) éléments est l’ensemble \(A\) lui-même. Ainsi, \(\dbinom{n}{0}=\dbinom{n}{n}=1\)
- Si \(A\) est un ensemble fini \(\{a_1;a_2;\ldots ;a_n\}\) de cardinal supérieur ou égal à 1, les parties à 1 élément de \(A\) sont simplement les singletons \(\{ a_1\}\), \(\{a_2\}\), … , \(\{a_n\}\).Ainsi, \(\dbinom{n}{1}=\dbinom{n}{n-1}=n\).
- Soit \(A\) un ensemble de cardinal \(n\geqslant 2\). Pour construire une partie à 2 éléments de \(A\), on choisit un premier élément (\(n\) choix possible) puis un second (\(n-1\) choix). En faisant ainsi, on peut construire \(n(n-1)\) couples d’éléments de \(A\). Or, l’ordre n’ayant pas d’importance, il est possible d’inverser l’ordre dans lequel on choisit les éléments de \(A\). Le nombre de combinaisons de \(A\) à 2 éléments vaut donc \(\dfrac{n(n-1)}{2}\)
Soit \(n\) un entier naturel supérieur ou égal à 2 et \(k\) un entier tel que \(1\leqslant k\leqslant n-1\). On a alors
\[ \dbinom{n-1}{k-1}+\dbinom{n-1}{k} = \dbinom{n}{k}\]
Cette relation s’appelle la relation de Pascal.
Démonstration avec la formule :
\[ \dbinom{n-1}{k-1}+\dbinom{n-1}{k}=\dfrac{(n-1)!}{(k-1)!(n-1-(k-1))!}+\dfrac{(n-1)!}{k!(n-1-k)!}\]
On multiplie le premier quotient par \(\dfrac{k}{k}\) et le second par \(\dfrac{n-k}{n-k}\), ce qui donne
\[\dbinom{n-1}{k-1}+\dbinom{n-1}{k}=\dfrac{k \times (n-1)!}{k\times (k-1)! \times (n-1)!}+\dfrac{(n-k) \times (n-1)!}{k! \times (n-k-1)! \times (n-k)}\]
Or, \(k\times (k-1)!=k!\), \((n-k-1) \times (n-k)=(n-k)!\). Ainsi,
\[\dbinom{n-1}{k-1}+\dbinom{n-1}{k} = \dfrac{k \times (n-1)!}{k!(n-k)!}+\dfrac{(n-k) \times (n-1)!}{k!(n-k)!}=\dfrac{n \times (n-1)!}{k! (n-k)!}=\dfrac{n!}{k!(n-k)!}=\dbinom{n}{k}\]
Démonstration combinatoire : Soit \(A\) un ensemble fini à \(n\) éléments et \(a\in A\). Soit \(k\) un entier naturel compris entre 1 et \(n-1\). L’ensemble des combinaisons à \(k\) éléments, noté \(\mathcal{P}_k(A)\), est, par définition, de cardinal \(\dbinom{n}{k}\). Il peut se décomposer en deux ensembles disjoints :
- \(P_1\), L’ensemble des combinaisons à \(k\) éléments de \(A\) qui contiennent l’élément \(a\). Il reste donc à choisir \(k-1\) éléments parmi les \(n-1\) restants. Le cardinal de cet ensemble est donc \(\dbinom{n-1}{k-1}\)
- \(P_2\), L’ensemble des combinaisons à \(k\) éléments de \(A\) qui ne contiennent pas l’élément \(a\). Il faut donc choisir \(k\) éléments parmi les \(n-1\) autres éléments. Le cardinal de cet ensemble est donc \(\dbinom{n-1}{k}\)
On a alors \(\mathcal{P}_k(A)=P_1 \cup P_2\) ce qui implique que \(\dbinom{n}{k} = \mathrm{Card}(\mathcal{P}_k(A))=\mathrm{Card}(P_1 \cup P_2)\). Or, les ensembles \(P_1\) et \(P_2\) sont disjoints. Ainsi, \(\mathrm{Card}(P_1 \cup P_2)= \mathrm{Card}(P_1)+\mathrm{Card}(P_2)\). Autrement dit, on a \(\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}\).
La relation de Pascal permet de construire récursivement les coefficients binomiaux. Ces coefficients peuvent être arrangés en triangle et forment ce que l’on appelle le triangle de Pascal
Dans ce triangle, on démarre avec un 1 en haut à gauche. Pour compléter chaque cellule, on ajoute alors le nombre au-dessus avec le nombre en haut à gauche. Les cases vides se voient assigner la valeur 0. On peut alors lire les coefficients binomiaux \(\dbinom{n}{k}\) dans ce triangle.
