Hoja de repaso: Dénombrer et Récurrence en Ensembles Finis

Fiche devision : Dénombre et Récurrence dans les ensembles finis

1. 📌 L'essentiel

• Ensemble fini : ensemble avec un nombre fini d’éléments, noté Card(E).
• Principe additif : pour deux ensembles disjoints E et F, Card(E ∪ F) = Card(E) + Card(F).
• Produit cartésien : E × F = ensemble des couples (e,f), avec Card(E × F) = Card(E) × Card(F).
• k-uplets : listes ordonnées de k éléments de E, Card(E^k) = Card(E)^k.
• Arrangements (A_n k) : tirages sans remise de k éléments parmi n, A_n k = n! / (n−k)!.
• Permutations : arrangements de n éléments, nombre = n!.
• Récurrence : méthode de démonstration basée sur initialisation et hérédité.
• Exemples de suites : u_n = 2^n - 1, v_n = 3(1 - 2^n), prouvées par récurrence.
• Diagramme de Venn : outil pour visualiser intersections et dénombrements.
• Principes fondamentaux : multiplication pour combinaisons indépendantes, addition pour unions disjointes.

2. 🧩 Structures & Composants clés

• Ensemble fini — ensemble avec un nombre fini d’éléments.
• Cardinal — nombre d’éléments d’un ensemble, noté Card(E).
• Principe additif — addition des cardinalités pour unions disjointes.
• Produit cartésien — ensemble de couples, caractéristique principale : Card(E × F) = Card(E) × Card(F).
• k-uplets — listes ordonnées, cardinal : Card(E)^k.
• Arrangements (A_n k) — tirages sans remise, ordre important.
• Permutations — arrangements complets, nombre = n!.
• Récurrence — méthode de preuve par induction : étape initiale + étape hérédité.
• Exemples de suites — formules par récurrence : u_n = 2^n - 1, v_n = 3(1 - 2^n).

3. 🔬 Fonctions, Mécanismes & Relations

• Dénombrer un ensemble fini : compter ses éléments (Card(E)).
• Union d’ensembles : Card(E ∪ F) = Card(E) + Card(F) − Card(E ∩ F).
• Produit cartésien : construit des couples, Card(E × F) = Card(E) × Card(F).
• k-uplets : générés par le produit répété, Card(E)^k.
• Arrangements : sélection ordonnée sans remise, A_n k = n! / (n−k)!.
• Permutations : arrangements de tous les éléments, n!.
• Récurrence : prouver une propriété pour n0, puis pour n+1 à partir de n.
• Suites par récurrence : démonstration par induction, exemples : u_n = 2^n - 1.

4. Tableau de synthèse

Concept	Caractéristiques clés	Notes / Différences
Ensemble fini	Nombre d’éléments, Card(E)	Exemples : {1..10}, alphabet français
Principe additif	Card(E ∪ F) = Card(E) + Card(F) si disjoints	Sinon, Card(E ∪ F) = Card(E) + Card(F) - Card(E ∩ F)
Produit cartésien	E × F, couples (e,f), Card(E × F) = Card(E) × Card(F)	Visualisation par arbre
k-uplets	E^k, Card(E^k) = Card(E)^k	Utilisé pour dénombrer listes ordonnées
Arrangements (A_n k)	n! / (n−k)!	Tirage sans remise, ordre important
Permutations	n!	Arrangement de tous les éléments d’un ensemble
Récurrence	Initialisation + hérédité	P(n0) vraie, P(n) → P(n+1)
Suites par récurrence	u_n = 2^n - 1, v_n = 3(1 - 2^n)	Démonstration par induction

5. Diagramme hiérarchique ASCII

Ensembles finis
 ├─ Cardinalité
 │   ├─ Principe additif
 │   └─ Produit cartésien
 ├─ k-uplets
 │   └─ Card(E)^k
 ├─ Arrangements
 │   └─ A_n k = n! / (n−k)!
 └─ Permutations
     └─ n!
Récurrence
 ├─ Initialisation
 └─ Hérédité

6. ⚠️ Pièges & Confusions fréquentes

• Confondre arrangements (A_n k) et permutations (n!).
• Oublier la correction pour l’intersection dans Card(E ∪ F).
• Confondre k-uplets et permutations.
• Ne pas vérifier la base d’induction en récurrence.
• Confondre principe additif et multiplicatif.
• Oublier que le produit cartésien augmente la cardinalité par multiplication.
• Confondre ensemble fini et infini.
• Mauvaise utilisation des diagrammes de Venn pour intersections complexes.

7. ✅ Checklist Examen Final

• Définir un ensemble fini et sa cardinalité.
• Expliquer le principe additif avec un exemple.
• Calculer le cardinal d’un produit cartésien.
• Définir et calculer un k-uplet.
• Calculer un arrangement A_n k.
• Définir une permutation et la compter.
• Expliquer la méthode de démonstration par récurrence.
• Prouver une formule par récurrence (exemples : suites 2^n - 1, 3(1 - 2^n)).
• Utiliser un diagramme de Venn pour dénombrement.
• Identifier les pièges courants en dénombrement.
• Résoudre un problème de dénombrement avec principes fondamentaux.
• Comprendre la différence entre union, intersection, produit.
• Appliquer la formule de Card(E ∪ F).
• Calculer le nombre total de résultats pour une expérience aléatoire (ex : dés, cadenas).
• Savoir utiliser la formule du produit pour des événements indépendants.

---