Fiche de révision : Ensembles et dénombrement

📋 Plan du Cours

1. Ensembles et inclusion
2. Opérations sur les ensembles
3. Cardinal des ensembles finis
4. Dénombrement et cardinalité
5. Ensembles dénombrables
6. Arrangements et permutations
7. Combinaisons et coefficients binomiaux
8. Cas de tirage et dénombrement

📖 1. Ensembles et inclusion

🔑 Notions clés & Définitions

• Ensemble : Collection d’objets dont les éléments peuvent être de n’importe quelle nature.
• Inclusion : Lorsque tout élément de A appartient à E, ce qui se note A ⊂ E.
• Ensemble des parties : Ensemble de tous les sous-ensembles de E.

★ À maîtriser

📌 Dans un ensemble, l’ordre des éléments ne compte pas et les éléments ne sont pas répétés.

Compléments

• La relation d’inclusion est une relation d’ordre partiel sur P(E).

• L’ensemble des parties de {1, 2} est {∅, {1}, {2}, {1, 2}}.

📖 2. Opérations sur les ensembles

🔑 Notions clés & Définitions

• Union : Ensemble des éléments qui appartiennent à A ou à B.
• Intersection : Ensemble des éléments qui appartiennent à A et à B.
• Ensembles disjoints : Deux ensembles A et B sont disjoints lorsque leur intersection est vide, soit A ∩ B = ∅.
• Complémentaire : Ensemble des éléments de E qui n’appartiennent pas à A.
• Produit cartésien : Ensemble des couples ordonnés (x, y) tels que x ∈ E et y ∈ F.
• Disjonction deux à deux : Une famille (Aᵢ)ᵢ∈I est disjointe deux à deux si, pour tous i ≠ j, Aᵢ ∩ Aⱼ = ∅.

★ À maîtriser

📐 Formule - Les lois de De Morgan s’écrivent $(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ$ et $(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ$.

Compléments

📐 Formule - La distributivité des opérations sur les ensembles s’écrit $A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)$ et $A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)$.

📌 Si A ⊂ B, alors Bᶜ ⊂ Aᶜ.

• Le produit cartésien E × E se note aussi E², et un élément de E₁ × ··· × Eₙ est un n-uplet.

📖 3. Cardinal des ensembles finis

🔑 Notions clés & Définitions

• Cardinal : Nombre de ses éléments et se note Card(E) ou |E|.
• Ensemble fini : En bijection avec {1, …, n}.

★ À maîtriser

📌 Deux ensembles finis ont le même cardinal si et seulement s’il existe une bijection entre eux.

📐 Formule - Si A et B sont disjoints, alors $Card(A ∪ B) = Card(A) + Card(B)$.

📐 Formule - Pour deux parties quelconques A et B d’un ensemble fini, $Card(A ∪ B) = Card(A) + Card(B) - Card(A ∩ B)$.

Compléments

📌 Pour deux ensembles finis E et F, Card(E) ≤ Card(F) si et seulement s’il existe une injection de E dans F, ou une surjection de F dans E.

📐 Formule - Pour A ⊂ B dans un ensemble fini, Card(A) ≤ Card(B) et $Card(E\A) = Card(E) - Card(A)$.

📐 Formule - Pour trois parties A, B et C d’un ensemble fini, la formule du crible est $Card(A ∪ B ∪ C) = Card(A) + Card(B) + Card(C) - Card(A ∩ B) - Card(B ∩ C) - Card(A ∩ C) + Card(A ∩ B ∩ C)$.

📌 Si n objets sont répartis dans m ensembles et que n > m, alors au moins un ensemble contient plusieurs objets.

📖 4. Dénombrement et cardinalité

🔑 Notions clés & Définitions

• Dénombrable : En bijection avec ℕ, et le terme désigne parfois aussi un ensemble fini.

★ À maîtriser

📐 Formule - Pour un ensemble fini E, $Card(E^n) = Card(E)^n$.

📐 Formule - Si Card(E) = n, alors $Card(P(E)) = 2^n$.

• Le nombre d’applications d’un ensemble fini E dans F est $Card(F)^{Card(E)}$.

Compléments

• Dans Cent mille milliards de poèmes de Raymond Queneau (1961), chaque sonnet comporte 14 vers avec 10 choix pour chaque vers, soit $10^{14}$ poèmes possibles.

• Une configuration de six points de braille, chacun en relief ou non et avec au moins un point en relief, permet $2^6 - 1 = 63$ signes.

• Distribuer 52 cartes à 4 joueurs sans imposer le même nombre de cartes à chacun revient à choisir une application des cartes vers les joueurs, soit $4^{52}$ distributions.

📖 5. Ensembles dénombrables

★ À maîtriser

• ℕ², ℤ et ℚ sont dénombrables.

• L’intervalle [0, 1] et l’ensemble des réels ℝ ne sont pas dénombrables.

📌 Le produit cartésien fini d’ensembles dénombrables est dénombrable.

📌 Une union dénombrable d’ensembles dénombrables est dénombrable.

Compléments

• L’argument diagonal de Cantor permet de montrer que l’ensemble des réels n’est pas dénombrable.

📌 Si Card(E) ≥ 2, l’ensemble des suites à valeurs dans E n’est pas dénombrable.

• Le cardinal de ℕ est noté ℵ₀, celui de ℝ est noté c, et Card(ℝ) = Card(P(ℕ)) = c > ℵ₀.

• Le théorème de Cantor affirme que, pour tout ensemble E, Card(E) < Card(P(E)).

• L’ensemble des suites réelles et celui des fonctions continues de ℝ dans ℝ ont le cardinal c, tandis que l’ensemble des fonctions de ℝ dans ℝ a un cardinal supérieur à c.

📖 6. Arrangements et permutations

🔑 Notions clés & Définitions

• Arrangement : k-uplet d’éléments distincts de E, dans lequel l’ordre compte.
• Permutation : Arrangement de tous les n éléments d’un ensemble de cardinal n, et il en existe n!.

★ À maîtriser

📐 Formule - Pour 0 ≤ k ≤ n, le nombre d’arrangements à k éléments d’un ensemble de cardinal n est $A_n^k = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$, avec $A_n^0 = 1$.

Compléments

• Un arrangement représente une injection de {1, …, k} dans E.

• Le nombre d’applications d’un ensemble F de cardinal k dans un ensemble E de cardinal n est $n^k$.

• Le nombre d’injections d’un ensemble F de cardinal k dans E de cardinal n est $A_n^k$ si k ≤ n.

• Le nombre de bijections de F dans E vaut n! si n = k et 0 si n ≠ k.

💡 Astuce mémo

Arrangement : l’ordre compte ; combinaison : l’ordre ne compte pas.

📖 7. Combinaisons et coefficients binomiaux

🔑 Notions clés & Définitions

• Combinaison : Sous-ensemble de E de cardinal k, sans ordre entre ses éléments.

★ À maîtriser

📐 Formule - Pour 0 ≤ k ≤ n, le nombre de combinaisons à k éléments d’un ensemble de cardinal n est $\binom{n}{k} = \frac{n!}{(n-k)!k!}$.

📐 Formule - Pour un entier n et des nombres réels ou complexes a et b, la formule du binôme de Newton est $(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^k b^{n-k}$.

Compléments

• Chaque combinaison à k éléments correspond à k! arrangements, ce qui explique la division par k! dans la formule binomiale.

• Les coefficients binomiaux vérifient $\binom{n}{0} = \binom{n}{n} = 1$ et $\binom{n}{1} = \binom{n}{n-1} = n$.

• L’écriture des coefficients binomiaux en lignes forme le triangle de Pascal.

📖 8. Cas de tirage et dénombrement

★ À maîtriser

• Un tirage avec ordre et avec remise correspond à E^k et comporte n^k résultats si E contient n éléments.

• Un tirage avec ordre et sans remise correspond aux arrangements et comporte $A_n^k$ résultats.

• Un tirage sans ordre et sans remise correspond aux combinaisons et comporte $\binom{n}{k}$ résultats.

• Un tirage sans ordre et avec remise comporte $\binom{n+k-1}{k}$ résultats, en supposant qu’un ordre est défini sur E.

Compléments

• Le dénombrement des tirages sans ordre et avec remise se ramène à choisir k objets parmi k+n−1.

💡 Astuce mémo

Ordre et remise sont deux choix indépendants : l’un détermine la position, l’autre la répétition.

📊 Tableaux de synthèse

Modèles de tirage