Ensemble fini :

Définitions :
• Un ensemble E est dit fini lorsqu'il admet un nombre fini d'éléments.
• Le nombre d'éléments de E est appelé cardinal de E et est noté card(E).
• L'intersection de deux ensembles A et B est l'ensemble des éléments appartenant à la fois à A et à B et est noté A ∩ B.
• La réunion de deux ensembles A et B est l'ensemble des éléments appartenant à A ou à B et est noté A ∪ B.

Exemple :
Soit A = {2;3;5;6;7} et B = {3;4;7;8}
card(A) = 5 et card(B) = 4
A ∩ B = {3;7} , card(A ∩ B) = 2
A ∪ B = {2;3;4;5;6;7;8} , card(A ∪ B) = 7

Remarque : Le cardinal de l'ensemble vide est égal à 0 : card(Ø)=0

Principe additif :

Définition : Deux ensembles A et B sont dits disjoints s'ils n'ont aucun élément en commun (c'est à dire si A ∩ B = Ø ).

Exemple :
Soit A = {1;5} et B = {2;3;4}. A ∩ B = Ø donc A et B sont disjoints.

Propriété :
Soient A et B deux ensembles disjoints, card(A ∪ B)=card(A)+card(B).
Plus généralement, si A₁,A₂,...,A_n sont n ensembles 2 à 2 disjoints, alors :
card(A₁ ∪ A₂ ∪ ... ∪ A_n)=card(A₁)+card(A₂)+...+card(A_n)

Exemples :

1) Soit A = {1;5} et B = {2;3;4}. A ∩ B = Ø, card(A)=2 et card(B)=3 donc card(A ∪ B) = card(A)+card(B)=2+3=5.

2) Dans une classe de 26 élèves, 15 élèves pratiquent un sport, 9 élèves pratiquent un instrument de musique et 8 élèves ne pratiquent ni un sport ni un instrument de musique. Combien d'élèves pratiquent à la fois un sport et un instrument de musique?


Principe multiplicatif :

Définitions :
• Soient A et B deux ensembles finis non vides, le produit cartésien de A par B, noté A×B, est l'ensemble des couples (a,b) où a∈A et b∈B.
• Soient A, B et C trois ensembles finis non vides, le produit cartésien A×B×C est l'ensemble des triplets (a,b,c) où a∈A, b∈B et c∈C.
• Soient A₁,A₂,...,A_n n ensembles finis non vides, le produit cartésien A₁ × A₂ × ... × A_n est l'ensemble des n-uplets (a₁,a₂,...,a_n) où a₁∈A₁, a₂∈A₂, ..., a_n∈A_n.

Exemple :
• Soient A = {1;2} et B = {a;b;c}. A × B ={(1;a);(1;b);(1;c);(2;a);(2;b);(2;c)}

Remarque : on note A² le produit cartésien de A par A (A²=A×A), et plus généralement, on note Aⁿ le produit cartésien de n ensembles A.

Propriété :
Soient A₁,A₂,...,A_n n ensembles finis non vides :
card(A₁ × A₂ × ... × A_n)=card(A₁) × card(A₂) × ... × card(A_n)

Exemples :

1) Soient A = {1;2} et B = {a;b;c}. A × B ={(1;a);(1;b);(1;c);(2;a);(2;b);(2;c)}
card(A) = 2 et card(B)=3 donc card(A × B)=2×3=6

2) Soient A = {1;2}, B = {a;b} et C={X;Y;Z}. A × B× C ={(1;a;X);(1;a;Y);(1;a;Z);(1;b;X);(1;b;Y);(1;b;Z);(2;a;X);(2;a;Y);(2;a;Z);(2;b;X);(2;b;Y);(2;b;Z)}
card(A) = 2, card(B)=2 et card(C)=3 donc card(A × B× C)=2×2×3=12

3) Soit A = {1;2;3;4}. A² = {(1;1);(1;2);(1;3);(1;4);(2;1);(2;2);(2;3);(2;4);(3;1);(3;2);(3;3);(3;4);(4;1);(4;2);(4;3);(4;4)}
card(A)=4 donc card(A²)=4²=16

4) Philippe hésite pour choisir sa tenue entre 4 chemises, 3 pantalons et 2 vestes. De combien de façon différentes peut-il s'habiller?
On note C l'ensemble des chemise, P l'ensemble des pantalons, et V l'ensemble des vestes.
card(C×P×V)=card(C)×card(P)×card(V)=4×3×2=24.
Il a 24 possibilités.

Nombre de k-uplets d'un ensemble fini :

Propriété :
Soit E un ensemble fini à n éléments. Soit k un entier naturel non nul. Un k-uplet d'éléments de E est un élément du produit cartésien E^k. Le nombre de k-uplets de E est n^k, autrement dit card(E^k)=n^k.

Exemples :

1) Combien de codes de 4 lettres (distinctes ou non) peut on former ?
Exemples de codes : AAFG ; FTDT; ERTY, etc...
On considère E l'ensemble des lettres de l'alphabet. card(E) = 26. On cherche le nombre de 4-uplets de lettres, c'est à dire le cardinal de E⁴. card(E⁴) = 26⁴=456 976.
On peut former 456 976 codes différents.



Factorielle d'un nombre :

Définition :
Soit n un nombre entier naturel. On appelle factorielle n le produit de tous les nombres entiers compris entre 1 et n. On note n!


Remarque : Par convention 0! = 1.

Arrangements :

Propriété :
Soit E un ensemble fini à n éléments. Soit k un entier naturel non nul tel que 1≤k≤n. Un arrangement de k éléments de E est un k-uplet d'éléments distincts de E. Le nombre d'arrangements de k éléments de E est égal à :


Exemples :

1) Combien de codes de 4 lettres distinctes peut on former ?
Exemples de codes : AFTG ; DEFR; ERTY, etc... (ABCA ne fait pas partie des codes possibles puisqu'il y a deux fois la lettre A)
On considère E l'ensemble des 26 lettres de l'alphabet. On cherche le nombre de 4-uplets distincts de lettres, c'est à dire le nombre d'arrangements de 4 éléments de E.
26×25×24×23=358 800 (On a 26 choix pour la première lettre, puis 25 choix pour la deuxième, 24 choix pour la troisième et 23 choix pour la dernière lettre)
On peut donc former 358 800 codes différents.



Permutations :

Propriété :
Soit E un ensemble fini à n éléments. Une permutation de E est un arrangement de n éléments de E. Le nombre de permutations de E est égal à :


Exemples :

1) Combien de mots de 5 lettres distinctes (ayant un sens ou non) peut on former avec les lettres du mots MATHS ?
Exemples de mots : MTASH ; ATSMH ; TASMH ; etc...
Cela revient à chercher le nombre de permutations d'un ensemble à 5 éléments.
5! = 1×2×3×4×5 = 120
On peut donc former 120 mots différents.

Nombre de parties d'un ensemble fini :

Définition :
Soit E un ensemble. Un ensemble F est une partie de E si tous les éléments de F appartiennent à E. On dit également que F est inclus dans E ou que F est un sous-ensemble de E et on note F⊂E.

Exemples :
Soit A = {1;2;3}.
• {1;2} est une partie de A.
• Ø est une partie de A.
• {2;3} est une partie de A.
• {1;4} n'est pas une partie de A. (car 4∉A)

Propriété :
Soit E un ensemble fini à n éléments. Le nombre de parties de E est égal au nombre de n-uplets de l'ensemble {0;1} c'est à dire 2ⁿ.
Explication : En effet, pour construire une partie de E, il faut décider pour chaque élément de E si on le choisit(1) ou pas(0) pour l'inclure dans la partie, il y a donc autant de n-uplets de l'ensemble {0;1} que de parties de E.

Exemple :
Soit A = {1;2;3}. Les parties de A sont Ø, {1}, {2}, {3}, {1;2}, {1;3}, {2;3}, {1;2;3}. L'ensemble A possède 8 parties distinctes. (2³=8)

Combinaison :

Définition et propriété :
Soit E un ensemble fini à n éléments et k un entier naturel tel que 0≤k≤n. Une combinaison de k éléments de E est une partie de E à k éléments. Le nombre de combinaisons de k éléments de E est noté $\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)$ et est égal à :


Exemples :
1) Soit A = {1;2;3;4;5}. Quel est le nombre de combinaisons de 2 éléments de A ?
$\left(\begin{array}{c}5\\ 2\end{array}\right)=\frac{\text{5×4}}{\text{1×2}}=\frac{20}{2}=10$
En effet, les combinaisons de 2 éléments de A sont : {1;2}, {1;3}, {1;4}, {1;5}, {2;3}, {2;4}, {2;5}, {3;4}, {3;5} et {4;5}.

2) Au jeu du loto, il faut choisir 5 numéros parmi 49. Combien y a-t-il de combinaisons différentes ?
$\left(\begin{array}{c}49\\ 5\end{array}\right)=\frac{\text{49×48×47×46×45}}{\text{1×2×3×4×5}}=\frac{\mathrm{228 826 080}}{120}=\mathrm{1 906 884 }$

Cas particuliers :
Quel que soit l'entier naturel n :


Propriété de symétrie :
Quel que soit les entiers naturels n et k tels que 0≤k≤n :


Propriété :
Quel que soit l'entier naturel n :

Démonstration :
$\underset{k=0}{\overset{n}{\sum <!--N-ARY\; SUMMATION-->}}\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)=\left(\begin{array}{c}\mathrm{n}\\ 0\end{array}\right)+\left(\begin{array}{c}\mathrm{n}\\ 1\end{array}\right)+\text{...}+\left(\begin{array}{c}\mathrm{n}\\ \mathrm{n}\end{array}\right)$. Cette somme est égale au nombre de parties d'un ensemble à n éléments (nombre de parties à 1 élément+ nombre de parties à 2 éléments+...+nombre de parties à n éléments). D'après la propriété précédente, le nombre de parties d'un ensemble à n éléments est égal à 2ⁿ, donc $\underset{k=0}{\overset{n}{\sum <!--N-ARY\; SUMMATION-->}}\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)=2^n$

Triangle de Pascal : Pour tous entiers n et k tels que n ≥ 1 et 0≤k≤n-1, on a :

Démonstration :

$\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)+\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}+1\end{array}\right)$	$=\frac{\text{n!}}{\text{k!(n-k)!}}+\frac{\text{n!}}{\text{(k+1)!(n-k-1)!}}$
	$=\frac{\text{n!}}{\text{k!(n-k-1)!(n-k)}}+\frac{\text{n!}}{\text{(k+1)k!(n-k-1)!}}$
	$=\frac{\text{n!}}{\text{k!(n-k-1)!}}(\frac{\text{1}}{\text{(n-k)}}+\frac{\text{1}}{\text{(k+1)}})$
	$=\frac{\text{n!}}{\text{k!(n-k-1)!}}\left(\frac{\text{k+1+n-k}}{\text{(n-k)(k+1)}}\right)$
	$=\frac{\text{n!}}{\text{k!(n-k-1)!}}\left(\frac{\text{n+1}}{\text{(n-k)(k+1)}}\right)$
	$=\frac{\text{n!(n+1)}}{\text{k!(k+1)(n-k-1)!(n-k)}}$
	$=\frac{\text{(n+1)!}}{\text{(k+1)!(n-k)!}}$
	$=\left(\begin{array}{c}\mathrm{n}+1\\ \mathrm{k}+1\end{array}\right)$