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 $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.

Références

• Riordan, John, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
• (en) Eric W. Weisstein, « Partial Derangements », sur MathWorld

Voir aussi

• Problème des Rencontres