Dénombrement (suite et fin)

# Dénombrement (suite et fin) ## Premiers outils élémentaires de dénombrement : Arbre de choix ; Arbre des parties ### Introduction Le dénombrement est une branche des mathématiques qui consiste à compter le nombre de possibilités ou de configurations dans diverses situations. C'est un outil fondamental pour comprendre la probabilité et analyser des ensembles de données. Dans cette leçon, nous allons explorer deux outils graphiques essentiels et intuitifs pour le dénombrement : l'**arbre de choix** et l'**arbre des parties**. Ces méthodes nous permettent de visualiser clairement toutes les options possibles et de calculer leur nombre de manière systématique. ### Concepts Clés #### L'Arbre de Choix ##### Définition et Utilité Un **arbre de choix** (ou arbre des possibles) est une représentation graphique qui permet de visualiser toutes les séquences de choix possibles dans une situation donnée. Il est particulièrement utile lorsque vous devez faire une série de décisions successives, et que chaque décision ouvre de nouvelles options. Chaque "branche" de l'arbre représente un choix, et les "feuilles" à l'extrémité de l'arbre représentent toutes les combinaisons finales possibles. ##### Comment le Construire ? 1. **Le point de départ (racine) :** C'est le début de votre situation, sans aucun choix encore effectué. 2. **Les premières branches :** À partir de la racine, tracez une branche pour chaque option du premier choix. 3. **Les nœuds intermédiaires :** À l'extrémité de chaque branche, vous atteignez un "nœud" qui représente l'état après le premier choix. 4. **Les branches suivantes :** À partir de chaque nœud, tracez de nouvelles branches pour les options du deuxième choix, et ainsi de suite. 5. **Les feuilles (résultats finaux) :** Les extrémités des dernières branches sont les résultats finaux, c'est-à-dire toutes les combinaisons possibles. ##### Calcul du Nombre de Possibilités Le **principe fondamental du dénombrement** (ou principe multiplicatif) stipule que si un premier événement peut se produire de \( n_1 \) manières, et un second événement (indépendant du premier) peut se produire de \( n_2 \) manières, alors les deux événements peuvent se produire de \( n_1 imes n_2 \) manières. Ce principe s'applique directement aux arbres de choix : le nombre total de chemins (et donc de résultats possibles) est le produit du nombre d'options à chaque étape. #### L'Arbre des Parties ##### Définition et Utilité Un **arbre des parties** est une méthode graphique utilisée pour lister tous les **sous-ensembles** possibles d'un ensemble donné. Un sous-ensemble est un ensemble qui contient une partie (ou la totalité, ou aucun) des éléments de l'ensemble original. Cet arbre est utile lorsque vous devez décider, pour chaque élément d'un ensemble, s'il doit être inclus ou non dans un sous-ensemble. L'ordre des éléments n'a pas d'importance pour un sous-ensemble. ##### Comment le Construire ? 1. **Le point de départ (racine) :** Représente l'ensemble vide (aucun élément choisi). 2. **Pour le premier élément :** Tracez deux branches à partir de la racine : * Une branche pour "inclure" cet élément. * Une branche pour "exclure" cet élément. 3. **Pour les éléments suivants :** Répétez ce processus pour chaque élément restant de l'ensemble, à partir de chaque nœud créé précédemment. Chaque nœud représente un ensemble partiel. 4. **Les feuilles (sous-ensembles finaux) :** Les extrémités des dernières branches sont les sous-ensembles complets de l'ensemble initial. ##### Calcul du Nombre de Possibilités Pour un ensemble de \( n \) éléments, il y a \( 2^n \) sous-ensembles possibles. Ceci est dû au fait que pour chaque élément, vous avez exactement deux choix : l'inclure ou ne pas l'inclure dans le sous-ensemble. Si un ensemble contient \( n \) éléments, le nombre total de ses sous-ensembles est donné par la formule : \[ N = 2^n \] ### Vocabulaire * **Dénombrement :** L'art de compter le nombre de façons d'organiser ou de sélectionner des objets. Il s'agit de déterminer le nombre de possibilités. \( \) * **Arbre de choix (ou arbre des possibles) :** Diagramme représentant toutes les séquences de choix possibles dans une situation donnée. * **Arbre des parties :** Diagramme représentant tous les sous-ensembles possibles d'un ensemble donné. * **Nœud :** Point d'un arbre où des branches se rencontrent ou se séparent, représentant un état ou un choix intermédiaire. * **Branche :** Segment reliant deux nœuds, représentant une action ou un choix unique. * **Feuille (ou terminal) :** Nœud final d'une branche, représentant un résultat ou une combinaison finale. * **Ensemble :** Collection d'objets distincts. \( \) * **Sous-ensemble :** Un ensemble formé de certains (ou de tous, ou d'aucun) éléments d'un autre ensemble. * **Principe de multiplication :** Si une tâche est composée de \( k \) étapes séquentielles, et que l'étape \( i \) peut être réalisée de \( n_i \) façons, alors la tâche entière peut être réalisée de \( n_1 imes n_2 imes ext{...} imes n_k \) façons. ### Exemples #### Exemple 1 : Arbre de Choix (Menu de Restaurant) Un restaurant propose les choix suivants pour un menu : * **Entrées :** Salade, Soupe (2 choix) * **Plats :** Poulet, Poisson, Végétarien (3 choix) * **Desserts :** Tarte, Glace (2 choix) Combien de repas différents peut-on composer ? ``` Racine | +--- Salade --- | | | +--- Poulet --- | | | | | +--- Tarte (Salade, Poulet, Tarte) | | | | | +--- Glace (Salade, Poulet, Glace) | | | +--- Poisson --- | | | | | +--- Tarte (Salade, Poisson, Tarte) | | | | | +--- Glace (Salade, Poisson, Glace) | | | +--- Végétarien --- | | | +--- Tarte (Salade, Végétarien, Tarte) | | | +--- Glace (Salade, Végétarien, Glace) | +--- Soupe --- | +--- Poulet --- | | | +--- Tarte (Soupe, Poulet, Tarte) | | | +--- Glace (Soupe, Poulet, Glace) | +--- Poisson --- | | | +--- Tarte (Soupe, Poisson, Tarte) | | | +--- Glace (Soupe, Poisson, Glace) | +--- Végétarien --- | +--- Tarte (Soupe, Végétarien, Tarte) | +--- Glace (Soupe, Végétarien, Glace) ``` Calcul : \( 2 ext{ (entrées)} imes 3 ext{ (plats)} imes 2 ext{ (desserts)} = 12 \) repas différents. #### Exemple 2 : Arbre des Parties (Choix d'Ingrédients) Vous avez un ensemble de fruits \( F = \{Pomme, Banane, Cerise\} \). Listez tous les sous-ensembles de fruits que vous pouvez choisir. ``` Racine ({}) | +--- Exclure Pomme --- | | | +--- Exclure Banane --- | | | | | +--- Exclure Cerise --- {} (Ensemble vide) | | | | | +--- Inclure Cerise --- {Cerise} | | | +--- Inclure Banane --- | | | +--- Exclure Cerise --- {Banane} | | | +--- Inclure Cerise --- {Banane, Cerise} | +--- Inclure Pomme --- | +--- Exclure Banane --- | | | +--- Exclure Cerise --- {Pomme} | | | +--- Inclure Cerise --- {Pomme, Cerise} | +--- Inclure Banane --- | +--- Exclure Cerise --- {Pomme, Banane} | +--- Inclure Cerise --- {Pomme, Banane, Cerise} ``` Calcul : L'ensemble \( F \) contient 3 éléments. Le nombre de sous-ensembles est \( 2^3 = 8 \). Les sous-ensembles sont : \( \{\}\) \( \{Cerise\}\) \( \{Banane\}\) \( \{Banane, Cerise\}\) \( \{Pomme\}\) \( \{Pomme, Cerise\}\) \( \{Pomme, Banane\}\) \( \{Pomme, Banane, Cerise\}\) ### Exercices #### Exercice 1 (Arbre de Choix) Un élève doit choisir une tenue pour la journée. Il a : * 3 chemises (Bleue, Verte, Rouge) * 2 pantalons (Jean, Treillis) * 2 paires de chaussures (Baskets, Mocassins) 1. Dessinez un arbre de choix pour représenter toutes les tenues possibles. 2. Calculez le nombre total de tenues différentes que l'élève peut composer. #### Exercice 2 (Arbre des Parties) Soit un ensemble de trois personnes \( P = \{Alice, Bob, Chloé\} \) pour former un petit comité (qui peut être vide, ou inclure toutes les personnes). 1. Dessinez un arbre des parties pour lister tous les comités possibles. 2. Déduisez-en le nombre total de comités différents pouvant être formés. #### Exercice 3 (Arbre de Choix et Dénombrement) On lance une pièce de monnaie équilibrée 3 fois de suite (P pour Pile, F pour Face). 1. Dessinez un arbre de choix pour représenter toutes les séquences possibles de Pile et Face. 2. Quel est le nombre total de résultats possibles ? 3. Combien de ces résultats contiennent exactement deux "Pile" ? ### Devoirs #### Question 1 (Arbre de Choix) Un questionnaire à choix multiples comporte 4 questions. Pour chaque question, il y a deux réponses possibles : Vrai ou Faux. 1. Dessinez un arbre de choix illustrant toutes les séquences de réponses possibles pour ce questionnaire. 2. Combien y a-t-il de façons différentes de répondre à l'intégralité du questionnaire ? #### Question 2 (Arbre des Parties) Un chef cuisinier prépare une salade et dispose de 4 ingrédients : Laitue, Tomate, Concombre, Oignon. Il peut choisir n'importe quelle combinaison de ces ingrédients (y compris une salade vide ou une salade avec tous les ingrédients). 1. Dessinez un arbre des parties pour lister toutes les salades différentes qu'il peut faire. 2. Combien de salades différentes le chef peut-il créer ? 3. Parmi ces salades, combien contiennent exactement 2 ingrédients ? ### Résumé Dans cette leçon, nous avons appris à utiliser deux outils graphiques puissants pour le dénombrement : l'**arbre de choix** et l'**arbre des parties**. * L'**arbre de choix** est idéal pour visualiser des séquences de décisions et compter le nombre total de résultats possibles en appliquant le principe multiplicatif : le nombre total de possibilités est le produit du nombre de choix à chaque étape. * L'**arbre des parties** est utilisé pour lister tous les sous-ensembles possibles d'un ensemble donné. Pour un ensemble de \( n \) éléments, il y a toujours \( 2^n \) sous-ensembles distincts, car chaque élément peut soit être inclus, soit être exclu. Ces outils ne sont pas seulement des moyens de compter ; ils nous aident aussi à organiser notre pensée et à s'assurer que nous n'oublions aucune possibilité lors de l'analyse de situations complexes.