Dénombrement

Le cours

1. Produit cartésien\n\nDéfinition : Le produit cartésien de deux ensembles $A$ et $B$ est l'ensemble :\n$$A \\times B = \\{(a, b) / a \\in A \\text{ et } b \\in B\}$$\n\nCardinal : Si $A$ a $n$ éléments et $B$ a $p$ éléments, alors :\n$$|A \\times B| = n \\times p$$\n\nExemple : Choix d'un menu = produit cartésien {entrées} × {plats} × {desserts}\nNombre de menus = $4 \\times 3 \\times 5 = 60$\n\n## 2. p-listes (p-uplets)\n\nDéfinition : Une p-liste d'éléments d'un ensemble $E$ à $n$ éléments est une suite ordonnée de $p$ éléments de $E$ (pas nécessairement distincts).\n\nNombre de p-listes :\n$$n^p$$\n\nExemple : Codes PIN de 4 chiffres (de 0 à 9) : $10^4 = 10\,000$ possibilités.\n\n## 3. Arrangements\n\nDéfinition : Un arrangement à $p$ éléments d'un ensemble à $n$ éléments ($p \\leq n$) est une p-liste d'éléments tous distincts.\n\nNombre d'arrangements :\n$$A_n^p = n(n-1)(n-2)...(n-p+1) = \\frac{n!}{(n-p)!}$$\n\nNotation : $n! = 1 \\times 2 \\times 3 \\times ... \\times n$ (factorielle n)\n\nExemple : Classement des 3 premiers d'une course de 8 athlètes à Yamoussoukro : $A_8^3 = 8 \\times 7 \\times 6 = 336$.\n\n## 4. Permutations\n\nDéfinition : Une permutation d'un ensemble à $n$ éléments est un arrangement à $n$ éléments (tous les éléments sont utilisés).\n\nNombre de permutations :\n$$P_n = n!$$\n\nExemple : Façons d'asseoir 5 personnes sur un banc : $5! = 120$.\n\nmathgraph\n{\n \"type\": \"points\",\n \"title\": \"Croissance des factorielles n!\",\n \"xRange\": [0, 6],\n \"yRange\": [0, 130],\n \"points\": [\n { \"x\": 1, \"y\": 1, \"color\": \"#0088FE\", \"name\": \"1! = 1\" },\n { \"x\": 2, \"y\": 2, \"color\": \"#00C49F\", \"name\": \"2! = 2\" },\n { \"x\": 3, \"y\": 6, \"color\": \"#FFBB28\", \"name\": \"3! = 6\" },\n { \"x\": 4, \"y\": 24, \"color\": \"#FF8042\", \"name\": \"4! = 24\" },\n { \"x\": 5, \"y\": 120, \"color\": \"#8884d8\", \"name\": \"5! = 120\" }\n ],\n \"showGrid\": true,\n \"showAxes\": true,\n \"xLabel\": \"n\",\n \"yLabel\": \"n!\"\n}\n\n\n## 5. Combinaisons\n\nDéfinition : Une combinaison à $p$ éléments d'un ensemble à $n$ éléments ($p \\leq n$) est un sous-ensemble à $p$ éléments (l'ordre n'a pas d'importance).\n\nNombre de combinaisons :\n$$C_n^p = \\frac{A_n^p}{p!} = \\frac{n!}{p!(n-p)!}$$\n\nPropriétés :\n1. $C_n^p = C_n^{n-p}$\n2. $C_n^0 = C_n^n = 1$\n3. $C_n^1 = C_n^{n-1} = n$\n\nExemple : Formation d'une équipe de 5 joueurs parmi 11 (football à Abidjan) : $C_{11}^5 = \\frac{11!}{5!6!} = 462$.\n\n## 6. Arbre de décision pour choisir la bonne formule\n\nmermaid\ngraph TD\n A[Problème de dénombrement] --> B{Les p éléments sont-ils\n nécessairement distincts ?}\n B -->|Non| C{p-liste : n^p}\n B -->|Oui| D{L'ordre a-t-il de\n l'importance ?}\n D -->|Non| E[Combinaison : C_n^p]\n D -->|Oui| F{Tous les n éléments\n sont-ils utilisés ?}\n F -->|Oui| G[Permutation : n!]\n F -->|Non| H[Arrangement : A_n^p]\n\n\n## 7. Formule du binôme de Newton\n\n$$(a + b)^n = \\sum_{k=0}^n C_n^k a^{n-k} b^k$$\n\nExemple : $(x + 1)^4 = C_4^0 x^4 + C_4^1 x^3 + C_4^2 x^2 + C_4^3 x + C_4^4$\n$= x^4 + 4x^3 + 6x^2 + 4x + 1$\n\n## 8. Applications ivoiriennes\n\na) Loterie nationale :\n- Choisir 5 numéros parmi 50 : $C_{50}^5 = \\frac{50!}{5!45!}$\n- Calcul : $\\frac{50\\times49\\times48\\times47\\times46}{5\\times4\\times3\\times2\\times1} = 2\,118\,760$\n\nb) Composition d'un gouvernement :\n- Choisir 10 ministres parmi 30 candidats : $C_{30}^{10}$\n\nc) Codes d'accès :\n- Code de 6 caractères (lettres + chiffres) : $36^6$ possibilités\n\nd) Tournoi de football à Bouaké :\n- Nombre de matchs dans un championnat de 12 équipes (aller simple) : $C_{12}^2 = 66$