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 ${\displaystyle D_{n,k}}$ le nombre de permutations de ${\displaystyle \{1,2,\ldots ,n\}}$ présentant exactement ${\displaystyle k}$ rencontres ; ces permutations, qui ont donc un support de cardinal n – k, sont appelées des dérangements partiels d'ordre n – k.

• La permutation ${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle D_{7,2}}$ possibilités pour que deux des couples précédant la pause soient reconstitués par le hasard.

Voici le début du tableau triangulaire de la suite double ${\displaystyle (D_{n,k})}$, suite A008290 de l'OEIS :

${\displaystyle _{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

Les nombres dans la colonne correspondant à ${\displaystyle k=0}$ sont les nombres de dérangements, définis par récurrence double par :

${\displaystyle D_{0,0}=1,\!}$

${\displaystyle D_{1,0}=0,\!}$

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

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

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

où ${\displaystyle \left\lceil .\right\rfloor }$ désigne la fonction entier le plus proche (le rapport est arrondi à la valeur supérieure si ${\displaystyle n}$ est pair et à la valeur inférieure si ${\displaystyle n}$ est impair).

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

${\displaystyle 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 ${\displaystyle k}$ points fixes parmi les ${\displaystyle n}$ éléments, puis déranger (sans aucun point fixe donc) les ${\displaystyle n-k}$ éléments restants. Il y a ${\displaystyle {n \choose k}}$ façons de choisir les points fixes, et ${\displaystyle 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 :

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

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

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

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

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

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

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

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

On a :

${\displaystyle \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 à ${\displaystyle 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 ${\displaystyle k=0}$ du tableau précédent : ${\displaystyle 1/e\approx }$ 0,367879.

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

• Problème des Rencontres

• Portail des mathématiques
• Portail des probabilités et de la statistique