Dénombrement et groupe symétrique

[Luc]

Bonjour,

Je suis en train de préparer un développement de la leçon de combinatoire autour de divers dénombrement sur le groupe symétrique.
On connait par exemple le nombre de permutations sans points fixes (dérangements). Plus généralement, on peut également calculer le nombre de permutations à exactement p points fixes (dérangements de Montmort).
On appelle la variable aléatoire égale au nombre de points fixes d'une permutation à n éléments tirée uniformément dans .
Sa loi est donnée par les nombres de permutations à p points fixes .

Je me suis alors posé quelques questions auxquelles je suis incapable de répondre :

- Calcul du nombre moyen de points fixes d'une permutation tirée au hasard (autrement dit, l'espérance de )
- Calcul de la variance de
- Calcul explicite de la fonction génératrice de

Limite quand n tend vers l'infini : je crois avoir montré que convergeait en loi vers , à valeurs dans , de loi . (Poisson de paramètre 1)

Plusieurs questions :
- Est-ce qu'on peut déduire quelque chose de cette convergence en loi? (par exemple a-t-on convergence des fonctions génératrices, CVS, CVU?)
- Limite des moments (espérance, variance)

Je pense que non, la convergence en loi est une notion faible (n'implique pas les autres convergences en général)
Il y a aussi un problème de type : a priori X est défini sur un espace d'états gros, celui des bijections de (qui n'est pas dénombrable, sauf erreur de ma part, et du coup on ne peut plus tirer uniformément)

J'ai d'autres questions plus compliquées, avec les variables aléatoires Y_n donnant le nombre de cycles d'une permutation, Z_n la longueur de la plus grande orbite, etc.

[adrien69]

J'ai en tête un bouquin disponible gratuitement sur le net qui répond à tes questions, il s'agit de "Analytic combinatorics", coécrit par P. Flageolet et S. Sedgwick. J'ai souvenance qu'ils étudiaient ça par le prisme de l'analyse complexe. Dis moi si tu ne trouves pas.

[Luc]

J'ai en tête un bouquin disponible gratuitement sur le net qui répond à tes questions, il s'agit de "Analytic combinatorics", coécrit par P. Flageolet et S. Sedgwick. J'ai souvenance qu'ils étudiaient ça par le prisme de l'analyse complexe. Dis moi si tu ne trouves pas.

Ok, je vais regarder ça, mais j'aurais bien aimé que l'on puisse répondre au moins partiellement à ces questions par des raisonnements purement combinatoires, ou par des actions de groupes (formule des classes).

Par exemple, j'ai vu dans le Colmez (éléments d'analyse et d'algèbre) un résultat sympa sur l'espérance de la va que j'ai appelée : le nombre moyen de k-cycles dans la décomposition d'une permutation de tirée uniformément est égal à 1/k. En particulier, le nombre moyen de cycles d'une permutation est égal à 1+1/2+...+1/n et tend vers l'infini.

Sinon, autre question, indépendante et je pense plus abordable. On sait que les transpositions (12),(13),...,(1n) engendrent et que ce résultat est optimal dans le sens où n-2 transpositions n'engendrent jamais .
Je m'intéresse à un problème similaire pour le groupe alterné. Les 3-cycles (123), (124),...,(12n) engendrent . Est-ce que n-3 3 cycles peuvent engendrer ? Je pense que non, mais je ne l'ai pas démontré.

Luc

[adrien69]

C'est l'asymptotique qui est faite de façon analytique, le reste est algébrique.
Je vois mal A3 être engendré par rien et A4 par un élément et son inverse (cardinal 3).
A5 par contre... Le meilleur cas de figure est celui ou les supports n'on qu'un élément en commun (car sinon il manquera toujours un élément de 1,2,3,4,5).
Comme le rôle des nombres est complètement arbitraire (je pourrais appeler 1 3 ou 2 5), on peut supposer que l'on a (123) et (345), il nous manquera toujours (125) si je ne m'abuse.
D'où le cas général. À n-3 cycles, on peut supposer qu'il nous ont donné (ijk) pour i,j,k entre 3 et n-2 et (n-2 n-1 n)
Il nous manquera toujours (i_1 i_2 n) avec i1 et i2 des valeurs prises simultanément par i et j.