Bonsoir, Si on pose l'univers omega l'ensemble Sn, sur lequel on dispose de la probabilité P uniforme, et que si X est un varaiablr aléatoire à valeurs dans N, on rappelle que sa fonction generatrice F(Z)=sum sur k dans N de P(X=k)z^k permet de calculer son espérance e mt sa variance à partir de f'(1) et f''(1) Il se trouve qu'il est possible (de mémoire par récurrence) de calculer le polynôme Q suivant Q=sum_{sigma dans Sn} z^{INV(sigma)} Si on note X la va qui à sigma associr INV(sigma), ce polynôme Q peut se ré écrire : cardinal de Sn fois sum_k P(X=k)z^k ie cardinal de Sn fois fonction generatrice de X Bref tout repose sur le calcul de ce polynôme Q. Quant on nombre de cycles je en sais pas si on peut suivre cette méthode.faifrait voir la vidéo précédente pour voir si on ne peut pas calculer la fonction génératrice correspondante.
Pour le calcul de Q (3n fait Q_{N+1} en fonction de Q_n), c'est assez simple si on fait le constat (somme toute trivial) suivant. constat : si au lieu de regarder des permutations on regarde des applications de E vers F où chacun des ensembles E et F est de cardinal n et muni d'un ordre total, alors le polynôme Q_n est le ''même'' On partitionne suivant la valeur de sigma(n+1) Q_{N+1}=sum_k sum_{sigma dans S_{N+1}, sigma (N+1)=k z^{INV (sigma)) Sigma (N+1)=k donne lieu aux inversions pour les sigma^{-1}(R) où R est un des entiers k+1, k+2 à N+1 ce qui donne lieu N+1-k inversions Et en utilisant le constat qu'on applique avec E égal aux entiers de 1 à N muni de l'ordre habituel et F les entiers de 1 N+1 excepté k muni de l'ordre habituel on obtient une relation de récurrence simple entre q_{N+1} et q_n Le reste c'est du calcul...
Georges Sand 👍
Bonsoir,
Si on pose l'univers omega l'ensemble Sn, sur lequel on dispose de la probabilité P uniforme, et que si X est un varaiablr aléatoire à valeurs dans N, on rappelle que sa fonction generatrice F(Z)=sum sur k dans N de P(X=k)z^k permet de calculer son espérance e mt sa variance à partir de f'(1) et f''(1)
Il se trouve qu'il est possible (de mémoire par récurrence) de calculer le polynôme Q suivant Q=sum_{sigma dans Sn} z^{INV(sigma)}
Si on note X la va qui à sigma associr INV(sigma), ce polynôme Q peut se ré écrire : cardinal de Sn fois sum_k P(X=k)z^k ie cardinal de Sn fois fonction generatrice de X
Bref tout repose sur le calcul de ce polynôme Q.
Quant on nombre de cycles je en sais pas si on peut suivre cette méthode.faifrait voir la vidéo précédente pour voir si on ne peut pas calculer la fonction génératrice correspondante.
Pour le calcul de Q (3n fait Q_{N+1} en fonction de Q_n), c'est assez simple si on fait le constat (somme toute trivial) suivant.
constat : si au lieu de regarder des permutations on regarde des applications de E vers F où chacun des ensembles E et F est de cardinal n et muni d'un ordre total, alors le polynôme Q_n est le ''même''
On partitionne suivant la valeur de sigma(n+1)
Q_{N+1}=sum_k sum_{sigma dans S_{N+1}, sigma (N+1)=k z^{INV (sigma))
Sigma (N+1)=k donne lieu aux inversions pour les sigma^{-1}(R) où R est un des entiers k+1, k+2 à N+1 ce qui donne lieu N+1-k inversions
Et en utilisant le constat qu'on applique avec E égal aux entiers de 1 à N muni de l'ordre habituel et F les entiers de 1 N+1 excepté k muni de l'ordre habituel on obtient une relation de récurrence simple entre q_{N+1} et q_n
Le reste c'est du calcul...