Dérangement

Quatre personnes déposent chacune un chapeau, puis les quatre chapeaux sont redistribués. L'attribution forme un dérangement si personne ne récupère le sien. Chacun reçoit bien un chapeau, et chaque chapeau n'est donné qu'une fois : seule la place d'origine est interdite.

Il ne suffit donc pas que quelques chapeaux changent de propriétaire. Une seule personne retrouvant son chapeau crée un point fixe et invalide toute l'attribution.

Un dérangement est une permutation d'un ensemble fini qui ne possède aucun point fixe. Une permutation réorganise tous les éléments sans omission ni répétition. Un point fixe est un élément envoyé sur lui-même. Ainsi, chaque élément doit occuper une position différente de sa position initiale.

Pour un ensemble de n éléments, le nombre de dérangements est noté D_n. La factorielle de n, notée n!, est le produit des entiers de 1 à n ; par convention, 0! = 1, ce qui correspond au produit vide. Le principe d'inclusion-exclusion part des n! permutations, retranche celles qui fixent au moins un élément, puis corrige les recouvrements. Dans la somme obtenue, l'indice k désigne le nombre de positions imposées comme fixes :

Le nombre d'Euler e fournit une approximation simple : la proportion D_n/n! se rapproche de 1/e lorsque n augmente, si bien que D_n est approximativement égal à n!/e. Ce résultat est connu sous le nom de problème des dérangements ou des chapeaux de Montmort.

Les personnes A, B, C et D possèdent les chapeaux A, B, C et D. La redistribution doit donner un chapeau à chacune, sans restituer le sien. La figure montre une possibilité : A reçoit B, B reçoit D, C reçoit A et D reçoit C.

1. Sans interdiction, les quatre chapeaux peuvent être attribués de 4! = 4 × 3 × 2 × 1 = 24 façons.

2. Fixer une personne laisse 3! attributions. On retranche donc 4 × 3! = 24, et le sous-total vaut 24 − 24 = 0.

3. Fixer deux personnes donne 6 paires et 2! placements restants. On rétablit 6 × 2! = 12, d'où le sous-total 0 + 12 = 12.

4. Les 4 choix de trois personnes fixes donnent 4 × 1! = 4 à retrancher. L'unique cas où les quatre sont fixes donne 1 à ajouter.

5. Ainsi, D₄ = 24 − 24 + 12 − 4 + 1 = 9 dérangements. Pour contrôler, 4!/e ≈ 8,83 ; son entier le plus proche est bien 9.

Pour vérifier une redistribution déjà donnée, comparez chaque destinataire à l'étiquette du chapeau reçu. Ce contrôle position par position suffit ; un comptage complet n'est utile que si l'on cherche toutes les attributions possibles.

Pour compter les distributions acceptables, l'énumération directe convient à un très petit nombre de chapeaux. Lorsque la liste devient longue, la formule d'inclusion-exclusion évite de parcourir toutes les permutations une à une.

Pour obtenir une probabilité exacte sous une redistribution uniforme, divisez le nombre de dérangements par le nombre total de permutations. Avec quatre personnes, elle vaut 9/24, soit 3/8. Pour un grand nombre de personnes, 1/e fournit plutôt une approximation rapide.

Une permutation quelconque. Elle peut laisser des éléments à leur place, tandis qu'un dérangement n'en laisse aucun. L'attribution A reçoit A, B reçoit C, C reçoit D et D reçoit B est une permutation, mais pas un dérangement, car A est fixe.

Un tirage sans répétition. Donner chaque chapeau une seule fois garantit une permutation, mais pas l'absence de point fixe. Si les quatre personnes reprennent leur propre chapeau, il n'y a aucune répétition et pourtant aucun dérangement.

Ensemble vide. Par convention, il existe une permutation de zéro élément, et elle n'a aucun point fixe : D₀ = 1. Ce cas sert notamment à faire fonctionner le dernier terme de la formule.

Un seul élément. La seule permutation le laisse en place, donc D₁ = 0. À partir de deux éléments, des dérangements existent ; pour deux éléments, l'unique possibilité échange les deux places.

Approximation mal interprétée. Le quotient n!/e n'est généralement pas un entier et ne remplace pas le comptage exact. Pour quatre éléments, 4!/e ≈ 8,83 alors que le nombre exact est 9.

Une seule position autorisée. Exiger seulement qu'un élément précis change de place ne suffit pas. Il faut contrôler les n positions : le moindre point fixe exclut la permutation.

Permutation paire — Pour étudier une autre propriété structurelle des permutations, fondée sur leur décomposition en échanges plutôt que sur leurs points fixes.