Nombre moyen de points fixes d'une permutation

jeremyjeff

Bonsoir,

Je cherche à résoudre cet exercice :
"Déterminer le nombre moyen de points fixes d'une permutation à n éléments".

Voici comment j'ai procédé:
J'appelle dn le nombre de permutations sans points fixes sur n éléments.
Le nombre de permutations sur n éléments ayant k points fixes exactement est donc : Cnk dn-k.
La probabilité qu'une permutation tirée de manière uniforme est k points fixes est donc :
pk,n= (1/ n ! ) * Cnk dn-k = (dn-k) / (k! (n-k)! ).

Le nombre moyen cherché est l'espérance de la variable aléatoire: "nombre de points fixes" :
mn = somme (k=0, n) k pk,n = somme (k=1, n) ( dn-k ) / ( (k-1) ! (n-k) ! )

Et là je bloque sur le calcule de cette somme.

Est-ce la bonne méthode ?
Ai-je fait une erreur ?

Merci

AitJoseph

Que veux-tu dire par nombre moyen ?

Salut

Lucas

Il y a beaucoup, beaucoup, beaucoup plus simple. Un indice : utilise la linéarité de l'espérance.

egoroffski

En fait, on peut faire beaucoup plus efficace en exploitant la linéarité de l'espérance. Pour $1 \leq k \leq n$, si $X_k$ est la variable aléatoire qui vaut $1$ si $k$ est un point fixe et $0$ sinon, quelle est la loi de $X_k$ ? Que représente $X_1+\cdots +X_n$ ?

JLT

Autre méthode : utiliser la formule de Burnside.

jeremyjeff

Bonjour,

Que représente X_1+...+X_n ?

La valeur de la moyenne qu'on recherche.

Par contre j'ai du mal à trouver une formule générique pour la loi de X_k

Cordialement

egoroffski

jeremyjeff a écrit:

Que représente $X_1+\cdots+X_n$ ?
La valeur de la moyenne qu'on recherche.

J'aurais écrit "la valeur variable {\bf dont} on recherche la moyenne l'espérance" : $X_1+\cdots+X_n$ représente le nombre de points fixes, et c'est l'espérance de cette variable qu'on souhaite calculer. Erreur de français ou de maths ?

Pour ton autre question : tu peux commencer par $k=1$. Si tu modélise le choix d'une permutation au hasard par l'équiprobabilité sur $\Omega=\mathfrak{S}_n$, alors $X_1(\omega)=1$ si et seulement si $\omega(1)=1$, et $X_1(\omega)=0$ sinon, donc $X_1$ suit une loi de Bernoulli de paramètre $p=\mathbb{P}(\omega(1)=1)$, et il suffit de calculer $p$ pour caractériser sa loi (et calculer son espérance).

jeremyjeff

OK, merci

Par contre, avec cette méthode, n'y-a-t-il pas des problèmes de redondances, ie :
1 peut être point fixe
2 peut être point fixe,
1 et 2 peuvent être point fixes en même temps ..

Cordialement

h

L'espérance (ou l'intégrale ou la somme, comme tu veux) est linéaire. Le problème que tu soulèves n'existe donc pas.

egoroffski

Justement, c'est l'interêt de cette méthode : la linéarité de l'espérance fait qu'on a pas à se soucier de ce genre de problèmes. Alors qu'avec la méthode que tu proposais initialement, il faut dénombrer des choses très compliquées.

jeremyjeff

p(X₁=1) = (n-1) ! / n ! = 1/ n
(On fixe 1 à sa place et on permutte les autres nombres).

Tous les X_i jouent le même rôle :

P(X₁=1) = P(X₂=1) = ... P(X_k=1)

L'espérance vaut :
E(x) = X₁+X₂+...+X_n = n * p = 1

C'est correct ?

Cordialement

egoroffski

Presque : l'espérance vaut $E(X_1)+\cdots+E(X_n)$, et pas $X_1+\cdots+X_n$.

jeremyjeff

exact.

une petite question à présent :
Avec ma 1ère méthode de dénombrement, peut-on aboutir ?
Quid de la formule de Burnside ?

Cordialement

JLT

La formule de Burnside dit que le nombre moyen de points fixes est égal au nombre d'orbites. Et comme il n'y a qu'une seule orbite...

bisam

Pour répondre à jeremyjeff : oui, on peut aboutir avec ta première méthode... mais il faut déjà connaître la valeur de $d_n$ (la dénomination courante est le nombre de "dérangements" de $n$ éléments) en fonction de $n$.
On obtient une expression de $d_n$ avec la formule du crible ou encore avec la formule d'inversion de Pascal.

Ensuite, il faut faire une interversion des signes $\sum$ et un changement d'indices pour aboutir au résultat voulu.

skyrmion

Bonjour,

Comme dit plus haut dans ce fil, le nombre moyen de points fixes d'une permutation de $S_n$ est donc égal à 1. Il y a d'autres choses marrantes à calculer pour les permutations (des immédiates ou évidentes par définition et d'autres beaucoup moins):
\begin{itemize}
\item Le nombre d'orbites d'une permutation.
\item Le nombre moyen d'orbites
\item La loi de répartition du nombre d'orbites.
\item Le nombre de points fixes d'une permutation.
\item Le nombre moyen de points fixes.
\item La loi du nombre de points fixes (Quelqu'un connait un résultat à ce sujet?)
\item Le nombre d'orbites de cardinal fixé
\item Le nombre moyen de ces orbites de cardinal fixé
\item La probabilité d'avoir un dérangement
\item La probabilité d'avoir aucune orbite de longueur donnée
\end{itemize}

Cordialement, sk.

Durtal

Sur un sujet un peu voisin il y a cet article : http://www.normalesup.org/~kortchem/travaux/records-cycles-rms.pdf

Jux

skyrmion a écrit:

La loi du nombre de points fixes (Quelqu'un connait un résultat à ce sujet?

On peut calculer explicitement la loi du nombre de points fixe d'une permutation tiré uniformément dans $\mathfrac{S}_n$ par inclusion-exclusion, et celle-ci converge étroitement vers la loi de Poisson de paramètre 1. Pour le nombre d'orbites de cardinal k, on a encore convergence, vers une Poisson(k). Il me semble que ces résultats sont dus à Goncharov et Feller.

JLT

Pour la loi du nombre de points fixes, on voit facilement apparaître la loi de Poisson : il est connu que le nombre de dérangements $d_n$ est environ égal à $n!/e$ lorsque $n$ est grand.

Le nombre de permutations ayant $k$ points fixes est $\binom{n}{k}d_{n-k}\simeq \dfrac{n!}{k!e}$ donc la probabilité pour une permutation d'avoir $k$ points fixes est environ $1/(k!e)$.

marc0075

N'y aurait il pas redondance ?

car avoir exactement k points fixes EQUIVAUT à n'avoir  aucun point fixe sur (n-k) éléments et comme Dn-k les comptabilise tous    ......

Merci de préciser les choses

bisam

Tout d'abord, je te fais remarquer que tu viens de poster dans une discussion vieille de presque 12 ans. Il y a peu de chances que les interlocuteurs d'origine te répondent.

Mais le hasard fait bien les choses... Je te réponds et, visiblement, je l'avais déjà fait à l'époque.

Ici, le facteur $\binom{n}{k}$ vient du fait qu'il faut choisir quels sont les points fixes parmi les $n$ valeurs, avant de compter le nombre de permutations ayant exactement ces $k$ points fixes (et donc les $n-k$ autres valeurs qui sont "dérangées").

Riemann_lapins_cretins

J'avais déjà résolu par approche probabiliste.

Il y a une approche combinatoire sinon, consistant à multiplier la somme définissant l'espérance par n! et compter le nombres de couples (x, s) où x est point fixe de s "d'abord par les x, et ensuite par les s".

Chaurien

On peut aussi penser à une attaque combinatoire, sans probabilité, comme une statistique sur les permutations, en attachant à chacune le nombre de ses points fixes. C'est ce que disait initialement @jeremyjeff : pour $n \in \mathbb N^*$  et $k \in \mathbb N$, on note $d_{n,k}$ le nombre de permutations de $ [\![1,n]\!]$ ayant $k$ points fixes, et $d_n=d_{n,0}$ le nombre de permutations de $ [\![1,n]\!]$ sans point fixe (dérangements). La moyenne demandée est $E=\frac{\sum_{k=0}^{n}kd_{n,k}}{\sum_{k=0}^{n}d_{n,k}}$.

La clé, c'est l'égalité $d_{n,k}=\binom {n}{k} d_{n-k}$ pour $n \in \mathbb N$, $k \in \mathbb N$, $ 0\le k \le n$. Noter que $d_0=1$, soit par convention, soit parce que l'application vide, qui est bijective, n'a pas de point fixe (elle n'a pas de « point » du tout...).

 Pas besoin d'avoir l'expression de $d_n$, qui est par ailleurs une question classique, mais n'est pas indispensable ici. Il est clair que $\sum_{k=0}^n d_{n,k}=n!$ (nombre total de permutations de $ [\![1,n]\!]$). Alors la moyenne cherchée est $E=\frac 1{n!} \sum_{k=0}^n k d_{n,k}$, soit : $E=\frac 1{n!} \sum_{k=0}^n k \binom {n}{k} d_{n-k}$. @jeremyjeff avait fait une grande partie du chemin.

Il suffit d'appliquer la formule bien connue, pour $n \ge 1$ et $ k \ge 1$ : $ k \binom {n}{k} = n\binom {n-1}{k-1}$. Résultat curieux : $E=1$.

Cette question faisait l'objet du problème 1 de la 28e Olympiade internationale, Cuba 1987.

Chaque fois qu'on demande une moyenne, moi je pense aussi à la variance : $V=\frac 1{n!} \sum_{k=0}^n (k-E)^2 d_{n,k}$. Joli résultat : on trouve encore $V=1$.

J'ai posé ça naguère en prépa-HEC.

Bonne journée.

Fr. Ch.