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,\dots ,n\}$ présentant exactement $k$ rencontres ; ces permutations, qui ont donc un support de cardinal Modèle:Formule, sont appelées des dérangements partiels d'ordre Modèle:Formule.

Exemples

• La permutation $\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& 2& 4& 6& 5& 1\end{array}\right)$ 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})$, Modèle:OEIS :

${}_n╲{}^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!}=\lfloor \frac{n!}{e}\rceil$,

où $\lceil .\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⩽k⩽n$, on a :

$D_{n,k}=(\genfrac{}{}{0ex}{}{n}{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 $(\genfrac{}{}{0ex}{}{n}{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 Modèle:Formule :

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

Pour $k$ fixé et Modèle:Mvar 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,\dots ,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,\dots ,n\}$. La probabilité d'avoir $k$ points fixes pour une permutation de $n$ éléments vaut donc :

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

${}_n╲{}^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⩾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⩽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 :

$\underset{n\to \mathrm{\infty }}{\lim }P(X_n=k)=\underset{n\to \mathrm{\infty }}{\lim }\frac{D_{n,k}}{n!}=\frac{1}{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

• John Riordan, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
• Modèle:MathWorld

Voir aussi

• Problème des Rencontres