Inscription / Connexion Nouveau Sujet
Niveau maths spé
Partager :

nombre moyen d'inversions pour uns permutation

Posté par
math71
29-06-17 à 11:43

Bonjour,
Je dois trouver le nombre moyen d'inversions pour une permutation de Sn
En premier lieu j'avais déjà du chercher le nombre moyen de points fixes pour une permutation et cela je l'ai réussi, j'ai trouvé 1.
Pour les inversions je ne sais pas comment m'y prendre. Intuitivement j'aurais tendance à dire que le résultat sera E(n/2), puisqu'il y a à mon avis autant de chance d'avoir une inversion que de ne pas en avoir, mais ceci n'est pas du tout un raisonnement mathématique et c'est juste pour conforter la réponse que je pourrais trouver par raisonnement mathématiques !

Posté par
verdurin
re : nombre moyen d'inversions pour uns permutation 29-06-17 à 14:11

Bonjour,
pour le nombre moyen de points fixes, c'est une limite.

Pour les inversions, ton raisonnement se formalise assez bien, mais le nombre de paires d'un ensemble à n éléments n'est pas égal à n.

Pour la formalisation : il faut montrer que la probabilité pour que la paire {i;j} soit inversé par une permutation prise au hasard avec équiprobabilité dans Sn est égale à 1/2. ( C'est vrai. )
Puis utiliser la linéarité de l'espérance.

Posté par
math71
re : nombre moyen d'inversions pour uns permutation 29-06-17 à 16:08

Si l'on considère les paires {i;j} avec i et j choisis entre 1 et n, pour les compter je choisis d'abord i donc n choix possibles, puis je choisis j parmi les nombres restant donc n-1 choix possibles et là j'ai chaque paire en double puisque {i,j} donne aussi {j,i}. Donc en fait j'ai
n(n-1)/2 paires {i;j} avec i<j.
On se donne une paire (i,j) de 2 nombres distincts pris entre 1 et n et on considère l'expérience "prendre une permutation s au hasard dans Sn" et l'événement A "la paire (i,j) est inversée par la permutation s choisie"
Il y n! permutations au total.  J'ai du mal à comptabiliser les permutations qui inversent i et j, je ne vois pas trop comment m'y prendre de manière rationnelle

Posté par
verdurin
re : nombre moyen d'inversions pour uns permutation 29-06-17 à 16:54

On peut associer à chaque permutation \sigma la permutation \sigma^* définie par :

\begin{cases} \sigma^*(k)=\sigma(k) \text{ si } k\not \in \lbrace i\, ; j\rbrace \\ \sigma^*(i)=\sigma(j)\\ \sigma^*(j)=\sigma(i)\end{cases}
 \\
Puis monter que l'application \sigma\mapsto \sigma^* est bijective de S_n dans S_n, et conclure sans compter.

Posté par
math71
re : nombre moyen d'inversions pour uns permutation 30-06-17 à 08:54

Notons F l'application que vous me donnez.
Donnons-nous 2 permutations s et t telles que F(s)=F(t)
Donc s(k)=t(k) pour tout k différents de i et de j
s(i)=F(s)(j)=F(t)(j)=t(i), de même pour j donc finalement s=t ce qui prouve que F est injective, comme elle agit sur un ensemble fini cela signifie qu'elle est bijective.
Or * n'est pas une inversion de {i,j} si en est une et inversement, ce qui signifie qu'il y a autant d'inversions de {i,j} que de non-inversion, il y en a donc autant l'une que l'autre, il y en a donc une probabilité de 1/2 que {i,j} présente une inversion.
Après je ne vois pas trop où je dois utiliser la linéarité de l'espérance.

Posté par
math71
re : nombre moyen d'inversions pour uns permutation 30-06-17 à 09:00

J'ai envoyé ma réponse trop vite.
En fait je considère la variable aléatoire Yi:j sur Sn qui vaut 1 si {i,j} présente une inversion et 0 sinon.
Puis X = la somme de tous les Yi,j
On a E(X)=E(Yi,j)=nombre de paires {i,j}x1/2=n(n-1).

Posté par
math71
re : nombre moyen d'inversions pour uns permutation 30-06-17 à 09:01

E(X)=n(n-1)/4 et non n(n-1) bien sûr!

Posté par
math71
re : nombre moyen d'inversions pour uns permutation 30-06-17 à 09:03

Merci Verdurin!

Posté par
verdurin
re : nombre moyen d'inversions pour uns permutation 30-06-17 à 22:53

Service



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1741 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !