Chap7: Dénombrement (suite)

# Chap7: Dénombrement (suite) ## Premiers outils élémentaires de dénombrement : Arbre de choix ; Arbre des parties ### Introduction Bienvenue dans ce nouveau chapitre sur le dénombrement ! Après avoir effleuré les bases du dénombrement, nous allons maintenant explorer deux outils visuels très puissants qui nous permettent de lister et de compter systématiquement les différentes possibilités dans des situations variées : l'arbre de choix et l'arbre des parties. Ces méthodes graphiques vous aideront à mieux comprendre comment structurer des problèmes de comptage avant d'aborder des formules plus complexes. ### Concepts Clés #### Rappel sur le Dénombrement Le dénombrement est une branche des mathématiques qui consiste à compter le nombre de façons dont un certain événement peut se produire ou le nombre d'éléments dans un ensemble. C'est l'art de compter des configurations, des arrangements ou des combinaisons. #### L'Arbre de Choix (ou Arbre de Décision) ##### Qu'est-ce qu'un arbre de choix ? Un **arbre de choix** est une représentation graphique qui permet de visualiser toutes les possibilités d'une succession de choix ou d'événements. Il est constitué de "nœuds" (points de décision ou d'étape) et de "branches" (choix possibles à chaque étape). * La **racine** de l'arbre est le point de départ. * Chaque **branche** représente une option ou un événement possible à une étape donnée. * Un **chemin** de la racine à une **feuille** (le nœud terminal) représente une séquence complète de choix, c'est-à-dire une possibilité unique. ##### Comment construire un arbre de choix ? 1. **Identifier la première étape** et les choix possibles. Dessinez la racine et les branches correspondantes. 2. Pour chaque choix de la première étape, **identifier la deuxième étape** et ses choix. Dessinez de nouvelles branches à partir des nœuds terminaux de l'étape précédente. 3. **Répéter** ce processus pour toutes les étapes successives jusqu'à ce qu'il n'y ait plus de choix à faire. ##### Utilité de l'arbre de choix * **Visualisation claire** : Il rend les situations complexes plus faciles à comprendre. * **Comptage systématique** : Le nombre total de possibilités est égal au nombre de feuilles (chemins complets) de l'arbre. * Il est étroitement lié au **principe multiplicatif** que nous avons déjà abordé. Si une expérience se déroule en plusieurs étapes, et que le nombre de choix à chaque étape est indépendant des choix précédents, le nombre total de possibilités est le produit du nombre de choix à chaque étape. #### L'Arbre des Parties ##### Qu'est-ce qu'un arbre des parties ? L'**arbre des parties** est un type spécifique d'arbre de choix utilisé pour lister tous les sous-ensembles (ou parties) d'un ensemble donné. Pour chaque élément de l'ensemble, il y a exactement deux possibilités : soit l'élément est inclus dans le sous-ensemble, soit il ne l'est pas. ##### Comment construire un arbre des parties ? Pour un ensemble \( E = \{e_1, e_2, ..., e_n\} \) : 1. Commencez avec un nœud initial (représentant l'ensemble vide, ou le point de départ avant toute décision). 2. Pour le premier élément \( e_1 \), créez deux branches : l'une pour l'inclure dans la partie en construction, l'autre pour ne pas l'inclure. 3. Répétez ce processus pour le deuxième élément \( e_2 \) à partir de chacun des nœuds créés à l'étape précédente. 4. Continuez ainsi pour tous les éléments de l'ensemble. Chaque feuille de l'arbre correspondra à une partie de l'ensemble \( E \). ##### Utilité de l'arbre des parties * **Listing exhaustif** : Il permet de lister de manière systématique toutes les parties d'un ensemble, y compris l'ensemble vide et l'ensemble lui-même. * **Découverte de la formule** : Pour un ensemble ayant \( n \) éléments, le nombre total de ses parties est \( 2^n \). Chaque élément a deux options (être inclus ou non), et il y a \( n \) éléments, d'où le produit \( 2 \times 2 \times ... \times 2 \) (\( n \) fois), soit \( 2^n \). Ce résultat peut être visuellement confirmé par le nombre de feuilles de l'arbre des parties. #### Principe Multiplicatif (Rappel et Lien) Le **principe multiplicatif** est fondamental en dénombrement. Il stipule que si une tâche peut être décomposée en \( k \) étapes successives, et si la première étape peut être réalisée de \( n_1 \) manières, la deuxième de \( n_2 \) manières, ..., et la \( k \)ème de \( n_k \) manières, alors le nombre total de façons de réaliser la tâche est le produit \( n_1 \times n_2 \times ... \times n_k \). Les arbres de choix sont une illustration directe de ce principe, où chaque branche représente un choix et le nombre de feuilles finales est le produit du nombre de branches à chaque étape. ### Vocabulaire * **Dénombrement** : L'étude des méthodes de comptage des éléments d'un ensemble ou des possibilités dans une situation donnée. * **Arbre de choix (ou Arbre de décision)** : Un diagramme en forme d'arbre qui représente toutes les séquences de décisions ou d'événements possibles et leurs résultats. * **Arbre des parties** : Un type spécifique d'arbre de choix utilisé pour énumérer tous les sous-ensembles (parties) d'un ensemble donné. * **Chemin** : Une séquence de branches de la racine à une feuille dans un arbre, représentant une suite de choix ou une possibilité unique. * **Étape** : Une phase distincte dans une succession de choix ou d'événements. * **Feuille (ou Nœud terminal)** : Le point final d'un chemin dans un arbre, représentant un résultat final ou une combinaison de choix. * **Ensemble** : Une collection d'objets distincts. * **Partie (ou Sous-ensemble)** : Un ensemble dont tous les éléments appartiennent à un autre ensemble plus grand. L'ensemble vide \( \emptyset \) est une partie de tout ensemble, et tout ensemble est une partie de lui-même. * **Principe Multiplicatif** : Règle fondamentale du dénombrement pour calculer le nombre total de résultats lorsque plusieurs choix indépendants sont effectués successivement. ### Exemples #### Exemple 1 : Arbre de choix - Composition d'un menu Un restaurant propose pour un menu : * **Entrées** : Salade, Soupe (2 choix) * **Plats** : Poisson, Viande, Végétarien (3 choix) * **Desserts** : Tarte, Glace (2 choix) Combien de menus différents peut-on composer ? **Construction de l'arbre :** ```mermaid graph TD A[Début] --> B(Entrée) B --> B1(Salade) B --> B2(Soupe) B1 --> C1(Plat) C1 --> C1a(Poisson) C1 --> C1b(Viande) C1 --> C1c(Végétarien) B2 --> C2(Plat) C2 --> C2a(Poisson) C2 --> C2b(Viande) C2 --> C2c(Végétarien) C1a --> D1a(Dessert) D1a --> D1a1(Tarte) D1a --> D1a2(Glace) C1b --> D1b(Dessert) D1b --> D1b1(Tarte) D1b --> D1b2(Glace) C1c --> D1c(Dessert) D1c --> D1c1(Tarte) D1c --> D1c2(Glace) C2a --> D2a(Dessert) D2a --> D2a1(Tarte) D2a --> D2a2(Glace) C2b --> D2b(Dessert) D2b --> D2b1(Tarte) D2b --> D2b2(Glace) C2c --> D2c(Dessert) D2c --> D2c1(Tarte) D2c --> D2c2(Glace) ``` **Calcul :** En comptant les feuilles de l'arbre, on trouve 12 chemins différents. En utilisant le principe multiplicatif : \( 2 \text{ (entrées)} \times 3 \text{ (plats)} \times 2 \text{ (desserts)} = 12 \) menus possibles. #### Exemple 2 : Arbre des parties - Parties d'un ensemble Listons toutes les parties de l'ensemble \( A = \{a, b, c\} \). **Construction de l'arbre :** Pour chaque élément, on décide s'il est présent (P) ou absent (A) dans la partie. ```mermaid graph TD A[\emptyset] --> B1("a est présent") A --> B2("a est absent") B1 --> C1("b est présent") B1 --> C2("b est absent") B2 --> C3("b est présent") B2 --> C4("b est absent") C1 --> D1("c est présent") D1 --> D1P({a,b,c}) C1 --> D2("c est absent") D2 --> D2A({a,b}) C2 --> D3("c est présent") D3 --> D3P({a,c}) C2 --> D4("c est absent") D4 --> D4A({a}) C3 --> D5("c est présent") D5 --> D5P({b,c}) C3 --> D6("c est absent") D6 --> D6A({b}) C4 --> D7("c est présent") D7 --> D7P({c}) C4 --> D8("c est absent") D8 --> D8A({\emptyset}) ``` **Résultat :** Les parties de \( A \) sont : \( \{\emptyset\}, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \). Nous avons \( 2^3 = 8 \) parties, ce qui correspond au nombre de feuilles de l'arbre. ### Exercices #### Exercice 1 (Arbre de choix) : Création de codes Un code est composé d'une lettre suivie d'un chiffre. Les lettres possibles sont A, B, C. Les chiffres possibles sont 1, 2. 1. Dessinez l'arbre de choix pour représenter toutes les combinaisons possibles. 2. Combien de codes différents peuvent être formés ? #### Exercice 2 (Arbre des parties) : Parties d'un petit ensemble Soit l'ensemble \( B = \{\text{bleu, jaune}\} \). 1. Dessinez l'arbre des parties de \( B \). 2. Listez toutes les parties de l'ensemble \( B \). 3. Vérifiez que le nombre de parties correspond à la formule \( 2^n \). #### Exercice 3 (Combiné) : Choix de vêtements Vous devez choisir une tenue pour la journée. Vous avez 3 chemises (verte, blanche, noire), 2 pantalons (jean, chino) et 2 paires de chaussures (baskets, mocassins). 1. Dessinez un arbre de choix pour représenter toutes les tenues possibles. 2. Combien de tenues différentes pouvez-vous former ? ### Devoirs #### Problème 1 (Arbre de choix) : Organisation d'un voyage Pour vos prochaines vacances, vous avez les choix suivants : * **Destinations** : Espagne, Italie, Portugal (3 choix) * **Modes de transport** : Avion, Train (2 choix) * **Types d'hébergement** : Hôtel, Camping, Airbnb (3 choix) 1. Dessinez l'arbre de choix pour déterminer toutes les combinaisons de voyage possibles. 2. Combien de voyages différents pouvez-vous planifier ? #### Problème 2 (Arbre des parties) : Composition d'une commission Une petite commission doit être formée à partir d'un groupe de trois étudiants : Alice, Ben, Chloé. La commission peut être composée de n'importe quel nombre de ces étudiants (de 0 à 3). 1. Dessinez l'arbre des parties pour l'ensemble des étudiants \( E = \{\text{Alice, Ben, Chloé}\} \). 2. Listez toutes les compositions de commission possibles. 3. Quel est le nombre total de compositions de commission possibles ? ### Résumé Dans cette leçon, nous avons exploré deux outils graphiques essentiels en dénombrement : * L'**arbre de choix** nous permet de visualiser et de compter toutes les séquences de décisions ou d'événements dans une situation donnée. Le nombre de feuilles de l'arbre correspond au nombre total de possibilités, illustrant le principe multiplicatif. * L'**arbre des parties** est une application spécifique de l'arbre de choix pour lister systématiquement tous les sous-ensembles (parties) d'un ensemble. Pour un ensemble de \( n \) éléments, il y a \( 2^n \) parties, chaque élément ayant deux options : être inclus ou non. Ces outils sont fondamentaux pour aborder les problèmes de dénombrement de manière structurée et méthodique, avant de passer à des techniques de calcul plus abstraites comme les arrangements et les combinaisons.