COURS DE DENOMBREMENT

« COURS DE DENOMBREMENT 1/ Définition des objets : introduction Guesmi.B Dénombrer, c’est compter des objets. Ces objets sont créés à partir d’un ensemble E, formé d’éléments. A partir des éléments de cet ensemble, les objets que l’on peut former sont soit des listes d’éléments de E soit des sous-ensembles de E. A la différence des sous-ensembles, les listes peuvent utiliser plusieurs fois un même élément, et surtout, possèdent un ordre. Dans les exercices, les objets obtenus sont le résultat d’une expérience aléatoire, c’est à dire que le hasard intervient dans leur formation. Le dénombrement de ces objets, lui, n’a rien d’aléatoire, il est un décompte organisé de tous les résultats possibles d’une telle expérience. Nous allons maintenant définir avec plus de précisions les différents objets que l’on peut rencontrer et pour ce, nous allons prendre comme exemple l’ensemble suivant : Soit E un ensemble à 4 éléments : E ={ a ; b ; c ; d} Remarques : 1) le nombre d’éléments de E est appelé cardinal de E et noté card E = 4 2) les éléments de E sont 2 à 2 distincts, sinon card E ≠ 4. Créons, maintenant les conditions d’une expérience aléatoire : * prenons 4 jetons indiscernables au toucher * inscrivons sur le premier : a, sur le deuxième : b, sur le troisième : c, sur le dernier : d et plaçons-les dans un sac 1/ Définition des objets : p-uplets Expérience n°1 : Tirages successifs avec remise. * On pioche un premier jeton, par exemple : b et on le remet dans le sac. * On pioche un deuxième jeton, par exemple : a et on le remet dans le sac. * On pioche un troisième jeton, par exemple : a et on le remet dans le sac. L’expérience est terminée. Le résultat est noté à l’aide de parenthèses : ( b ; a ; a ) Les résultats possibles de cette expérience sont des listes de 3 éléments de E, avec répétition d’éléments possible. - Une liste de 3 éléments est appelée un triplet. - Plus généralement, une liste de p éléments est appelée un p-uplet ou une p-liste. Attention ! Une liste respecte un ordre : ( b ; a ; a ) ≠ ( a ; a ; b ) Dans une liste, il y a un premier élément, un deuxième élément, etc… 1/ Définition des objets : arrangements Expérience n°2 : Tirages successifs sans remise. * On pioche un premier jeton, par exemple : b que l’on ne remet pas dans le sac. * On pioche un deuxième jeton, par exemple : a que l’on ne remet pas dans le sac. * On pioche un troisième jeton, par exemple : c que l’on ne remet pas dans le sac. L’expérience est terminée. Le résultat est noté à l’aide de parenthèses : ( b ; a ; c ) Les résultats possibles de cette expérience sont des listes de 3 éléments de E, sans répétition d’éléments possible. - Une liste de 3 éléments sans répétition possible est appelée un arrangement de 3 éléments. - Plus généralement, une liste de p éléments sans répétition possible est appeléeun arrangement de p éléments de E. Remarques : 1) Cette dénomination a pour avantage de bien marquer l’importance de l’ordre dans une telle liste. 2) Un arrangement de p éléments de E est un cas particulier de p-uplet d’éléments de E. 1/ Définition des objets : permutations Expérience n°2 : Tirages successifs sans remise. Cas particulier d’arrangement : Si l’on réalise autant de pioches sans remise qu’il y a de jetons dans le sac, on obtient alors une liste de tous les éléments de E rangés dans un certain ordre. Une telle liste est appelée une permutation des éléments de E. Par exemple : ( d ; b ; c ; a ) est une permutation des éléments de E. Et : ( c ; a ; d ; b ) en est une autre. Plus généralement : un arrangement de n éléments d’un ensemble E à n éléments est appelé une permutation des éléments de E. 1/ Définition des objets : combinaisons Expérience n°3 : Tirages simultanés. * On pioche trois jetons en une seule fois, par exemple : a, d et c. Le résultat est noté à l’aide d’accolades : a ; d ; c Les résultats possibles de cette expérience sont des sous-ensembles de E ou parties de E, possédant 3 éléments. Un sous-ensemble de E comportant 3 éléments est appelé une combinaison de 3 éléments de E. Plus généralement, une partie de E possédant p éléments est appelée une combinaison de p éléments de E. - L’ensemble d ; a ; c possède les mêmes éléments que l’ensemble a ; d ; c Ils sont donc égaux. Par conséquent, contrairement aux listes, l’ordre d’écriture des éléments d’une combinaison n’a pas d’importance. Cette absence d’importance de l’ordre est marquée par l’utilisation de l’écriture avec accolades,écriture réservée aux ensembles. 2/ Dénombrement : arrangements Nous savons ce qu’est, par exemple, un arrangement de 3 éléments de E, mais le problème est maintenant de trouver combien on peut former de listes de ce type. Deux grandes techniques de dénombrement existent. Voici la première de ces techniques, appliquée au dénombrement des arrangements de 3 éléments de l’ensemble E, défini plus haut : Technique de l’arbre : Il y a 4 choix pour le premier élément de la liste. Puis, à chaque choix fait pour le premier élément correspond pour le deuxième élément un même nombre de choix : 3. ( = nombre de choix possibles parmi les (4-1) éléments restants, car la liste est sans répétition ) Puis, à chaque choix fait pour le deuxième élément correspond pour le troisième élément un même nombre de choix : 2. ( = nombre de choix possibles parmi les (4-2) éléments restants, car la liste est sans répétition ) En bout de branches, nous récupérons les différents arrangements possibles. A chaque stade de choix, chaque branche « éclatant » en un même nombre de choix, les arrangements possibles sont au nombre de : 4x3x2 = 24. Soit : (4-0)x(4-1)x(4-2). Ou encore : 4x(4-1)(4-(3-1)). Technique des cases : « Fabriquer » un arrangement de 3 éléments de E, équivaut à remplir les 3 cases suivantes avec des éléments 2 à 2 distincts : Il y a 4 choix possibles pour le premier élément. Puis le choix du premier élément étant fait, il reste 3 choix possibles pour le deuxième. Et enfin, le choix des deux premiers éléments étant fait, il reste 2 choix possibles pour le dernier. Remarque : cette technique équivalente à celle de l’arbre, est parfois plus pratique quand par exemple un élément de la liste est connu ainsi que sa position. Cas général : soit un entier naturel n > 1, et soit p entier naturel tel que : 1 < p < n p n Le nombre d’arrangements de p éléments d’un ensemble E à n éléments est noté : A Et en généralisant le raisonnement tenu sur le cas particulier, on a : 2/ Dénombrement : permutations * Si p = n, on dénombre alors les permutations d’éléments de E. Sur notre cas particulier, en utilisant par exemple la technique des cases, on trouve qu’il existe : 4x3x2x1 permutations des éléments de E. Soit : 24 permutations des 4 éléments de E. Plus généralement, une permutation étant un arrangement de n éléments de E, il en existe : Soit : Cas général : pour tout entier n > 1 Le nombre de permutations d’un ensemble à n éléments est noté : n ! (se lit "factoriel n") Avec : Remarques : 1) D’un point de vue calculatoire ( qui perd le sens Il s’agit tout simplement du produit des n du dénombrement ) : premiers entiers. 2) Par convention : 0 !=1 2/ Dénombrement : p-uplets Toujours avec notre exemple, en dénombrant à l’aide de la technique des cases et en tenant compte du fait que la répétition d’un même élément est possible :.... »