Authors: Frédérique Bassino ¹; Mathilde Bouvel ²; Adeline Pierrot ³; Carine Pivoteau ⁴; Dominique Rossin ⁵

• 1 Laboratoire d'Informatique de Paris-Nord
• 2 Laboratoire Bordelais de Recherche en Informatique [LaBRI]
• 3 Laboratoire d'informatique Algorithmique : Fondements et Applications
• 4 Laboratoire d'Informatique Gaspard-Monge
• 5 Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]

[en]
This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{C}$, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations.The obtained specification yields a system of equations satisfied by the generating function of $\mathcal{C}$, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in $\mathcal{C}$. The method presented is fully algorithmic.

[fr]
Cet article présente une méthodologie qui calcule automatiquement une spécification combinatoire pour la classe de permutations $\mathcal{C} = Av(B)$, étant donnés une base $B$ de motifs interdits et l’ensemble des permutations simples de $\mathcal{C}$, lorsque ces deux ensembles sont finis. Ce résultat est obtenu en considérant à la fois des contraintes de motifs interdits et de motifs obligatoires dans les permutations. La spécification obtenue donne un système d’équations satisfait par la série génératrice de la classe $\mathcal{C}$, système qui est toujours positif et algébrique. Elle fournit aussi un générateur aléatoire uniforme de permutations dans $\mathcal{C}$. La méthode présentée est complètement algorithmique.