Dérangements

Les dérangements associés à un ensemble d'éléments, sont un sous-ensemble de ses permutations. Un dérangement est une permutation des éléments sans points fixes, c'est-à-dire sans élément en position identique avec la position de départ de l'ensemble.

Exemple : L'ensemble A,B,C possède 2 dérangements C,A,B et B,C,A.

La manière la plus rapide de générer la liste des dérangements d'un ensemble est de lister les permutations de celle-ci et de supprimer celles qui ont des points fixes.

Exemple : L'ensemble A,B,C' a 6 permutations : A,B,C B,A,C C,A,B A,C,B B,C,A C,B,A. Supprimer les permutations avec des points fixes, c'est à dire celles dont le A est en position 1, et/ou celles dont le B est en position 2 et/ou celles dont le C en position 3.
La liste des dérangements est composée des 2 permutations restantes : C,A,B et B,C,A.

Le dénombrement des dérangements se fait à l'aide de la sous-factorielle. Pour $ n $ éléments, le nombre de dérangements est $ !n $ (sous-factorielle de $ n $) : $$ !n = n! \sum_{k=0}^n \frac {(-1)^k}{k!} $$

Les dérangements engendrent un nombre exponentiel de valeurs et donc de calculs. Plus il y a de calculs, plus de gros serveurs de calcul sont nécessaires et coutent chers, donc les grandes générations sont payantes.