Accueil > Non-Fiction > Créativité > Dénombrement
Wikipédia : Combinaison
Wikipédia : Triangle de Pascal
Combien de groupes de n éléments est-il possible de former dans un ensemble de k éléments ?
Voir le triangle de Pascal : ligne k, case n (la pyramide et chacune de ses lignes commencent à 0). Par exemple, pour un ensemble à 6 éléments, lire la ligne 6 en partant du sommet de la pyramide (c’est-à-dire la 7ème en comptant à partir de la ligne 0) : 1, 6, 15, 20, 15, 6, 1. Il y a donc, dans un ensemble de 6 éléments, 15 paires différentes, 20 triplets différents, et 15 quadruplets différents.
Les combinaisons des cinq couleurs de MtG se retrouvent à la ligne 5 : 1, 5, 10, 10, 5, 1. On y retrouve 10 paires différentes (les dix guildes de Ravnica), 10 triplets différents (les 5 shards d’Alara + les 5 clans de Tarkir), et 5 quadruplets différents (puisque choisir 4 couleurs revient à choisir laquelle des 5 couleurs écarter).
Cas particulier : combien de paires d’éléments (n = 2) est-il possible de former dans un ensemble de k éléments ? Réponse : 1 + 2 + … + k-2 + k-1.
Par exemple, dans un ensemble de 6 éléments, il y a 1+2+3+4+5 = 15 éléments (ce qui correspond bien la case 2 de la ligne 6 du triangle de Pascal).
Wikipédia : Permutation
Wikipédia : Factorielle
Lorsque l’ordre ou la position des éléments est important, combien est-il possible de former de permutations différentes de n éléments ? Réponse : n! (factorielle de n), soit n × n-1 × n-2 × … × 2 × 1.
Par exemple, pour ordonner 4 éléments, il existe 4×3×2×1=24 permutations possibles.
Il est possible de les énumérer en considérant que, une fois choisi le premier élément parmi l’ensemble des n éléments initialement disponibles, il en reste n-1 pour choisir le deuxième élément, puis n-2 pour choisir le troisième élément, et ainsi de suite.
Dans le cas particulier où le nombre d’emplacements est plus petit que le nombre d’éléments, il suffit d’interrompre le processus après le bon nombre d’itérations. Par exemple, s’il y a 6 éléments mais seulement 3 emplacements, le calcul sera 6×5×4 : le premier emplacement a 6 possibilités, ce qui laisse 5 possibilités pour le deuxième emplacement, et 4 pour le troisième, mais comme il n’y a pas d’autre emplacement disponible, le calcul est terminé. (Ceci n’est valable que dans le cas où l’ordre ou les positions sont importantes ; si elles ne le sont pas, il s’agit simplement d’un problème de combinaison, comme détaillé au paragraphe précédent.)