Cours
I. Cardinal d'un ensemble fini⚓︎
Remarque
Dans tout ce chapitre on considère un ensemble \(E\) fini.
Définition : Cardinal d'un ensemble fini
Le cardinal de l'ensemble \(E\) est son nombre d'éléments et on le note \(|E| \in \mathbb{N}\).
Exemples
Remarque
On le note également \(\text{Card}(E)\).
Proposition
On considère une partie \(F\) de l'ensemble \(E\). Alors la partie \(F\) est fini et \(|F|\leq |E|\) avec égalité si et seulement si \(E = F\).
Démonstration
Exemple
Proposition
On considère un autre ensemble fini \(F\) et une application \(f : E \longrightarrow F\). Si \(|F| = |E|\) alors les assertions suivantes sont équivalentes.
-
L'application \(f\) est injective.
-
L'application \(f\) est surjective.
-
L'application \(f\) est bijective.
Démonstration
Exemple
Proposition
On considère des parties \(A\) et \(B\) de l'ensemble \(E\).
-
Si les parties \(A\) et \(B\) sont disjointes alors \(|A\cup B| = |A| + |B|\).
-
\(|A\cup B| = |A| + |B| - |A\cap B|\).
-
\(|A^c| = |E|- |A|\).
-
\(|A \backslash B| = |A| - |A \cap B|\).
-
\(|A\times B| = |A||B|\).
Démonstration
Exemples
Proposition
On considère un autre ensemble finie \(F\) de cardinal \(|F| = p \in \mathbb{N}\). Alors l'ensemble \(F^E\) des applications de l'ensemble \(E\) dans l'ensemble \(F\) est fini et \(|F^E| = |F|^{|E|}\).
Démonstration
Exemple
Corollaire
L'ensemble \(\mathcal{P}(E)\) des parties de l'ensemble \(E\) est fini et \(|\mathcal{P}(E)| = 2^n\).
Démonstration
Exemple
II. Listes et combinaisons⚓︎
Définition : \(p\)-liste (ou \(p\)-uplet)
On considère un entier \(p \in \{1, ..., n\}\). Alors on appelle \(p\)-liste (ou \(p\)-uplet) de l'ensemble \(E\) toute famille \(\{a_1, ..., a_p\}\) de \(p\) éléments de l'ensemble \(E\).
Proposition
On considère un entier \(p\in \{1, ..., n\}\). Alors l'ensemble des \(p\)-listes de l'ensemble \(E\) est fini et de cardinal \(n^p\).
Démonstration
Exemple
Proposition
On considère un entier \(p\in \{1, ..., n\}\). Alors l'ensemble des \(p\)-listes de l'ensemble \(E\) d'éléments distincts est fini et de cardinal \(\dfrac{n!}{(n-p)!} = n! ... (n-p+1)!\).
Démonstration
Exemple
Proposition
L'ensemble des permutations de l'ensemble \(\mathcal{S}_E\) est fini et \(|\mathcal{S}_E| = n!\).
Démonstration
Exemple
Proposition
On considère un autre ensemble fini \(F\) de cardinal \(p = |F| \in \mathbb{N}\). Alors l'ensemble des applications injectives de l'ensemble \(E\) dans l'ensemble \(F\) est fini et de cardinal \(\dfrac{n!}{(n-p)!}\).
Démonstration
Exemple
Proposition
On considère un entier \(k \in \{0, ..., n\}\). Alors l'ensemble des parties de l'ensemble \(E\) à \(k\) éléments est fini et de cardinal \(\dfrac{n!}{k! (n-k)!} = \binom{n}{k}\).
Démonstration
Exemple
Théorème : Formule de Pascal
On considère un entier \(k \in \{0,..., n\}\). Alors \(\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}\).
Démonstration
Exemple
Théorème : Formule du binôme de Newton
On considère deux scalaires \(a,b \in \mathbb{K}\). Alors