Énumération et génération aléatoire de cactus m-aires

Michel Bousquet (1) , Cedric Chauve (2) , Gilles Schaeffer (3)

1 LaCIM - Laboratoire de combinatoire et d'informatique mathématique [Montréal]
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique
3 POLKA - Polynomials, Combinatorics, Arithmetic

Dans cette note, nous appliquons une preuve bijective de la formule d'inversion de Lagrange multidimensionnelle pour donner une explication combinatoire de deux formules d'énumération de cactus $m$-aires, selon la distribution des couleurs et selon la distribution des degrés. Nous en déduisons un algorithme de génération aléatoire pour ces structures.

Mots clés: lagrange inversion; génération aléatoire; random sampling; cactus; trees; arbres; inversion de lagrange

Domaines: Autre [cs.OH]

Michel Bousquet, Cedric Chauve, Gilles Schaeffer. Énumération et génération aléatoire de cactus m-aires. Colloque LaCIM 2000: Combinatoire, Informatique et Applications, 2000, Montréal, Canada, 11 p. ⟨inria-00099190⟩