Accueil🇫🇷Chercher

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

  1. (en) Jim Pitman, « Some Probabilistic Aspects of Set Partitions », American Mathematical Monthly, vol. 104, no 3,‎ , p. 201–209 (lire en ligne)

Voir aussi

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.