Dénombrement (suite)

# Dénombrement (suite) ## Les p-listes, arrangements et combinaisons : p- listes d’éléments d’un ensemble (p-uplets). ### Introduction au Dénombrement Le dénombrement est une branche des mathématiques qui consiste à compter le nombre de façons d'organiser ou de sélectionner des objets. Il est fondamental dans de nombreux domaines, de l'informatique à la biologie en passant par la cryptographie et les probabilités. Aujourd'hui, nous allons explorer trois concepts clés du dénombrement : les p-listes, les arrangements et les combinaisons. La distinction entre ces concepts repose sur deux critères essentiels : * **L'ordre des éléments :** Est-ce que l'ordre dans lequel les éléments sont choisis a de l'importance ? * **La répétition des éléments :** Est-ce qu'un élément peut être choisi plusieurs fois ? ### Concepts Clés #### 1. Les p-listes (ou p-uplets) ##### Définition Une **p-liste** (ou p-uplet) d'éléments d'un ensemble \(E\) à \(n\) éléments est une suite ordonnée de \(p\) éléments de \(E\), avec **répétition possible**. Cela signifie que les éléments peuvent être répétés et que l'ordre dans lequel ils sont choisis est important. ##### Formule Le nombre de p-listes d'un ensemble à \(n\) éléments est donné par : \[ n^p \] * \(n\) : nombre total d'éléments disponibles. * \(p\) : nombre d'éléments choisis pour former la liste. ##### Exemples Concrets * Les codes PIN d'une carte bancaire (par exemple, 4 chiffres choisis parmi 10, avec répétition et ordre). * Les plaques d'immatriculation. * Les séquences d'ADN (bases A, T, C, G). #### 2. Les Arrangements ##### Définition Un **arrangement** de \(p\) éléments pris dans un ensemble \(E\) à \(n\) éléments est une suite ordonnée de \(p\) éléments **distincts** de \(E\). Ici, l'ordre est important, mais la répétition est impossible (chaque élément ne peut être utilisé qu'une seule fois). ##### Formule Le nombre d'arrangements de \(p\) éléments parmi \(n\) est noté \(A_n^p\) et est donné par : \[ A_n^p = rac{n!}{(n-p)!} \] Où \(n!\) (prononcé "factorielle n") est le produit de tous les entiers positifs de 1 à \(n\). Par exemple, \(5! = 5 imes 4 imes 3 imes 2 imes 1 = 120\). Par convention, \(0! = 1\). Il faut toujours que \(p eq n\) ou \(p \le n\). ##### Exemples Concrets * Le classement des trois premiers coureurs dans une course de 10 participants (l'ordre 1er, 2e, 3e est important, et un coureur ne peut pas être à la fois 1er et 2e). * Le choix d'un président, d'un vice-président et d'un secrétaire parmi 15 personnes. #### 3. Les Combinaisons ##### Définition Une **combinaison** de \(p\) éléments pris dans un ensemble \(E\) à \(n\) éléments est un sous-ensemble de \(p\) éléments **distincts** de \(E\), sans que l'ordre n'ait d'importance. Ici, la répétition est impossible et l'ordre n'est pas pris en compte. ##### Formule Le nombre de combinaisons de \(p\) éléments parmi \(n\) est noté \(C_n^p\) ou \(\binom{n}{p}\) (coefficient binomial) et est donné par : \[ C_n^p = inom{n}{p} = rac{n!}{p!(n-p)!} \] Il faut toujours que \(p \le n\). ##### Propriétés Importantes des Coefficients Binomiaux * \(C_n^p = C_n^{n-p}\) * \(C_n^0 = 1\) * \(C_n^n = 1\) * \(C_n^1 = n\) ##### Exemples Concrets * Le tirage de 6 numéros au Loto parmi 49 (l'ordre des numéros tirés n'a pas d'importance, et un numéro ne peut être tiré qu'une fois). * Le choix de 3 élèves pour former un comité parmi 20 (les élèves A, B, C forment le même comité que B, A, C). #### Récapitulatif : Quand utiliser quoi ? | Caractéristique \ Période | Ordre Important | Ordre Non Important | | :------------------------- | :---------------- | :------------------ | | **Avec Répétition** | p-listes (\(n^p\)) | Impossible (ou plus complexe, hors programme Première) | | **Sans Répétition** | Arrangements (\(A_n^p\)) | Combinaisons (\(C_n^p\)) | ### Vocabulaire * **Dénombrement :** L'art de compter le nombre de façons d'organiser ou de choisir des objets. * **Ensemble (E) :** Une collection d'objets distincts. \(n\) est le nombre d'éléments dans l'ensemble. * **p-liste / p-uplet :** Suite ordonnée de \(p\) éléments, avec répétition possible. * **Arrangement :** Suite ordonnée de \(p\) éléments distincts. * **Combinaison :** Sous-ensemble non ordonné de \(p\) éléments distincts. * **Factorielle (\(n!\)) :** Produit de tous les entiers positifs de 1 à \(n\). \(n! = n imes (n-1) imes ... imes 1\). * **Coefficient Binomial (\(\binom{n}{p}\)) :** Autre nom pour \(C_n^p\), représente le nombre de combinaisons. * **Ordre :** Indique si la position des éléments est importante. * **Répétition :** Indique si un élément peut être choisi plusieurs fois. ### Exemples #### Exemple 1 : p-liste Un cadenas à combinaison possède 3 roues, chacune ayant les chiffres de 0 à 9. Combien de codes différents peut-on former ? * \(n = 10\) (10 chiffres possibles pour chaque roue). * \(p = 3\) (3 roues). * L'ordre est important (123 est différent de 321) et la répétition est possible. * Nombre de codes = \(n^p = 10^3 = 1000\) codes différents. #### Exemple 2 : Arrangement Dans une course de 12 chevaux, on parie sur les 3 premiers chevaux dans l'ordre exact d'arrivée (Tiercé dans l'ordre). Combien y a-t-il de Tiercés dans l'ordre possibles ? * \(n = 12\) (12 chevaux). * \(p = 3\) (3 premières places). * L'ordre est important (1er, 2e, 3e est différent de 2e, 1er, 3e) et la répétition est impossible (un cheval ne peut être qu'à une place). * Nombre de Tiercés = \(A_{12}^3 = rac{12!}{(12-3)!} = rac{12!}{9!} = 12 imes 11 imes 10 = 1320\) Tiercés possibles. #### Exemple 3 : Combinaison Un club de 15 membres souhaite élire un comité de 4 personnes. Combien de comités différents peut-on former ? * \(n = 15\) (15 membres). * \(p = 4\) (4 personnes à élire). * L'ordre n'est pas important (le comité {A, B, C, D} est le même que {D, C, B, A}) et la répétition est impossible. * Nombre de comités = \(C_{15}^4 = inom{15}{4} = rac{15!}{4!(15-4)!} = rac{15!}{4!11!} = rac{15 imes 14 imes 13 imes 12}{4 imes 3 imes 2 imes 1} = 1365\) comités différents. ### Exercices 1. Une urne contient 7 boules numérotées de 1 à 7. On tire successivement 3 boules **avec remise** et on note les numéros obtenus. Combien de tirages différents y a-t-il ? 2. Toujours avec les 7 boules, on tire successivement 3 boules **sans remise** et on note les numéros dans l'ordre. Combien de tirages différents y a-t-il ? 3. Avec les 7 boules, on tire simultanément 3 boules. Combien de groupes de 3 boules peut-on obtenir ? 4. Combien de mots de 5 lettres peut-on former avec les lettres de l'alphabet (26 lettres), si la répétition des lettres est autorisée ? 5. Dix athlètes participent à une course. Combien y a-t-il de podiums possibles (1er, 2e, 3e) ? 6. Parmi 20 étudiants, combien de groupes de 3 étudiants peut-on former pour un travail de groupe ? ### Devoirs à la maison 1. On dispose des chiffres 1, 2, 3, 4, 5. Combien peut-on former de nombres de 3 chiffres : a. Si les chiffres peuvent être répétés ? b. Si les chiffres doivent être tous distincts ? 2. Un jeu de cartes contient 32 cartes. Combien de mains de 5 cartes différentes peut-on distribuer ? 3. Un code est formé de 2 lettres (parmi les 26 de l'alphabet) suivies de 3 chiffres (de 0 à 9). a. Combien de codes différents peut-on former si les répétitions sont autorisées pour les lettres et les chiffres ? b. Combien de codes différents peut-on former si toutes les lettres et tous les chiffres doivent être distincts ? 4. Lors d'un conseil de classe, 2 délégués titulaires et 2 suppléants doivent être désignés parmi 10 élèves. Combien y a-t-il de façons de faire cette désignation ? (Attention, les rôles sont différents pour titulaire et suppléant). ### Résumé Pour récapituler, le choix de la méthode de dénombrement dépend de deux questions clés : 1. **L'ordre est-il important ?** 2. **La répétition est-elle possible ?** * Si l'ordre est important et la répétition est possible : utilisez les **p-listes** (\(n^p\)). * Si l'ordre est important mais la répétition est impossible : utilisez les **arrangements** (\(A_n^p = rac{n!}{(n-p)!}\)). * Si l'ordre n'est pas important et la répétition est impossible : utilisez les **combinaisons** (\(C_n^p = inom{n}{p} = rac{n!}{p!(n-p)!}\)). Maîtriser ces trois concepts est essentiel pour résoudre une grande variété de problèmes de dénombrement et de probabilités.