Principes de Dénombrement en Combinatoire

Bonjour,

Dans la leçon précédente, nous avons conclu notre premier module sur les méthodes de preuve en abordant la correction des algorithmes récursifs et itératifs. Vous maîtrisez désormais la preuve par récurrence et la technique de l'invariant de boucle, des outils formels essentiels pour raisonner sur les programmes.

Nous ouvrons aujourd'hui le deuxième module, consacré aux Mathématiques Discrètes pour l'Informatique. L'objectif de cette première leçon est de poser les fondations de la combinatoire, l'art de compter. Vous allez apprendre à appliquer les principes de dénombrement (addition et multiplication) pour résoudre des problèmes combinatoires. Ces principes, bien que simples en apparence, sont la pierre angulaire de l'analyse d'algorithmes, des probabilités discrètes et de nombreux autres domaines de l'informatique théorique.

1. Principes Fondamentaux du Dénombrement

Le dénombrement consiste à déterminer la taille (le cardinal) d'ensembles finis. Presque tous les problèmes de dénombrement, aussi complexes soient-ils, peuvent être décomposés en une succession de choix plus simples, gouvernés par deux principes fondamentaux : le principe additif et le principe multiplicatif.

La vidéo suivante, issue de la chaîne "Les Bons Profs", présente ces deux principes de manière claire et intuitive, avec des exemples pertinents.

Principes additif et multiplicatif - Maths -Terminale - Les Bons Profs

Cette vidéo explique le principe additif (ou règle de la somme) et le principe multiplicatif (ou règle du produit). Elle est très bien structurée et vous donnera les bases nécessaires.

Regardez les deux parties principales de la vidéo (de 00:16 à 11:45). Principe additif (00:16 - 05:26) : Concentrez-vous sur la condition des choix disjoints (la "classification non redondante"). Portez une attention particulière à l'exemple des langues (à partir de 02:26), qui introduit une idée cruciale : que faire lorsque les ensembles de choix ne sont pas disjoints ? Principe multiplicatif (05:26 - 11:45) : Observez comment l'arbre de décision pour l'exemple du menu illustre la multiplication des choix. Retenez l'idée qu'il s'agit de compter le nombre de résultats possibles pour une séquence d'expériences.

a) Le Principe Additif (Règle de la Somme)

Comme vous l'avez vu, le principe additif s'applique lorsque vous devez faire un choix parmi plusieurs options alternatives et mutuellement exclusives. Le mot-clé est "OU".

Cas simple (ensembles disjoints) : Si une tâche A peut être réalisée de $n_{1}$ manières et une tâche B de $n_{2}$ manières, et qu'il est impossible de faire A et B en même temps, alors le nombre de manières de faire A ou B est $n_{1} + n_{2}$ .
En termes ensemblistes, que vous avez étudiés dans le module précédent, si $A$ et $B$ sont deux ensembles finis disjoints ( $A \cap B = \emptyset$ ), alors :
$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$
Cas général (principe d'inclusion-exclusion) : L'exemple des élèves étudiant l'anglais et l'allemand dans la vidéo est fondamental. Lorsque les ensembles de choix ne sont pas disjoints, additionner simplement leurs cardinaux compte deux fois les éléments de l'intersection. Il faut donc les soustraire une fois. Pour deux ensembles $A$ et $B$ :
$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$

b) Le Principe Multiplicatif (Règle du Produit)

Le principe multiplicatif s'applique lorsque vous réalisez une procédure qui se décompose en une séquence d'étapes indépendantes. Le mot-clé est "ET".

Si une procédure peut être décomposée en une séquence de $k$ tâches, où la première tâche peut être réalisée de $n_{1}$ manières, la deuxième de $n_{2}$ manières, ..., et la $k$ -ième de $n_{k}$ manières, alors le nombre total de manières de réaliser la procédure complète est le produit $n_{1} \times n_{2} \times \dots \times n_{k}$ .

Ceci correspond au calcul du cardinal du produit cartésien des ensembles de choix à chaque étape :
$∣ E_{1} \times E_{2} \times \dots \times E_{k} ∣ = ∣ E_{1} ∣ \times ∣ E_{2} ∣ \times \dots \times ∣ E_{k} ∣$

L'arbre de décision est une excellente façon de visualiser ce principe.

Dénombrement: Principe Multiplicatif avec Arbre de Cas — Cette image illustre le principe multiplicatif pour former des nombres à deux chiffres distincts à partir de l'ensemble {1, 2, 3}. Pour le premier chiffre (unités), il y a 3 choix. Pour chaque choix, il reste 2 choix pour le second chiffre (dizaines). Le nombre total de possibilités est donc 3 × 2 = 6.

En préparation à l'agrégation, il est utile de vous familiariser avec la manière dont ces principes sont formalisés dans les documents de référence.

Leçon 190 - Méthodes combinatoires, problèmes de dénombrement.

Le document suivant est une "leçon d'agrégation" typique. Il formalise rigoureusement les concepts que nous venons de voir. Il n'est pas nécessaire de tout lire, mais de repérer les définitions clés.

Sur la page 2, dans la section I.1 "Ensembles finis et cardinaux", retrouvez les propositions qui formalisent les deux principes : Proposition 3 : La formule pour Card(A ∪ B) est le principe d'inclusion-exclusion. Corollaire 5 : C'est le principe additif pour une partition (plusieurs ensembles disjoints). Proposition 6 : C'est le principe multiplicatif, énoncé en termes de produit cartésien.

2. Application et Problèmes Combinés

La véritable difficulté en combinatoire est de savoir quand et comment combiner ces deux principes. Un problème complexe doit être décomposé en une série de "ET" (produit) et de "OU" (somme).

Exemple : Combien de plaques d'immatriculation peut-on former avec 2 lettres majuscules (de A à Z) suivies de 3 chiffres (de 0 à 9), si les lettres doivent être distinctes et au moins un des chiffres doit être un '9' ?

Décomposons le problème :

Choix des lettres : C'est une séquence de 2 choix sans répétition.
- Choix de la 1ère lettre : 26 options.
- Choix de la 2ème lettre : 25 options.
- Total pour les lettres (principe multiplicatif) : $26 \times 25$ .
Choix des chiffres : Ici, c'est plus subtil. La condition est "au moins un 9". Il est souvent plus simple de compter le contraire : "aucun 9".
- Nombre total de combinaisons de 3 chiffres (avec répétition) : $10 \times 10 \times 10 = 1 0^{3}$ .
- Nombre de combinaisons de 3 chiffres sans le '9' : $9 \times 9 \times 9 = 9^{3}$ .
- Le nombre de combinaisons avec au moins un '9' est donc (principe additif, version soustractive) : $1 0^{3} - 9^{3} = 1000 - 729 = 271$ .
Combinaison finale : La plaque est formée des lettres ET des chiffres. On applique le principe multiplicatif.
- Nombre total de plaques : $(26 \times 25) \times (1 0^{3} - 9^{3}) = 650 \times 271 = 176150$ .

Cet exemple montre une stratégie clé : compter le complémentaire est souvent plus facile.

3. Exercices d'application

Il est temps de mettre ces principes en pratique. Les exercices suivants, tirés du site BibM@th, sont d'un niveau classique pour ce sujet. Essayez de les résoudre par vous-même avant de regarder le corrigé.

Exercices corrigés - Dénombrements (pratiques) - BibM@th

Cette page contient une série d'exercices corrigés sur le dénombrement. Nous allons nous concentrer sur quelques-uns qui appliquent directement les principes de somme et de produit.

Veuillez traiter les exercices suivants. Pour chacun, essayez d'abord de le résoudre, puis vérifiez votre raisonnement avec la correction fournie sur la page.

Exercice 1 : Le cadenas (Exercice 8 sur la page)

Cet exercice est une application directe du principe multiplicatif et de la technique du complémentaire.

Répondez aux questions de la partie 1 :
- a. Combien y-a-t-il de codes possibles ?
- c. Combien y-a-t-il de codes contenant au moins un chiffre 4 ?
- d. Combien y-a-t-il de codes contenant exactement un chiffre 4 ?

Pistes de réflexion

* Pour la question 1a, il s'agit d'une séquence de 3 choix avec répétition possible. * Pour la 1c, pensez à utiliser le complémentaire : comptez le nombre total de codes et soustrayez le nombre de codes qui n'ont *aucun* chiffre 4. * Pour la 1d, il faut combiner les deux principes. Il y a un "OU" (le 4 est en première, deuxième, **ou** troisième position) et des "ET" (choisir le premier chiffre **et** le deuxième **et** le troisième).

Exercice 2 : Groupe d'étudiants (Exercice 1 sur la page)

Cet exercice se résout très bien en utilisant un tableau à double entrée, ce qui est une méthode visuelle pour organiser les informations et appliquer le principe d'addition/soustraction.

Essayez de remplir le tableau comme suggéré dans l'indication et la correction. Cela vous aidera à visualiser les ensembles disjoints et leurs intersections.

Exercice 3 : Dans une entreprise (Exercice 2 sur la page)

Cet exercice est une application directe de la formule d'inclusion-exclusion pour 3 ensembles :
$∣ H \cup M \cup S ∣ = ∣ H ∣ + ∣ M ∣ + ∣ S ∣ - (∣ H \cap M ∣ + ∣ H \cap S ∣ + ∣ M \cap S ∣) + ∣ H \cap M \cap S ∣$

Utilisez les données de l'énoncé pour calculer $∣ H \cup M \cup S ∣$ .
Ce que l'on vous demande est le cardinal du complémentaire de cet ensemble.

Conclusion

Cette première incursion dans le dénombrement vous a permis de maîtriser les deux outils les plus fondamentaux de la combinatoire.

Points clés à retenir :

Le principe additif s'utilise pour des choix alternatifs (un OU logique). Si les choix ne sont pas mutuellement exclusifs, il faut utiliser le principe d'inclusion-exclusion pour corriger le double comptage.
Le principe multiplicatif s'utilise pour des procédures en étapes séquentielles (un ET logique). Le nombre total de possibilités est le produit du nombre de choix à chaque étape.
Face à un problème complexe, la stratégie est de le décomposer en une arborescence de décisions plus simples, en identifiant les "ET" et les "OU".
La technique du dénombrement par le complémentaire (compter ce que l'on ne veut pas et le soustraire du total) est extrêmement puissante.

Dans la prochaine leçon, nous nous appuierons sur ces principes pour définir et utiliser des outils plus spécialisés : les arrangements et les combinaisons. Nous verrons comment ces concepts formalisent les situations de tirages "avec ou sans ordre" et "avec ou sans remise", qui sont au cœur d'innombrables problèmes d'algorithmique et de probabilités.

Recommended resources