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 n – k, sont appelées des dérangements partiels d'ordre n – k.
Exemples
- 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.
Valeurs numériques
Voici le début du tableau triangulaire de la suite double , suite A008290 de l'OEIS :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|---|
0 | 1 | |||||||
1 | 0 | 1 | ||||||
2 | 1 | 0 | 1 | |||||
3 | 2 | 3 | 0 | 1 | ||||
4 | 9 | 8 | 6 | 0 | 1 | |||
5 | 44 | 45 | 20 | 10 | 0 | 1 | ||
6 | 265 | 264 | 135 | 40 | 15 | 0 | 1 | |
7 | 1854 | 1855 | 924 | 315 | 70 | 21 | 0 | 1 |
Formules
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 n – k :
Pour fixé et n tendant vers l'infini, on a donc :
Distribution de probabilité
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 . La probabilité d'avoir points fixes pour une permutation de éléments vaut donc :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|---|
0 | 1 | |||||||
1 | 0 | 1 | ||||||
2 | 0.5 | 0 | 0,5 | |||||
3 | 0,33333 | 0,5 | 0 | 0,16667 | ||||
4 | 0,375 | 0,33333 | 0,25 | 0 | 0,04167 | |||
5 | 0,36667 | 0,375 | 0,16667 | 0,08333 | 0 | 0,00833 | ||
6 | 0,36806 | 0,36667 | 0,1875 | 0,05556 | 0,02083 | 0 | 0,00139 | |
7 | 0,36786 | 0,36806 | 0,18333 | 0,0625 | 0,01389 | 0,00417 | 0 | 0,00020 |
Pour , l'espérance du nombre de points fixes est égale à 1, tout comme pour la loi de Poisson de paramètre 1. Plus généralement, pour , le ème moment de cette loi de probabilité est égal au ème moment de la loi de Poisson de paramètre 1 ; il s'agit aussi du ème nombre de Bell, i.e. le nombre de partitions d'un ensemble à éléments[1] : .
D'une façon générale, , où est un nombre de Stirling de seconde espèce, alors que .
Pour , le ème moment de cette loi de probabilité est donc plus petit que celui de la loi de Poisson.
Distribution de probabilité limite
On a :
Il s'agit de la probabilité qu'une variable aléatoire de Poisson de paramètre 1 soit égale à . Ainsi le nombre de points fixes converge en loi vers une loi de Poisson de paramètre 1. On constate la vitesse de cette convergence avec la colonne du tableau précédent : 0,367879.
Références
- (en) Jim Pitman, « Some Probabilistic Aspects of Set Partitions », American Mathematical Monthly, vol. 104, no 3,‎ , p. 201–209 (lire en ligne)
- Riordan, John, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
- (en) Eric W. Weisstein, « Partial Derangements », sur MathWorld