Fiche de révision : Techniques fondamentales de dénombrement

📋 Plan du Cours

1. Comptage d'ensembles disjoints
2. Produit cartésien
3. Règle du produit
4. Permutations
5. Combinaisons
6. Formules de comptage
7. Exemples de comptage
8. Applications en jeux de cartes

📖 1. Comptage d'ensembles disjoints

🔑 Notions clés & Définitions

• Ensembles disjoints : Deux ensembles A et B sont disjoints si leur intersection est vide, c’est-à-dire A ∩ B = ∅.
• Propriété de l’union pour ensembles disjoints : Si A et B sont disjoints, alors |A ∪ B| = |A| + |B|.
• Notations |S| : Le nombre d’éléments dans un ensemble S, appelé la cardinalité de S.
• Exemple simple d’addition de cardinalités : Si le groupe comporte 43 femmes et 54 hommes, alors le total est |Femmes| + |Hommes| = 43 + 54 = 97.
• Produit cartésien : Pour deux ensembles A et B, le produit A × B est l’ensemble des couples (a, b) avec a ∈ A et b ∈ B. Si |A| = n et |B| = m, alors |A × B| = nm.
• Exemple de cardinalité du produit : Si A = {a, b, c, d} et B = {1, 2, 3}, alors |A × B| = 4 × 3 = 12.

📝 Points essentiels

• La propriété |A ∪ B| = |A| + |B| s’applique uniquement lorsque A et B sont disjoints.
• La cardinalité |S| représente le nombre d’éléments dans l’ensemble S, ce qui permet de quantifier la taille d’un ensemble.
• Lorsqu’on compte des objets dans un groupe, on peut additionner les cardinalités de sous-ensembles disjoints pour obtenir la taille totale. Par exemple, le total de femmes et d’hommes dans un groupe est la somme de leurs cardinalités respectives.
• Le produit cartésien permet de compter le nombre de couples ou de séquences formés à partir de deux ensembles, en multipliant leurs cardinalités.
• La formule |A × B| = |A| × |B| est généralisée au produit de plusieurs ensembles : |A₁ × A₂ × ... × Aₖ| = |A₁| × |A₂| × ... × |Aₖ|, utilisant la règle du produit.

💡 À retenir

Lorsque deux ensembles sont disjoints, leur union a pour cardinalité la somme de leurs tailles, et le produit cartésien permet de compter le nombre de combinaisons de leurs éléments.

📖 2. Produit cartésien

🔑 Notions clés & Définitions

• Produit cartésien (A × B) : Ensemble constitué de tous les couples (a, b) où a ∈ A et b ∈ B.
  Formule : $A \times B = \{(a, b) \mid a \in A, b \in B\}$.

• Cardinalité du produit cartésien : Si |A| = n et |B| = m, alors |A × B| = n × m.
  Extension au produit multiple : pour des ensembles $A_1, A_2, ..., A_k$, |$A_1 \times A_2 \times ... \times A_k$| = |$A_1$| × |$A_2$| × ... × |$A_k$|.

• Exemples concrets : Couples homme/femme (exemple : 43 femmes et 54 hommes donnent 43×54 couples), chaînes de bits (exemple : B = {0,1}, B² = toutes les chaînes de 2 bits).

📝 Points essentiels

• La taille du produit cartésien de deux ensembles est le produit de leurs tailles : |A × B| = |A| × |B|, ce qui peut être visualisé comme la construction d’un tableau où chaque ligne correspond à un élément de A et chaque colonne à un élément de B, chaque case représentant un couple.

• L’extension au produit multiple (plus de deux ensembles) repose sur la règle du produit : si on construit un produit de k ensembles, la cardinalité est le produit des cardinalités de chacun, soit |$A_1 \times A_2 \times ... \times A_k$| = |$A_1$| × |$A_2$| × ... × |$A_k$|. La preuve s’appuie sur l’induction mathématique.

• Exemple : Si |A|=4 (hommes) et |B|=3 (femmes), alors le nombre de couples homme/femme possibles est 12. Pour des chaînes de bits de longueur 10, avec B = {0,1}, le nombre total est $2^{10} = 1024$.

• La construction du produit cartésien permet de compter des objets complexes en décomposant leur description en choix successifs, illustrée par les exemples d’adresses IP, mots de passe, et autres.

💡 À retenir

Le produit cartésien d’ensembles permet de construire des ensembles de tous les objets possibles formés par la combinaison d’éléments de plusieurs ensembles, avec une taille donnée par le produit de leurs tailles respectives.

📖 3. Règle du produit

🔑 Notions clés & Définitions

• Règle du produit généralisée : Si une séquence de choix successifs comporte plusieurs étapes, et si pour chaque étape le nombre de possibilités est donné par un ensemble d’éléments, alors le nombre total de séquences possibles est le produit du nombre de possibilités à chaque étape. (source : supports de Naveen Garg)

• Application de la règle du produit : Lorsqu’on construit un ensemble par choix successifs, le nombre total d’éléments est le produit du nombre d’options à chaque étape. Par exemple, pour compter le nombre de mots de passe ou de chaînes de caractères, on multiplie le nombre de choix pour chaque position.

• Produit cartésien : L’ensemble formé par tous les couples (a, b) où a appartient à A et b appartient à B, noté A × B. La cardinalité est donnée par |A × B| = |A| × |B|. Extension au produit multiple : |A₁ × A₂ × ... × Aₖ| = |A₁| × |A₂| × ... × |Aₖ|. (source : supports de Naveen Garg)

• Exemples d’utilisation :

  • Mots de passe : le nombre de mots de longueur n avec un alphabet de taille m est mn.
  • Chaînes de caractères : par exemple, le nombre de chaînes binaires de longueur n est 2ⁿ.
  • Chaînes IP : le nombre d’adresses IP possibles avec 4 octets de 256 valeurs chacun est 256⁴.

• Lien avec la construction d’ensembles : La règle du produit permet de construire des ensembles complexes en combinant des ensembles plus simples, en comptant le nombre total d’éléments par le produit des tailles des ensembles composants.

📝 Points essentiels

• La règle du produit généralisée s’applique à toute situation où un choix successif est effectué, chaque étape ayant un nombre fixe de possibilités.
• La formule fondamentale : si pour chaque étape i, il y a nᵢ possibilités, alors le nombre total de séquences est n₁ × n₂ × ... × nₖ.
• La cardinalité du produit cartésien est toujours le produit des cardinalités des ensembles individuels : |A₁ × A₂ × ... × Aₖ| = |A₁| × |A₂| × ... × |Aₖ|.
• Elle est utilisée pour compter des objets comme des mots de passe, des chaînes binaires, des adresses IP, ou encore des mains de poker, en décomposant le problème en choix successifs.
• La preuve formelle de la règle du produit pour plusieurs ensembles repose sur l’induction mathématique.

💡 À retenir

La règle du produit généralisée permet de compter efficacement le nombre total d’objets construits par choix successifs, en multipliant le nombre d’options à chaque étape, ce qui est fondamental en combinatoire pour dénombrer des ensembles complexes.

📖 4. Permutations

🔑 Notions clés & Définitions

• Permutation : Arrangement ordonné de tous les éléments d’un ensemble, où chaque élément apparaît une seule fois. (source : contenu fourni)
• Nombre de permutations d’un ensemble de n éléments : Le total des arrangements possibles, donné par la formule n! = n × (n-1) × ... × 1. (source : contenu fourni)
• Lien avec la règle du produit : La formule du nombre de permutations découle directement de la règle du produit, en considérant le choix successif pour chaque position. (source : contenu fourni)

📝 Points essentiels

• La permutation d’un ensemble de n éléments est une séquence contenant tous ces éléments une seule fois, dans un ordre précis.
• La formule n! résulte du choix du premier élément (n options), puis du second (n-1 options), et ainsi de suite, jusqu’au dernier (1 option).
• Par exemple, pour l’ensemble {a, b, c}, il existe 3! = 6 permutations : (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a).
• La formule de Stirling (voir section 6) permet d’approcher la croissance de n! pour de grands n.
• La permutation est fondamentale pour compter le nombre de arrangements possibles lorsque l’ordre est important, notamment dans des jeux de cartes, des mots de passe, etc.

💡 À retenir

Une permutation est un arrangement ordonné de tous les éléments d’un ensemble, et le nombre total de permutations d’un ensemble de n éléments est donné par n!.

📖 5. Combinaisons

🔑 Notions clés & Définitions

• Sous-ensemble de taille k : Ensemble contenant exactement k éléments issus d’un ensemble de n éléments, sans tenir compte de l’ordre.
• Combinaison : Sous-ensemble de taille k d’un ensemble de n éléments, où l’ordre n’a pas d’importance.
• Formule du nombre de combinaisons :
  $C(n,k) = \frac{n!}{k! (n-k)!}$
  où $n!$ désigne la factorielle de n, représentant le nombre total d’arrangements possibles.
• Différence entre permutations et combinaisons :
  • Permutations (voir section 4) : arrangements ordonnés de n éléments, où l’ordre est important.
  • Combinaisons : sélection d’un sous-ensemble sans considération de l’ordre.
• Exemples concrets :
  • Sélection de sous-ensembles de taille k, par exemple, choisir 3 personnes parmi 10, ou former une équipe de 3 joueurs parmi 15.

📝 Points essentiels

• La formule $C(n,k) = \frac{n!}{k! (n-k)!}$ permet de compter le nombre de sous-ensembles de taille k dans un ensemble de n éléments.
• La différence fondamentale avec les permutations est que, dans le cas des combinaisons, l’ordre n’est pas pris en compte, ce qui explique la division par $k!$ (le nombre d’arrangements d’un sous-ensemble de k éléments).
• Lorsqu’on choisit des sous-ensembles, on ne considère pas la disposition, uniquement la composition.
• Par exemple, pour former une équipe de 3 personnes parmi 10, le nombre de combinaisons est $C(10,3) = \frac{10!}{3! \times 7!} = 120$.
• La règle du produit s’applique pour combiner plusieurs choix indépendants, mais pour le comptage de sous-ensembles, on utilise la formule spécifique de la combinaison.

💡 À retenir

Les combinaisons permettent de compter le nombre de sous-ensembles de taille k dans un ensemble de n éléments, en ignorant l’ordre, grâce à la formule $C(n,k) = \frac{n!}{k! (n-k)!}$.

📖 6. Formules de comptage

🔑 Notions clés & Définitions

• Somme (règle de somme) : Si un événement peut se produire de plusieurs manières disjointes, le nombre total de façons de le réaliser est la somme des façons individuelles.
  Exemple : Le nombre de caractères possibles dans un mot de passe combinant lettres minuscules, majuscules et chiffres est la somme des options (26 + 26 + 10).

• Produit (règle du produit) : Si un événement se décompose en plusieurs choix successifs indépendants, le nombre total de combinaisons est le produit du nombre de choix à chaque étape.
  Exemple : Le nombre de chaînes binaires de longueur n est $2^n$, car chaque position a 2 options.

• Permutations : Arrangement ordonné de tous les éléments d’un ensemble de n éléments, chaque élément étant utilisé une seule fois.
  Formule : $n!$ (factorielle de n).
  Exemple : Le nombre de permutations de {a, b, c} est 3! = 6.

• Combinaisons : Sous-ensembles de taille k d’un ensemble de n éléments, sans tenir compte de l’ordre.
  Formule : $C(n, k) = \frac{n!}{k!(n-k)!}$.
  Exemple : Nombre de sous-ensembles de 3 éléments dans un ensemble de 5.

• Formule de Stirling (date non précisée dans la source) : approximation de $n!$ pour de grands n, souvent exprimée par $n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$.

📝 Points essentiels

• La relation entre permutations et combinaisons : chaque combinaison de k éléments peut être arrangée en $k!$ permutations distinctes. Donc, $C(n, k) = \frac{\text{nombre de permutations de k éléments}}{k!}$.
• La formule de Stirling permet d’approximer rapidement $n!$ pour de grandes valeurs de n, utile dans l’analyse asymptotique.
• La technique de partitionnement consiste à diviser un ensemble en sous-ensembles disjoints, puis à compter chaque sous-ensemble séparément en utilisant la règle de somme ou de produit, puis à additionner ou multiplier selon le contexte.

💡 À retenir

Les formules de comptage essentielles incluent la règle de somme, la règle du produit, les permutations, et les combinaisons, qui permettent de compter efficacement les arrangements et sous-ensembles selon l’ordre ou non, avec ou sans répétition. La formule de Stirling offre une approximation précieuse pour $n!$ lorsque n est grand.

📖 7. Exemples de comptage

🔑 Notions clés & Définitions

• Règle du produit (voir section 4) : Si un processus se décompose en plusieurs étapes successives, où chaque étape a un nombre d’options indépendant, alors le nombre total de résultats possibles est le produit des options de chaque étape.
• Méthode de partitionnement : Technique consistant à diviser un ensemble en sous-ensembles disjoints, puis à compter chaque sous-ensemble séparément et à additionner les résultats, notamment pour compter des objets contenant au moins un certain élément (ex : au moins un 7).
• Complément (voir section 3) : Technique de comptage qui consiste à calculer le nombre total d’objets puis à soustraire ceux qui ne répondent pas à la propriété recherchée, pour simplifier le calcul (ex : nombres sans chiffre 7).
• Exemple d’application — chaînes de bits : Ensemble de séquences de longueur n constituées de bits {0,1}, où le nombre de séquences avec k zéros est donné par le choix de positions pour ces zéros, soit le coefficient binomial $\binom{n}{k}$.
• Exemple d’application — mots de passe : Utilisation du produit pour compter le nombre de mots de passe de longueur n, formés à partir d’un alphabet, en combinant différentes sous-ensembles (ex : lettres, chiffres) selon des règles spécifiques.

📝 Points essentiels

• La règle du produit permet de compter efficacement le nombre de chaînes ou objets composés d’étapes successives indépendantes, en multipliant le nombre d’options à chaque étape. Par exemple, pour compter le nombre de chaînes binaires de longueur n, on utilise $2^n$.
• La méthode de partitionnement est particulièrement utile pour compter des objets qui doivent contenir au moins un certain élément, en divisant l’ensemble en sous-ensembles disjoints selon la position ou la présence de cet élément, puis en additionnant. Par exemple, pour compter les nombres à 4 chiffres contenant au moins un 7, on peut compter le total et soustraire ceux sans 7.
• La technique du complément facilite le comptage en évitant de compter directement tous les objets répondant à une propriété complexe, en comptant d’abord tous les objets, puis en soustrayant ceux qui ne la possèdent pas.
• La règle du produit généralisée s’applique à des séquences ou produits cartésiens de plusieurs ensembles, permettant de compter le nombre total d’objets formés en combinant indépendamment chaque étape ou choix.
• Ces méthodes sont illustrées par des exemples concrets tels que le comptage de chaînes de bits, de mots de passe, ou de numéros de série avec chiffres distincts.

💡 À retenir

Les techniques de comptage telles que la règle du produit, le partitionnement et le complément permettent de décomposer des problèmes complexes en calculs simples, facilitant ainsi le dénombrement précis d’objets variés.

📖 8. Applications en jeux de cartes

🔑 Notions clés & Définitions

• Structure d’un jeu de 52 cartes : Ensemble constitué de 4 couleurs (♠, ♥, ♦, ♣), chacune comprenant 13 valeurs (2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A).
• Calcul du nombre de mains possibles au poker (5 cartes) : Utilisation de la combinatoire et de la règle du produit pour déterminer le nombre total de mains distinctes, en évitant le double comptage.
• Exemple de carré : Main contenant 4 cartes de même valeur, comptée par la séquence de choix de la valeur (13 options), puis de la carte supplémentaire (4 options). (13 × 12 × 4 = 624) mains possibles.
• Exemple de full house : Main avec trois cartes d’une valeur et deux d’une autre, comptée par la sélection de la valeur du brelan (13), des combinaisons pour le brelan (4 parmi 4), puis de la valeur de la paire (12), et des combinaisons pour la paire (4 parmi 4).
• Exemple de deux paires : Main avec deux cartes d’une valeur, deux d’une autre, et une carte supplémentaire d’une troisième valeur, comptée par la sélection des valeurs et des couleurs pour chaque paire et la carte restante.

📝 Points essentiels

• La structure d’un jeu de 52 cartes permet de modéliser différents problèmes de comptage en utilisant la combinatoire, notamment la règle du produit pour compter les mains ou configurations spécifiques.
• Pour compter le nombre de mains contenant un carré, on choisit la valeur des quatre cartes (13 options), puis la valeur de la carte restante (12 options), et enfin la couleur de la carte supplémentaire (4 options). La formule est : 13 × 12 × 4 = 624.
• La méthode de comptage pour un full house consiste à choisir la valeur du brelan (13), la combinaison pour le brelan (4 parmi 4), la valeur de la paire (12), et la combinaison pour la paire (4 parmi 4).
• Pour deux paires, on sélectionne deux valeurs distinctes (13 puis 12), puis les couleurs pour chaque paire (2 parmi 4), et enfin la carte restante (11 valeurs, 4 couleurs). La formule est : 13 × 4 × 12 × 4 × 11 × 4.
• La correction du double comptage intervient notamment dans le cas où plusieurs configurations se chevauchent, en divisant par le facteur correspondant (ex : 2! pour deux paires).

💡 À retenir

Les problèmes de comptage en jeux de cartes utilisent la combinatoire et la règle du produit pour déterminer le nombre de mains spécifiques, en évitant le double comptage grâce à la correction par division lorsque nécessaire.

📊 Tableaux de Synthèse

⚠️ Pièges & Confusions Fréquentes

1. Confondre ensembles disjoints et non disjoints lors de l’addition : |A ∪ B| = |A| + |B| uniquement si A ∩ B = ∅.
2. Oublier que le produit cartésien augmente la taille par multiplication, pas addition.
3. Confondre permutation (ordre) et combinaison (sans ordre).
4. Utiliser n! pour le nombre de permutations sans vérifier que tous les éléments sont utilisés.
5. Omettre la règle du produit lors du dénombrement de chaînes ou mots de passe.
6. Confondre le nombre de permutations avec le nombre de combinaisons.
7. Ne pas faire attention à la distinction entre cardinalité et nombre d’objets dans un contexte donné.

✅ Checklist Examen

1. Connaître la définition d’ensembles disjoints et la propriété |A ∪ B| = |A| + |B| pour A ∩ B = ∅.
2. Savoir calculer le produit cartésien A × B et sa cardinalité |A| × |B|.
3. Maîtriser la règle du produit généralisée pour plusieurs ensembles.
4. Connaître la formule du nombre de permutations n! et la justifier par la règle du produit.
5. Savoir définir une permutation d’un ensemble et donner un exemple.
6. Connaître la formule des combinaisons C(n, k) = n! / (k! (n-k)!) et ses applications.
7. Être capable de compter le nombre de chaînes binaires de longueur n (2ⁿ).
8. Comprendre l’application des formules en contexte de jeux de cartes ou d’adresses IP.
9. Savoir distinguer permutation et combinaison dans un problème donné.
10. Maîtriser la formule du produit pour compter des objets complexes construits par choix successifs.
11. Connaître la croissance de n! (approximation ou formule de Stirling si demandé).
12. Vérifier que le contexte correspond à un dénombrement d’ensembles ou d’arrangements, en utilisant la formule appropriée.