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.

ExemplesModifier

  • 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ériquesModifier

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

FormulesModifier

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)

 ,

  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éModifier

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é limiteModifier

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érencesModifier

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

Voir aussiModifier