Les notions ensemblistes
Quand on parle d'ensembles ayant un nombre fini d'éléments, on s'intéresse aux listes d'éléments que l'on peut former ainsi qu'à la façon de regrouper différents ensembles. Pour cela il existe trois opérateurs : l'union, l'intersection et le produit cartésien.
Les ensembles considérés dans ce chapitre sont finis mais les notions introduites dans cette section seront introduites dans le cas général.
L'ensemble des « couleurs » dans un jeu de 32 cartes est un ensemble fini :
{pique, cœur, carreau, trèfle}
Liste ou k-uplet
On appelle liste (d'ordre k) ou k-uplet toute suite ordonnée de k éléments d'un ensemble. On note cette liste (ou k-uplet) entre parenthèses.
Soit A le point de coordonnées (2;4) dans le plan muni d'un repère. Les coordonnées du point A forment une liste à deux éléments. On dit aussi 2-uplet ou couple.
Réunion des ensembles
Soient n un entier naturel non nul et E_1, E_2, ..., E_n des ensembles.
On appelle réunion des ensembles E_1, E_2, ..., E_n, notée E_1\cup E_2\cup ...\cup E_n, l'ensemble constitué des éléments qui appartiennent à au moins l'un des ensembles E_1, E_2, ..., E_n.
Dans un lycée, on note U l'ensemble des élèves inscrits à l'UNSS et T celui des élèves de terminale. La réunion U\cup T est l'ensemble des élèves du lycée appartenant à au moins un des deux groupes U et T.
Cet ensemble est donc constitué des élèves inscrits à l'UNSS, quelle que soit leur classe, auxquels on ajoute les élèves de terminale non inscrits à l'UNSS.
On considère les ensembles suivants :
- A : ensemble des entiers naturels inférieurs ou égaux à 20 et multiples de 2
- B : ensemble des entiers naturels inférieurs ou égaux à 20 et multiples de 3
- C : ensemble des entiers naturels inférieurs ou égaux à 20 et multiples de 5
Alors, on a :
A=\{0;2;4;6;8;10;12;14;16;18;20\}
B=\{0;3;6;9;12;15;18\}
C=\{0;5;10;15;20\}
La réunion des trois ensembles A, B et C est :
A\cup B\cup C=\{0;2;3;4;5;6;8;9;10;12;14;15;16;18;20\}
Intersection de deux ensembles
Soient A et B deux ensembles. On appelle intersection des deux ensembles A et B, notée A\cap B, l'ensemble constitué des éléments qui appartiennent aux deux ensembles A et B.
On considère les ensembles suivants :
- A : ensemble des entiers naturels inférieurs ou égaux à 20 et multiples de 2
- B : ensemble des entiers naturels inférieurs ou égaux à 20 et multiples de 3
Alors, on a :
A=\{0;2;4;6;8;10;12;14;16;18;20\}
B=\{0;3;6;9;12;15;18\}
L'intersection des ensembles A et B est :
A\cap B=\{0;6;12;18\}
Produit cartésien de deux ensembles
Soient A et B deux ensembles. Le produit cartésien des deux ensembles A et B, noté A\times B, est l'ensemble des couples (listes de 2 éléments) dont le premier élément est un élément de A et le deuxième élément un élément de B.
Le produit cartésien de l'ensemble \mathbb{R} avec lui-même, noté \mathbb{R}\times \mathbb{R}, est l'ensemble des couples de deux réels. Il s'agit donc de l'ensemble des coordonnées des points du plan muni d'un repère.
Soit un entier naturel non nul n et E_1, E_2, ..., E_n des ensembles.
Le produit cartésien de ces n ensembles, noté E_1\times E_2\times ...\times E_n, est l'ensemble des n-uplets dont le premier élément appartient à E_1, le deuxième à E_2, etc.
On considère un jeu de 32 cartes constitués des quatre « couleurs » classiques (pique, cœur, carreau, trèfle).
On note P l'ensemble des piques, C_1 l'ensemble des cœurs, C_2 l'ensemble des carreaux et T l'ensemble des trèfles.
Le produit cartésien P\times C_1\times C_2\times T est l'ensemble des 4-uplets (ou quadruplets) dont :
- le premier élément est un pique ;
- le deuxième élément est un cœur ;
- le troisième élément est un carreau ;
- le quatrième élément est un trèfle.
Soit \mathcal{A} un ensemble.
On note \mathcal{A}^k l'ensemble des k-uplets d'éléments de l'ensemble \mathcal{A}.
Le dénombrement
Que ce soit avec des ensembles de nombres, d'objets concrets ou d'objets plus abstraits, on cherche souvent à connaître le nombre d'éléments d'un ensemble (le cardinal), et les possibilités de découpage de cet ensemble en sous-parties.
Le cardinal d'un ensemble
Lorsque l'on travaille avec des ensembles ayant un nombre fini d'éléments, on est souvent amené à compter des éléments. On appelle cardinal d'un ensemble le nombre d'éléments de cet ensemble.
Cardinal d'un ensemble fini
On appelle cardinal d'un ensemble ayant un nombre fini d'éléments, le nombre d'éléments de cet ensemble.
L'ensemble des entiers naturels inférieurs ou égaux à 20 est l'ensemble :
\{0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20\}
Il compte 21 éléments. Son cardinal est donc 21.
Soient E un ensemble fini et A et B deux parties de E disjointes.
Le cardinal de la réunion de A et de B est la somme des cardinaux des parties A et B.
Soit E l'ensemble des entiers naturels non nuls inférieurs ou égaux à 50.
Soit A le sous-ensemble de E des multiples de 7 et B le sous-ensemble de E des multiples de 11.
On a :
- A=\{7;14;21;28;35;42;49\}
- B=\{11;22;33;44\}
A est de cardinal 7.
B est de cardinal 4.
Comme A et B sont disjoints, le cardinal de A\cup B est :
7+4=11
On parle du principe additif du cardinal pour la réunion de deux ensembles disjoints.
Soient A et B deux ensembles non disjoints.
Si on note \text{card}(E) le cardinal d'un ensemble E, alors :
\text{card}(A\cup B)=\text{card}(A)+\text{card}(B)-\text{card}(A\cap B)
Soient E et F deux ensembles finis de cardinaux respectifs n et p. Alors le cardinal du produit cartésien E\times F est :
\text{card}(E\times F)=n\times p
Soit E=[[ 0;9]] l'ensemble des entiers naturels compris entre 0 et 9 et soit F=[[ 0;19]] l'ensemble des entiers naturels compris entre 0 et 19.
- Le cardinal de E est 10.
- Le cardinal de F est 20.
L'ensemble E\times F est constitué des couples d'entiers dont le premier est compris entre 0 et 9 et le deuxième entre 0 et 19.
Le cardinal de E\times F est donc :
10\times 20=200
Soient p un entier naturel non nul et E_1, E_2, ...E_p p ensembles de cardinaux respectifs n_1, n_2, ..., n_p. Alors le cardinal du produit cartésien E_1\times E_2\times ...\times E_p est :
n_1\times n_2\times ...\times n_p
Soit E=[[ 1;10]] l'ensemble des entiers naturels compris entre 1 et 10.
L'ensemble E^3=E\times E\times E est l'ensemble des triplets d'entiers appartenant chacun à E.
Le cardinal de E est 10.
Le cardinal de E^3 est donc :
10^3=\text{1 000}
Le nombre de k-uplets et de sous parties
Lorsque l'on travaille avec des ensembles ayant un nombre fini d'éléments, on peut dénombrer les éléments, les listes d'éléments et les sous-parties.
Soient n un entier naturel non nul et E un ensemble de cardinal n. Soit k un entier naturel non nul. L'ensemble des k-uplets (ou k-listes) d'éléments de E, avec répétitions possibles, a pour cardinal :
n^k
On considère l'ensemble E=\{A;B;C;D;E\}.
Les « mots » de trois lettres (avec répétitions possibles) appartenant à l'ensemble E, ayant un sens ou non, sont les triplets d'éléments de E. Leur nombre est donc :
5^3=125
Soit E=\{0;1\}.
Les entiers naturels que l'on peut écrire en binaire sur un octet (huit bits) sont les octuplets, avec répétitions possibles, constitués d'éléments de l'ensemble E. Leur nombre est donc :
2^8=256
On peut donc écrire les entiers entre 0 et 255 en binaire sur un octet.
Factorielle
Soit n un entier naturel. On appelle factorielle n, notée n!, le nombre défini par :
\begin{cases}0!=1\\n!=n\times (n-1)\times (n-2)\times ...\times 1\text{ si }n>0\end{cases}
5! = 5 \times 4 \times 3 \times 2 \times 1 = 120
Soient n un entier naturel non nul et E un ensemble de cardinal n. Soit k un entier naturel compris entre 1 et n.
L'ensemble des k-uplets (ou k-listes) d'éléments de E obtenus sans répétition a pour cardinal :
\dfrac{n!}{(n-k)!} = n\times (n-1)\times...\times (n-k+1)
Soit E l'ensemble des entiers compris entre 1 et 100. L'ensemble des triplets d'éléments de E pris sans répétition est de cardinal :
\dfrac{100!}{97!} = 100\times 99\times 98=\text{970 200}
Permutation
Soient n un entier naturel non nul et E un ensemble de cardinal n. On appelle permutation de l'ensemble E tout n-uplet d'éléments de E ne comportant pas de répétition.
Soit E l'ensemble des entiers naturels compris entre 1 et 10.
(1;3;5;7;9;2;4;6;8;10) est une permutation de l'ensemble E.
Soient n un entier naturel non nul et E un ensemble de cardinal n. Le nombre de permutations de l'ensemble E est :
n! = n\times (n-1)\times (n-2)\times ...\times 1
Soit E l'ensemble des entiers naturels compris entre 1 et 10. Le nombre de permutations de l'ensemble E est :
10! = 10\times 9\times 8\times ...\times 1
Soit 3 628 800.
Soient n un entier naturel non nul et E un ensemble de cardinal n. Soit k un entier naturel non nul compris entre 0 et n. Le nombre de sous-ensembles de E à k éléments est :
\dfrac{n!}{k!(n-k)!} = \dfrac{n\times (n-1)\times (n-2)\times ...\times (n-k+1)}{k\times (k-1)\times...\times 1}
Soit E l'ensemble des élèves d'une classe de terminale en comptant 30.
Le nombre de binômes différents possibles est :
\dfrac{30!}{2!(30-2)!} = \dfrac{30!}{2!28!}
Soit :
\dfrac{30\times 29\times ...\times 2\times 1}{2\times 1\times 28\times 27\times ...\times 2\times 1}
Soit après simplification partielle :
\dfrac{30\times 29}{2\times 1} = 15\times 29 = 435
Soit n un entier naturel non nul. Soit E un ensemble de cardinal n. Le nombre de parties de E, c'est-à-dire le nombre de sous-ensembles de E, de l'ensemble vide à E tout entier, est :
2^n
Soit E=[[1;3]] l'ensemble des entiers naturels compris entre 1 et 3.
Le nombre de sous-ensembles de E est :
2^3=8
Les sous-ensembles de E sont les suivants :
\varnothing
\{1\}
\{2\}
\{3\}
\{1;2\}
\{1;3\}
\{2;3\}
\{1;2;3\}
Les coefficients binomiaux
En probabilité, lorsqu'on cherche à dénombrer des issues vérifiant un certain critère lors d'une succession d'épreuves identiques de Bernoulli, des nombres aux propriétés très particulières apparaissent, les coefficients binomiaux. On les retrouve également dans le développement de certaines expressions algébriques. Ces deux domaines a priori éloignés utilisent le même type de dénombrement.
Combinaison
Soient n un entier naturel non nul et E un ensemble à n éléments. Soit k un entier naturel compris entre 0 et n. Une combinaison de k éléments de E est une partie de E comportant k éléments.
Soit E l'ensemble des entiers naturels inférieurs ou égaux à 100.
\{1;2;3;4;5;6;7;8;9;10\} est une combinaison de E à 10 éléments.
Coefficient binomial
Soient n un entier naturel, E un ensemble de cardinal n et k un entier naturel inférieur ou égal à n. On appelle coefficient binomial le nombre lu « k parmi n », noté \binom{n}{k}, donnant le nombre de sous-ensembles de E ayant k éléments.
Soit E l'ensemble des entiers naturels compris entre 1 et 5.
\binom{5}{2} est le nombre de sous-ensembles de E comptant 2 éléments.
Les sous-ensembles possibles sont :
\{1;2\}
\{1;3\}
\{1;4\}
\{1;5\}
\{2;3\}
\{2;4\}
\{2;5\}
\{3;4\}
\{3;5\}
\{4;5\}
On a donc :
\binom{5}{2}=10
Soit n un entier naturel non nul. Dans une succession de n épreuves de Bernoulli, le nombre d'issues comptant k succès est :
\binom{n}{k}
Soient n un entier naturel et k un entier naturel inférieur ou égal à n. Le coefficient binomial \binom{n}{k} peut se calculer de la façon suivante :
\binom{n}{k}=\dfrac{n!}{k!(n-k)!}.
\binom{5}{0}=\dfrac{5!}{0!5!}=1
\binom{5}{1}=\dfrac{5!}{1!4!}=\dfrac{5}{1}=5
\binom{5}{2}=\dfrac{5!}{2!3!}=\dfrac{5\times 4}{2}=10
\binom{5}{3}=\dfrac{5!}{3!2!}=\dfrac{5\times 4}{2}=10
\binom{5}{4}=\dfrac{5!}{4!1!}=\dfrac{5}{1}=5
\binom{5}{5}=\dfrac{5!}{5!0!}=1
Soient n un entier naturel et k un entier naturel inférieur ou égal à n. Alors on a :
\binom{n}{k} = \binom{n}{n-k}
\binom{5}{2}=10
\binom{5}{3}=10
On a bien :
\binom{5}{2}= \binom{5}{3}
Soient n un entier naturel non nul et k un entier naturel inférieur ou égal à n-1. Alors on a :
\binom{n}{k}+ \binom{n}{k+1}= \binom{n+1}{k+1}
Soient n un entier naturel non nul et k un entier naturel inférieur ou égal à n-1. Alors on a :
\binom{n}{k}+ \binom{n}{k+1}=\dfrac{n!}{k!(n-k)!}+\dfrac{n!}{(k+1)!(n-k-1)!}
\binom{n}{k}+ \binom{n}{k+1}=\dfrac{(k+1)\times n!}{(k+1)!(n-k)!}+\dfrac{(n-k)\times n!}{(k+1)!(n-k)!}
\binom{n}{k}+ \binom{n}{k+1}=\dfrac{(k+1+n-k)\times n!}{(k+1)!(n-k)!}
\binom{n}{k}+ \binom{n}{k+1}=\dfrac{(n+1)\times n!}{(k+1)!(n-k)!}
\binom{n}{k}+ \binom{n}{k+1}=\dfrac{(n+1)\times n!}{(k+1)!((n+1)-(k+1))!}
\binom{n}{k}+ \binom{n}{k+1}= \binom{n+1}{k+1}
Soient n un entier naturel non nul et k un entier naturel inférieur ou égal à n-1. Soit E un ensemble de cardinal n+1. Alors on a :
\binom{n+1}{k+1} est le nombre de parties de E à k+1 éléments.
Il y a n+1 parties à n éléments dans E.
On considère une telle partie de E que l'on note A.
Pour choisir k+1 éléments dans E, on a deux possibilités :
- On choisit k éléments dans A puis on prend l'élément de E qui n'est pas dans A.
- On choisit les k+1 éléments dans A.
Pour dénombrer les parties de E à k+1 éléments, il suffit donc d'ajouter le nombre de parties de A à k éléments avec le nombre de parties de A à k+1 éléments.
Le nombre de parties de A comptant k éléments est \binom{n}{k}.
Le nombre de parties de A comptant k+1 éléments est \binom{n}{k+1}.
On obtient donc bien :
\binom{n}{k}+ \binom{n}{k+1}= \binom{n+1}{k+1}
\binom{9}{2} = 36
\binom{9}{3} = 84
\binom {9}{2}+\binom{9}{3}=36+84=120
Or \binom{10}{3}=120
On a bien :
\binom{9}{2}+\binom{9}{3}=\binom{10}{3}
Soit n un entier naturel. Alors on a :
\sum_{k=0}^{n}\binom{n}{k}=\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=2^n
Soit n un entier naturel, soient k un entier naturel inférieur ou égal à n et E un ensemble de cardinal n.
\binom{n}{k} est le nombre de parties à k éléments de E.
Par conséquent :
\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n} est la somme des nombres de parties à 0 élément, puis 1 élément, ..., jusqu'à n éléments.
C'est donc le nombre total de partie de E.
On obtient bien :
\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=2^n
\binom{5}{0}+\binom{5}{1}+\binom{5}{2}+\binom{5}{3}+\binom{5}{4}+\binom{5}{5}=2^5=32