Forum de mathématiques - Bibm@th.net

jacco78

Invité

Somme permutation

Bonjour
$n\geq 2$  $1\leq k \leq n$ des entiers, $T(p,k)=\sum_{j=1}^{p(k)} p(j)=p(1)+p(2)+...+p(p(k))$
Calculer $\frac{1}{n!}\sum_{p \in S_n} T(p,k)$
J'ai étudié les cas n=2, n=3 comment aborder le cas général. J'ai vu qu'une permutation se décompose en produit
de transpositions, le cardinal de $S_n$ est $n!$
Merci à vous

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Somme permutation

Bonjour,

  Est-ce que tu pourrais préciser les notations dans $T(p,k)$ : $p$ est bien une permutation de $S_n$?
On somme bien jusque $p(k)$???

Et qu'as-tu trouvé pour les cas $n=2$ et $n=3$?

F.

jacco78

Invité

Re : Somme permutation

Ha oui $p$ est une permutation de $S_n$
---------------
Pour $n=2$

Si $k=1$, pour $p=Id$ on a $T(p,1)=p(1)+p(p(1))= 1+1=2$, pour la transposition $p=(12)$ on a $T(p,1)=p(1)+p(p(1))=2+2$
ce qui donne $(1+1+2+2)/2=3$

Si $k=2$ pour $p=Id$ on a $T(p,2)=p(1)+p(p(2))= 1+2=3$, pour la transposition $p=(12)$ on a $T(p,1)=p(1)+p(p(1))=2+1=3$
ce qui donne $(3+3)/2=3$

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Somme permutation

Re-

  Sauf si je n'ai pas compris la définition, je ne suis pas d'accord avec tes calculs.
Pour $k=1,$ et pour $p=Id,$ on a $p(1)=1$ et donc la somme ne comporte qu'un élément : $T(p,1)=1.$
Pour la transposition $p=(1\ 2),$ on a $p(1)=2$ et donc la somme comporte deux élements : $T(p,1)=p(1)+p(2)=2+1=3.$
Finalement, le résultat que l'on doit trouver, c'est $2$, non????

Que se passe-t-il pour $k=2$???

F.

jacco78

Invité

Re : Somme permutation

En effet pour $k=1$ je n’ai pas bien vu.

Pour $k=2$
Si $p=Id$ on a $p(2)=2$ donc $T(p,2)=p(1)+p(2)=1+2=3$
Si $p=(12)$ transposition on a $p(2)=1$ donc $T(p,2)=p(1)=2$
Ce qui donne $(3+2)/2=5/2$ sous réserve que je n’ai pas fait de fautes.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Somme permutation

Re-

  Au moins si $k=1,$ je suis tenté par faire une permutation des deux sommes... Attention, ce n'est pas si facile!

F.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

Bonjour,

On peut voir ce qu'on demande de calculer comme une espérance d'une somme de variables aléatoires indexées par $j\in \{1,\ldots,n\}$, définies sur $\Omega= \mathfrak S_n$, avec équiprobabilité : on pose $X_j(p)= \mathbf 1_{j\leq p(k)} p(j)$, alors $T(p,k)= \sum_{j=1}^n X_j(p)$ et on doit donc calculer $\mathbf E( \sum_{j=1}^n X_j)=\sum_{j=1}^n\mathbf E(X_j)$. Je n'ai pas poussé, maix c'est peut-être une façon de s'en sortir.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

Allez, je commence par le plus facile  : $\mathbf E(X_k)=\dfrac{n-k+1}{n}\times \dfrac{n+k}2$. Yapuka calculer $\mathbf E(X_j)$ pour $j\neq k$.

jacco78

Invité

Re : Somme permutation

je cherche à trouver une solution sans variables aléatoires ni probabilité( je ne sais si c’est possible )
Pour le moment je voudrai permuter les somme, ce me qui gêne $p(k)$ dans la deuxième somme

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

L'utilisation du formalisme de l'espérance d'une somme de varibles aléatoires permet justement de "permuter les sommes" en ayant une bonne visibilité de ce qu'on fait.
Pourquoi refuses tu cette voie ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

Et pour $j\neq k$, sauf erreur, $\mathbf E(X_j)=\dfrac{(n+1-j)(n^2-j)}{2n(n-1)}$ .

jacco78

Invité

Re : Somme permutation

En fait je ne suis pas à l’aise avec cette méthode pour calculer $E(X_i)$, mais je peux essayer de voir commenter  ça marche
je sais si une v.a. X prend ses valeurs $a(1),…,a(t)$ de probabilité $q(1),…,q(t)$ alors
$Ei(X)= a(1)p(1)+…+a(t)p(t)$.
Dans $X_k(p)=1_{j\leq p(k}p(j)$ donne que cette v.a. prend comme valeurs $1$ si $j \leq p(k)$ et $0$ si $j>p(k)$ de probabilités
$q(1)=…=q(t)=1/n!$( je ne suis pas sûr) et  je ne vois pas ce qu’il faut choisir pour t ?

jacco78

Invité

Re : Somme permutation

Est-ce $t=p(k)$ ? Du coup $E(X_k)= \sum_{j=1}^{p(k)}1/n!$ là je reviens à la case départ. Que faut-il faire ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

Dis donc, on n'est pas dans le même fuseau horaire ou alors tu as des insomnies !

Ici les variables aléatoires $X$ sont définies sur l'ensemble des permutations $S_n$ (toutes les permutations étant équiprobables, chacune de proba $\dfrac1{n!}$). L'espérance d'une telle variable aléatoire $X$ est la moyenne des valeurs $X(p)$ pour toutes les permutations $p$ : $\mathbf E(X)= \dfrac1{n!}\,\sum_{p\in S_n}X(p)$. Tu vois donc que ce tu as à calculer est l'espérance de la variable aléatoire $p\mapsto T(p,k)$. Or cette variable aléatoire est la somme des variables aléatoires $X_j=\mathbf 1_{j\leq p(k)}\,p(j)$ (rappelons que la fonction indicatrice $\mathbf 1_{j\leq p(k)}$ vaut $1$ pour les permutations $p$ telles que $j\leq p(k)$ et $0$ pour les autres). Et on sait que l'espérance d'une somme est la somme des espérances (propriété de linéarité de l'espérance).

Venons-en au calcul de l'espérance de $X_k$. $p(k)$ prend de manière équiprobable les valeurs $1,2,\ldots,n$ (il y a autant de permutations qui envoient $k$ sur $1$ que $k$ sur $2$ que ..., à savoir $(n-1)!$). La fonction indicatrice $\mathbf 1_{k\leq p(k)}$ sélectionne les permutations qui prennent en $k$ une des $n+1-k$ valeurs $k,k+1,\ldots, n$, et la moyenne de ces valeurs est $(k+n)/2$. Donc
$$\mathbf E(X_k) = \frac{n+1-k}{n}\times \frac{k+n}{2}\;.$$
Le calcul de $\mathbf E(X_j)$ pour $j\neq k$ est un peu plus compliqué. Ici on utilise le fait que $p(k)$ prend de manière équiprobables les valeurs $1,2,\ldots, n$ et qu'ensuite $p(j)$ prend de manière équiprobable les $n-1$ valeurs différentes de $p(k)$.

Dernière modification par Michel Coste (03-10-2023 09:13:46)

jacco78

Invité

Re : Somme permutation

En suivant tes idées de #14 pour l’espérance $E(X_j)=\frac{(n+1-j)(n^2-j)}{2n(n-1)} $ pour $j\neq k$ la quantité $ (n+1-j)$
c’est lié à $1_{j\leq p(k)}$ et $\frac{n^2-j}{2n(n-1)}$ est une moyenne ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

L'indicatrice $\mathbf 1_{j\leq p(k)}$ sélectionne les $n+1-j$ valeurs $j,j+1,\ldots,n$ pour $p(k)$. Si $p(k)=\ell$ est une de ces valeurs, $p(j)$ peut prendre de manière équiprobable toutes les valeurs de $1$ à $n$, sauf $\ell$, ce qui fait $n-1$ valeurs.
À partir de ces constatations et avec un peu de soin, on peut calculer $\mathbf E(X_j)$.

jacco78

Invité

Re : Somme permutation

Pour une autre piste pour calculer $W=\sum_{p \in S_n} (\sum_{j=1}^{p(k)} p(j) ) $ j’essaie de permuter les sommes
en notant $p_1,p_2,…,p_{n!}$ les éléments de $S_n$ on a
$W=\sum_{h=1}^{n!} \sum_{j=1}^{p_h(k)} p_h(j)=\sum_{j=1}{n} \sum_{h=1}^{n!} p_h(j)1$
ça ne paraît pas être juste.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

Non, ce n'est pas juste ; tu as oublié le $j\leq p(k)$.

Ce qui est juste, c'est $$W=\sum_{j\in \{1,\ldots,n\},\ p\in S_n;\ j\leq p(k)} p(j) = \sum_{j=1}^n\sum_{p\in S_n;\ j\leq p(k)} p(j)\;.$$
Et on peut remarquer que $ \sum_{p\in S_n;\ j\leq p(k)} p(j)$, c'est $n!$ fois l'expérance de ma variable aléatoire $X_j$. Tu peux travailler directement avec cette expresion, si tu te sens plus à l'aise.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

Un petit programme python pour calculer le $W$ :

from itertools import permutations

def T(p,k) :
    t=0
    for j in range(p[k-1]) : t += p[j]
    return t

def W(n,k) :
    Sn = permutations(range(1,n+1))
    return sum(T(p,k) for p in Sn)

Ça calcule, mais pas très vite dès que $n$ augmente un peu  :

%time W(12,7)

CPU times: user 5min 1s, sys: 23.6 ms, total: 5min 1s
Wall time: 5min 1s

20502720000

Avec la formule calculée par la méthode que j'ai indiquée, ça va nettement plus vite :

%time U(12,7)

CPU times: user 8 µs, sys: 0 ns, total: 8 µs
Wall time: 10.5 µs

20502720000

Heureusement, ça trouve bien le même résultat.

jacco78

Invité

Re : Somme permutation

Existe-t-il des logiciels de maths qui donnent  une forme close de W ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 475

Re : Somme permutation

À partir de la somme avec des permutations, ça m'étonnerait. Mais faire la somme sur $j$ à partir des formules que j'ai données plus haut, ça se fait à la main sans problème. C'est comme cela que j'ai procédé pour donner une formule close à Python.

jacco78

Invité

Re : Somme permutation

Oui pour calculer W les formules $1+2+...+N=N(N+1)/2$ et $1^2+2^2+3^3+...+N^2=N(N+1)(2N+1)/6$
je ne trouve pas de forme factoriser

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 913

Re : Somme permutation

Bonjour,

J'ai vérifié "à la paluche" que les calculs pour j=k d'une part, j différent de k d'autre part , donnés par Michel sont parfaitement exacts.
(Un peu pénible tout de même).
Il reste à sommer tout cela vis à vis de j, ce qui est possible je suppose en développant les facteurs, en connaissant les sommes classiques d'entiers consécutifs, et de leurs carrés. J'avoue manquer de peps pour le faire.

J'avais essayé de trouver une transformation bijective sur les p -> p'  pour symétriser la question vis à vis des indices ( p(k) sup. à j devenant p'(k) inf. à j )  , afin de simplifier la somme interne sur les permutations (à un facteur 2 près) , mais ça n' a pas fonctionné.

[ ironie du sort ??: dans les résultats le facteur 2 apparaît ainsi que n+1-j , changement d'indice que j'avais tenté pour inverser la vapeur sur p , peut-être matière à creuser davantage ]

Alain

Dernière modification par bridgslam (06-10-2023 14:11:41)