Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

CHAPITRE 1 RAPPELS D’ANALYSE COMBINATOIRE I Généralités L’analyse combinatoire

CHAPITRE 1 RAPPELS D’ANALYSE COMBINATOIRE I Généralités L’analyse combinatoire a pour but le dénombrement des dispositions que l’on peut former à partir des éléments d’un ensemble de cardinal fini. Plus simplement, elle cherche à déterminer comment on compte des objets ayant certaines propriétés. Pour effectuer un dénombrement, il faut connaître l’ensemble sur lequel on travaille et le type de disposition souhaité.  L’ensemble étudié : il peut être formé d’éléments discernables et/ou d’éléments indiscernables. - Si tous les éléments sont distinguables les uns des autres, on dit qu’ils sont discernables. On écrit alors avec si . On a . Exemple : les cartes à jouer, les numéros portés par des sportifs dans une épreuve, les numéros des candidats à un examen, etc … - Si les éléments sont tous identiques, on dit qu’ils sont indiscernables. On écrit encore, avec un abus de notation du point de vue purement mathématique, , avec . Exemple : un ensemble de boules de la même couleur dans une urne. - Si l’ensemble comprend un mélange des deux types d’éléments, on écrit, de façon abusive, , avec si . On a .  Les dispositions : elles peuvent être ordonnées ou non-ordonnées, avec ou sans répétition. Il faut donc considérer le nombre de fois où chaque apparaît dans un dénombrement donné, et sa position dans le dénombrement. Si chaque élément apparaît au plus une fois, la disposition est sans répétition, si un élément au moins a un nombre d’apparitions strictement supérieur à 1, on obtient une disposition avec répétition. Attention : toutes les dispositions ordonnées s’écrivent entre parenthèses, toutes les dispositions non-ordonnées s’écrivent entre accolades Exemples : - disposition ordonnée sans répétition : une liste de noms distincts rangés dans l’ordre alphabétique, - disposition non ordonnée sans répétition : les numéros gagnants du loto, - disposition ordonnée avec répétition : un mot du dictionnaire contenant plusieurs fois une ou plusieurs lettres, - disposition non ordonnée avec répétition : les lettres formant un mot du dictionnaire écrites dans un ordre quelconque.  Principe général d’un dénombrement : toujours commencer par préciser la nature de l’ensemble et la structure du de la disposition étudiée. II Formules classiques 1) Multiplets  Définition : Soient ensembles formés d’éléments complètement discernables, avec . Ces ensembles sont supposés non vides, et on note . Un multiplet est une disposition ordonnée de éléments tels que , , , . On l’écrit .  Valeur : Le nombre de multiplets que l’on peut former est alors . Cas particulier : les paires. On a alors . 2) Arrangements avec répétition Soit un ensemble non vide , formé d’éléments discernables. .  Définition : On appelle arrangement avec répétition de éléments parmi toute disposition ordonnée avec répétition éventuelle formée de éléments pris parmi les de . Exemple : .  Valeur : Le nombre d’arrangements avec répétition de éléments parmi est . 3) Arrangements sans répétition Soit un ensemble non vide , formé d’éléments discernables. . Soit un entier tel que .  Définition : Un arrangement sans répétition, ou tout simplement arrangement, de éléments parmi est toute disposition ordonnée de éléments deux à deux distincts pris parmi les de .  Valeur : Le nombre d’arrangements de éléments parmi est : . Exemple : le nombre de façons de tirer 3 cartes sans remise et en tenant compte de l’ordre dans un jeu de 32 cartes est . 4) Permutations sans répétition Soit un ensemble non vide , formé d’éléments discernables. .  Définition : On appelle permutation sans répétition, ou simplement permutation, des éléments de toute disposition ordonnée sans répétition de ces éléments.  Valeur : Le nombre de permutations de ces éléments est . Exemple : le nombre des permutations des 3 éléments de l’ensemble est . Ces permutations sont : . 5) Permutations avec répétition  Définition Soit , avec si . On note L’ensemble contenant des élements discernables et des élements indiscernables, toute permutation de ses élements sera forcément une permutation avec répétition.  Valeur : Le nombre de permutations avec répétition des éléments de l’ensemble s’écrit : . Il dépend des valeurs des . Exemple : soit . Dans ce cas, . Vérification : les permutations que l’on obtient sont : . 6) Combinaisons sans répétition Soit un ensemble non vide , formé d’éléments discernables. . Soit un entier tel que .  Définition : Une combinaison sans répétition, ou tout simplement combinaison, de éléments parmi est toute disposition non-ordonnée de éléments deux à deux distincts pris parmi les de . On l’écrit entre accolades, par exemple si .  Valeur : Le nombre de combinaisons de éléments parmi est : . Exemple : le nombre de combinaisons sans répétition de 2 éléments parmi les 5 de est . Vérification : ces combinaisons sont : . 7) Combinaisons avec répétition Soit un ensemble non vide , formé d’éléments discernables. .  Définition : On appelle combinaison avec répétition de éléments parmi toute disposition non ordonnée avec répétition éventuelle formée de éléments pris parmi les de . Exemple : .  Valeur : Le nombre de combinaisons avec répétition de éléments parmi est : . Exemple : le nombre de combinaisons avec répétition de 2 éléments pris dans est . Vérification : ces combinaisons sont . Rappel : pour , le nombre appelé factorielle n et noté est le produit des premiers entiers non nuls . Par convention, . Ce nombre croît très vite lorsque augmente. Par exemple, . Dès que dépasse 10, on utilise la formule d’approximation de Stirling : . III Propriétés des combinaisons 1) La symétrie Pour tous et , tels que , on a . Valeurs à connaître : 2) Le triangle de Pascal Formule de Pascal : Pour tous et , tels que , on a (Réfléchir à une démonstration sans calcul). On en déduit le triangle de Pascal : p n 0 1 2 3 4 5 6 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 Il en découle la formule du binôme de Newton : En posant dans cette formule , on obtient . D'où la valeur de , où désigne un ensemble à éléments : Remarque : on déduit un certain nombre de formules de la formule du binôme de Newton. A titre d'exemple, on pourra essayer de démontrer : uploads/Geographie/ probas-cours-chapitre-1.pdf