Dérangement partiel

En combinatoire, le nombre de rencontres d'une permutation d'un ensemble fini de n objets est le nombre de points fixes de cette permutation. Ce nombre intervient dans le problème des rencontres. On notera le nombre de permutations de présentant exactement rencontres ; ces permutations, qui ont donc un support de cardinal , sont appelées des dérangements partiels d'ordre . La permutation présente 2 rencontres ; c'est un dérangement partiel d'ordre 4. Si sept cadeaux sont donnés à sept personnes, il y a manières que deux personnes reçoivent le cadeau qui leur était destiné. Un autre exemple classique est celui d'une école de danse avec sept couples. Après une pause, les participants doivent sélectionner au hasard un partenaire pour la suite du cours : il y a à nouveau possibilités pour que deux des couples précédant la pause soient reconstitués par le hasard. Voici le début du tableau triangulaire de la suite double , : Les nombres dans la colonne correspondant à sont les nombres de dérangements, définis par récurrence double par : Il s'avère que (voir le problème des rencontres) où désigne la fonction entier le plus proche (le rapport est arrondi à la valeur supérieure si est pair et à la valeur inférieure si est impair). Plus généralement, pour tout , on a : En effet, les nombres de dérangements partiels s'obtiennent facilement à partir des nombres de dérangements : choisir les points fixes parmi les éléments, puis déranger (sans aucun point fixe donc) les éléments restants. Il y a façons de choisir les points fixes, et façon de déranger les points non fixes. On en déduit la formule explicite pour les nombres de dérangements partiels d'ordre : Pour fixé et n tendant vers l'infini, on a donc : La somme des cases de chaque ligne de la table de la section «valeurs numériques» est le nombre total de permutations de l'ensemble : . En divisant donc ces valeurs par , on obtient la loi de probabilité du nombre de points fixes pour une permutation aléatoire uniforme sur .