Résumé | Dans cet exposé, je vous présenterai un nouvel arbre de génération uniforme pour les permutations qui préserve le nombre de k-cycles entre toute permutation et ses enfants dans l'arbre (à l'exception d'une petite proportion non évitable de taille optimale).
L'arbre que je vais décrire aura la propriété que lors d'une descente dans l'arbre, si le nombre de k-cycles reste constant pendant k niveaux consécutifs, alors le reste de la descente ne parcourra que des permutations avec ce même nombre de k-cycles. Cette propriété additionnelle permet d'obtenir des algorithmes efficaces pour la génération de permutations (permutations uniformes avec un nombre de k-cycles fixé) et de variables aléatoires de Poisson.
Ce travail en collaboration avec Ph. Duchon généralise un précédent arbre avec des propriétés similaires traitant le cas k=1. |