Dérangement partiel
# 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 $D_{n,k}$ le nombre de permutations de $\{1,2,\ldots ,n\}$ présentant exactement $k$ 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 ${\bigl{\begin{smallmatrix}1&2&3&4&5&6\\3&2&4&6&5&1\end{smallmatrix}}{\bigr )}$ présente 2 rencontres ; c'est un dérangement partiel d'ordre 4.
* Si sept cadeaux sont donnés à sept personnes, il y a $D_{7,2}$ 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 $D_{7,2}$ 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 $(D_{n,k})$, suite A008290 de l'OEIS :

| $_{n}\!\!\diagdown \!\!^{k}$ | 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 à $k=0$ sont les nombres de dérangements, définis par récurrence double par :

    $D_{0,0}=1,\!$
    $D_{1,0}=0,\!$
    $D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!$

Il s'avère que (voir le problème des rencontres)

    $D_{n,0}=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}=\left\lfloor {\frac {n!}{e}}\right\rceil$,

où $\left\lceil .\right\rfloor$ désigne la fonction entier le plus proche (le rapport est arrondi à la valeur supérieure si Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): n est pair et à la valeur inférieure si $n$ est impair).

Plus généralement, pour tout $0\leqslant k\leqslant n$, on a :

    $D_{n,k}={n \choose k}D_{n-k,0}$

En effet, les nombres de dérangements partiels s'obtiennent facilement à partir des nombres de dérangements : choisir les $k$ points fixes parmi les $n$ éléments, puis déranger (sans aucun point fixe donc) les $n-k$ éléments restants. Il y a ${n \choose k}$ façons de choisir les points fixes, et $D_{n-k,0}$ 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 :

    $D_{n,k}={\frac {n!}{k!}}\sum _{i=0}^{n-k}{\frac {(-1)^{i}}{i!}}$

Pour $k$ fixé et n tendant vers l'infini, on a donc :

    $D_{n,k}\sim {\frac {n!}{e.k!}}$

## 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 $\{1,2,\ldots ,n\}$ : $n!$. En divisant donc ces valeurs par $n!$, on obtient la loi de probabilité du nombre $X_{n}$ de points fixes pour une permutation aléatoire uniforme sur $\{1,2,\ldots ,n\}$. La probabilité d'avoir $k$ points fixes pour une permutation de $n$ éléments vaut donc :

    $P(X_{n}=k)={D_{n,k} \over n!}={\frac {1}{k!}}\sum _{i=0}^{n-k}{\frac {(-1)^{i}}{i!}}$

| $_{n}\!\!\diagdown \!\!^{k}$ | 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 $n\geqslant 1$, 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 $i\leqslant n$, le $i$ème moment de cette loi de probabilité est égal au $i$ème moment de la loi de Poisson de paramètre 1 ; il s'agit aussi du $i$ème nombre de Bell, i.e. le nombre de partitions d'un ensemble à $i$ éléments : $E(X_{n}^{i})=\sum _{k=0}^{n}k^{i}{\frac {D_{n,k}}{n!}}=B_{i}$ .

D'une façon générale, $E(X_{n}^{i})=\sum _{k=0}^{\min(n,i)}S(i,k)$, où $S(i,k)$ est un nombre de Stirling de seconde espèce, alors que $B_{i}=\sum _{k=0}^{i}S(i,k)$.

Pour $i>n$, le $i$ème moment de cette loi de probabilité est donc plus petit que celui de la loi de Poisson.

### Distribution de probabilité limite

On a :

    $\lim _{n\to \infty }{P(X_{n}=k)}=\lim _{n\to \infty }{D_{n,k} \over n!}={1 \over ek!}$

Il s'agit de la probabilité qu'une variable aléatoire de Poisson de paramètre 1 soit égale à $k$. 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 $k=0$ du tableau précédent : $1/e\approx$ 0,367879.

