Chap11 : Dénombrement

# Chap11 : Dénombrement ## Premiers outils dénombrement Leçon 40 : Les p-listes, arrangements et combinaisons : p- listes d’éléments d’un ensemble (p-uplets). ### Introduction Bienvenue à cette leçon sur les p-listes, un concept fondamental du dénombrement en mathématiques. Le dénombrement est l'art de compter le nombre de façons d'organiser ou de choisir des éléments. Aujourd'hui, nous allons nous concentrer sur les p-listes, également appelées p-uplets, qui représentent des séquences ordonnées d'éléments avec répétition possible. Ce concept est essentiel pour résoudre de nombreux problèmes de comptage où l'ordre est important et les éléments peuvent être utilisés plusieurs fois. ### Concepts Clés #### Qu'est-ce qu'une p-liste (ou p-uplet) ? Une p-liste, ou p-uplet, d'éléments d'un ensemble E est une séquence ordonnée de \(p\) éléments choisis dans E, où les répétitions sont autorisées. L'ordre des éléments compte. * **Ensemble E :** C'est l'ensemble de départ à partir duquel nous choisissons les éléments. * **Longueur p :** C'est le nombre d'éléments dans la séquence. * **Ordre :** L'ordre dans lequel les éléments apparaissent est important. Par exemple, \((a, b)\) est différent de \((b, a)\). * **Répétition :** Un même élément peut être choisi plusieurs fois. Par exemple, \((a, a)\) est une p-liste valide si \(a \in E\). **Exemple simple :** Si \(E = \{1, 2, 3\}\), une 2-liste (ou 2-uplet) peut être \((1, 1)\), \((1, 2)\), \((2, 1)\), etc. #### Nombre de p-listes d'éléments d'un ensemble E Considérons un ensemble \(E\) de \(n\) éléments (c'est-à-dire, \(|E| = n\)). Nous voulons former une p-liste d'éléments de \(E\). Pour le premier élément de la p-liste, nous avons \(n\) choix possibles. Pour le deuxième élément, puisque les répétitions sont autorisées, nous avons toujours \(n\) choix possibles. ... et ainsi de suite ... Pour le p-ième élément, nous avons également \(n\) choix possibles. Le nombre total de p-listes est obtenu en multipliant le nombre de choix à chaque étape. C'est le principe multiplicatif. Le nombre de p-listes d'éléments d'un ensemble à \(n\) éléments est : \[ n \times n \times \dots \times n \quad (p \text{ fois}) \] Ce qui s'écrit mathématiquement : \[ n^p \] #### Relation avec les choix avec répétition et ordre Les p-listes sont directement liées aux situations où l'on effectue \(p\) choix successifs parmi \(n\) options, avec la possibilité de répéter les choix et où l'ordre des choix est pertinent. ### Vocabulaire * **Dénombrement :** Branche des mathématiques qui consiste à compter le nombre d'éléments dans des ensembles finis ou le nombre de façons de réaliser des combinaisons ou des arrangements d'éléments. * **Ensemble \(E\) :** Une collection d'objets distincts. Son cardinal, noté \(|E|\) ou \(n\), est le nombre d'éléments qu'il contient. * **p-liste (ou p-uplet) :** Séquence ordonnée de \(p\) éléments choisis dans un ensemble, avec répétition possible. Par exemple, \((x_1, x_2, \dots, x_p)\). * **Principe multiplicatif :** Si une tâche peut être effectuée de \(n_1\) façons, et une deuxième tâche de \(n_2\) façons, etc., jusqu'à une \(k\)-ième tâche de \(n_k\) façons, alors le nombre total de façons d'effectuer toutes les tâches est le produit \(n_1 \times n_2 \times \dots \times n_k\). ### Exemples #### Exemple 1 : Codes PIN Combien de codes PIN à 4 chiffres peut-on former ? * L'ensemble des chiffres est \(E = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\). Il y a \(n = 10\) éléments. * Un code PIN à 4 chiffres est une 4-liste de ces chiffres (l'ordre compte, et les chiffres peuvent se répéter). * La longueur de la liste est \(p = 4\). Le nombre de codes PIN est donc \(n^p = 10^4 = 10 \times 10 \times 10 \times 10 = 10 000\). Il y a 10 000 codes PIN à 4 chiffres possibles. #### Exemple 2 : Résultats d'un lancer de dés On lance trois dés à six faces successivement. Combien de résultats différents peut-on obtenir ? * L'ensemble des faces d'un dé est \(E = \{1, 2, 3, 4, 5, 6\}\). Il y a \(n = 6\) éléments. * Un résultat de trois lancers est une 3-liste (l'ordre des lancers compte, et les résultats peuvent se répéter). * La longueur de la liste est \(p = 3\). Le nombre de résultats différents est donc \(n^p = 6^3 = 6 \times 6 \times 6 = 216\). Il y a 216 résultats différents possibles. #### Exemple 3 : Mots de passe Combien de mots de passe de 5 caractères peut-on former si chaque caractère peut être une lettre minuscule (26 lettres), une lettre majuscule (26 lettres) ou un chiffre (10 chiffres) ? * L'ensemble des caractères possibles est \(E = \{\text{26 minuscules} + \text{26 majuscules} + \text{10 chiffres}\}\). Le nombre total d'éléments est \(n = 26 + 26 + 10 = 62\). * Un mot de passe de 5 caractères est une 5-liste de ces caractères. * La longueur de la liste est \(p = 5\). Le nombre de mots de passe différents est donc \(n^p = 62^5 = 62 \times 62 \times 62 \times 62 \times 62 = 916 132 832\). Il y a plus de 900 millions de mots de passe possibles. ### Exercices 1. Un restaurant propose 5 entrées, 8 plats principaux et 4 desserts. Un client choisit une entrée, un plat principal et un dessert. Combien de repas différents peut-il composer ? (Considérez chaque choix comme indépendant et ordonné dans le repas) 2. On dispose de 6 couleurs différentes pour peindre 3 cases alignées. Chaque case peut être peinte avec n'importe quelle couleur, et une couleur peut être utilisée plusieurs fois. Combien de façons différentes y a-t-il de peindre ces 3 cases ? 3. Un système de loterie demande aux participants de choisir une séquence de 3 chiffres, chacun pouvant être de 0 à 9. Combien de séquences différentes sont possibles ? ### Devoirs 1. Dans une base de données, les identifiants utilisateur sont composés de 6 caractères alphanumériques (lettres majuscules et chiffres). Combien d'identifiants uniques sont possibles ? (Il y a 26 lettres majuscules et 10 chiffres). 2. Une serrure à combinaison est déverrouillée par une séquence de 4 rotations (gauche, droite, gauche, droite) d'un cadran qui comporte 30 numéros. Pour chaque rotation, le numéro sur lequel s'arrête le cadran est important. Combien de combinaisons différentes sont possibles pour déverrouiller cette serrure ? 3. Un étudiant doit choisir une matière principale et deux matières secondaires parmi 10 matières proposées par son université. Les matières secondaires peuvent être les mêmes que la matière principale, et l'ordre des matières secondaires n'importe pas entre elles, mais l'ensemble {matière principale, matière secondaire 1, matière secondaire 2} est ordonné. S'il n'y a pas de contrainte sur la répétition des choix, combien de combinaisons de matières peut-il faire ? (Indice : il s'agit de p-listes où p est le nombre de choix à faire, et n est le nombre total de matières). ### Résumé Dans cette leçon, nous avons exploré le concept des **p-listes (ou p-uplets)**. Nous avons appris qu'une p-liste est une séquence ordonnée de \(p\) éléments choisis dans un ensemble à \(n\) éléments, où la répétition est autorisée. Le nombre de p-listes possibles est donné par la formule \[ n^p \]. Ce concept est fondamental en dénombrement pour résoudre des problèmes de comptage où l'ordre des éléments est important et où les éléments peuvent être choisis plusieurs fois, comme pour les codes PIN, les résultats de lancers de dés ou les mots de passe. La maîtrise de cette notion est une première étape cruciale pour aborder d'autres outils de dénombrement plus complexes comme les arrangements et les combinaisons, que nous verrons dans les prochaines leçons. ## Premiers outils dénombrement ### Introduction au Dénombrement Bienvenue dans le chapitre sur le dénombrement ! Le dénombrement est l'art de compter le nombre de possibilités, de chemins, ou de combinaisons sans avoir à les lister toutes une par une. C'est un outil fondamental en mathématiques, notamment en probabilités, en informatique et dans de nombreux domaines de la vie quotidienne. Dans cette leçon, nous allons explorer les premiers concepts et outils pour aborder le dénombrement de manière méthodique et efficace. Préparez-vous à développer votre logique et votre capacité à résoudre des problèmes de comptage complexes. ### Concepts Clés du Dénombrement #### Qu'est-ce que le dénombrement ? Le dénombrement consiste à déterminer le nombre d'éléments d'un ensemble fini, ou le nombre de façons d'organiser ou de choisir des éléments selon certaines règles. C'est une étape cruciale avant de calculer des probabilités, par exemple. #### Le Principe Multiplicatif Le principe multiplicatif est l'un des outils les plus puissants en dénombrement. Il s'énonce comme suit : Si une tâche peut être accomplie en \( k \) étapes successives, et si : * La première étape peut être réalisée de \( n_1 \) manières différentes. * La deuxième étape peut être réalisée de \( n_2 \) manières différentes, quel que soit le choix de la première étape. * ... * La \( k \)-ième étape peut être réalisée de \( n_k \) manières différentes, quels que soient les choix des étapes précédentes. Alors le nombre total de façons d'accomplir la tâche est le produit : \[ N = n_1 \times n_2 \times \dots \times n_k \] **Exemple :** Si vous choisissez un pantalon parmi 3, une chemise parmi 4 et une paire de chaussures parmi 2, le nombre total de tenues possibles est \( 3 \times 4 \times 2 = 24 \). #### L'utilisation des Diagrammes en Arbre Les diagrammes en arbre sont des représentations graphiques qui permettent de visualiser toutes les issues possibles d'une succession d'événements. Ils sont particulièrement utiles lorsque le nombre de choix n'est pas trop grand. * Chaque branche représente un choix possible à une étape donnée. * Les chemins de la racine jusqu'aux feuilles représentent les différentes séquences d'événements (issues). * Le nombre total d'issues est le nombre de chemins différents menant aux feuilles de l'arbre. **Comment le construire :** 1. Commencez par un point (la racine). 2. Dessinez des branches pour chaque choix possible à la première étape. 3. À la fin de chaque branche, dessinez de nouvelles branches pour les choix possibles de la deuxième étape, et ainsi de suite. #### Les Listes (ou p-listes ou n-uplets) Une **liste** (ou **p-liste** ou **n-uplet**) est une suite ordonnée de \( p \) éléments choisis parmi \( n \) éléments distincts, avec répétition possible. * **Ordre :** L'ordre des éléments compte. Par exemple, \( (A, B) \) est différente de \( (B, A) \). * **Répétition :** Les éléments peuvent être choisis plusieurs fois. Par exemple, \( (A, A) \) est une liste valide. Le nombre de p-listes d'éléments choisis parmi \( n \) éléments est donné par la formule : \[ N = n^p \] Où \( n \) est le nombre d'éléments disponibles et \( p \) est la longueur de la liste. **Exemple :** Un code PIN à 4 chiffres (chaque chiffre de 0 à 9). Ici, \( n=10 \) (0, 1, ..., 9) et \( p=4 \). Le nombre de codes possibles est \( 10^4 = 10 000 \). ### Vocabulaire Important * **Dénombrement :** L'étude des méthodes de comptage des éléments d'un ensemble fini ou des configurations possibles. * **Principe Multiplicatif :** Règle fondamentale qui permet de calculer le nombre total de possibilités en multipliant le nombre de choix à chaque étape. * **Diagramme en Arbre :** Représentation graphique des choix successifs pour visualiser toutes les issues possibles. * **Liste (ou p-liste ou tuple) :** Une suite ordonnée de \( p \) éléments choisis parmi \( n \) éléments, avec répétition possible. L'ordre des éléments est important. * **Issue :** Un résultat possible d'une expérience aléatoire ou d'une suite de choix. * **Expérience aléatoire :** Une expérience dont on ne peut pas prédire le résultat avec certitude, mais dont on connaît l'ensemble des résultats possibles. ### Exemples Pratiques #### Exemple 1 : Choix d'un repas (Principe Multiplicatif) Un restaurant propose 3 entrées, 4 plats principaux et 2 desserts. Combien de menus différents peut-on composer si l'on choisit une entrée, un plat et un dessert ? **Solution :** * Nombre de choix pour l'entrée : \( n_1 = 3 \) * Nombre de choix pour le plat : \( n_2 = 4 \) * Nombre de choix pour le dessert : \( n_3 = 2 \) En utilisant le principe multiplicatif, le nombre total de menus est \( 3 \times 4 \times 2 = 24 \). #### Exemple 2 : Tirages successifs avec remise (Diagramme en Arbre et p-listes) On tire successivement deux boules d'une urne contenant 3 boules numérotées 1, 2, 3, en remettant la boule après chaque tirage. Combien de séquences de deux boules peut-on obtenir ? **Solution :** 1. **Avec un diagramme en arbre :** * Premier tirage : 1, 2, ou 3. * Deuxième tirage (après remise) : pour chaque premier tirage, on peut tirer à nouveau 1, 2, ou 3. Cela crée 3 branches au premier niveau, et 3 branches pour chacune de ces 3 au deuxième niveau, soit \( 3 \times 3 = 9 \) chemins (issues) au total. Les issues sont : (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3). 2. **Avec la formule des p-listes :** * Il s'agit d'une liste ordonnée de 2 éléments \( (p=2) \) choisis parmi 3 éléments \( (n=3) \), avec répétition possible. * Le nombre de possibilités est \( n^p = 3^2 = 9 \). #### Exemple 3 : Codes à chiffres (p-listes) Combien de nombres à 3 chiffres peuvent être formés en utilisant les chiffres de 1 à 5, si la répétition est autorisée ? **Solution :** * Nous avons \( n=5 \) chiffres disponibles (1, 2, 3, 4, 5). * Nous voulons former un nombre à \( p=3 \) chiffres. * Puisque la répétition est autorisée et l'ordre compte (par exemple, 123 est différent de 321), il s'agit de p-listes. * Le nombre de nombres possibles est \( n^p = 5^3 = 5 \times 5 \times 5 = 125 \). ### Exercices 1. Une bibliothèque propose 5 romans, 3 bandes dessinées et 4 magazines. Si un élève doit choisir un livre de chaque catégorie, combien de choix différents a-t-il ? 2. On lance une pièce de monnaie trois fois de suite. Dessinez un diagramme en arbre représentant toutes les issues possibles. Combien y a-t-il d'issues au total ? 3. Un cadenas à combinaison a un code à 4 chiffres. Chaque chiffre peut être de 0 à 9. Combien de codes différents sont possibles si la répétition des chiffres est autorisée ? 4. Combien de mots de 2 lettres peut-on former avec les lettres A, B, C, D si la répétition des lettres est autorisée et l'ordre compte ? ### Devoirs à la Maison 1. Un restaurant offre un menu avec 6 entrées, 8 plats principaux, 5 fromages et 7 desserts. Combien de repas différents composés d'une entrée, un plat, un fromage et un dessert sont possibles ? 2. Un groupe de rock doit choisir une chanson parmi 5 chansons possibles pour ouvrir son concert, puis une deuxième chanson parmi les 4 restantes (sans répétition). Dessinez un diagramme en arbre pour visualiser les options des deux premières chansons. Combien de paires de chansons sont possibles ? 3. Dans un système d'identification, un code est formé d'une lettre (parmi les 26 de l'alphabet) suivie de 3 chiffres (de 0 à 9). Combien de codes différents peuvent être générés si la répétition est autorisée pour les chiffres ? 4. Un test de type QCM comporte 5 questions. Pour chaque question, il y a 4 réponses possibles (A, B, C, D). Si un élève répond à toutes les questions au hasard, combien de suites de réponses différentes sont possibles ? ### Résumé Dans cette leçon, nous avons appris les bases du dénombrement. Les points essentiels à retenir sont : * **Le Dénombrement** est l'art de compter les possibilités. * Le **Principe Multiplicatif** permet de calculer le nombre total de façons d'accomplir une tâche en plusieurs étapes en multipliant le nombre de choix à chaque étape : \[ N = n_1 \times n_2 \times \dots \times n_k \]. * Les **Diagrammes en Arbre** sont des outils visuels pour représenter et compter les issues de séquences d'événements, surtout pour un petit nombre de choix. * Les **Listes (ou p-listes)** sont des suites ordonnées d'éléments avec répétition possible. Le nombre de p-listes de \( p \) éléments choisis parmi \( n \) est donné par la formule \[ N = n^p \].