## Frédérique Bassino ; Mathilde Bouvel ; Adeline Pierrot ; Carine Pivoteau ; Dominique Rossin - Combinatorial specification of permutation classes

dmtcs:3082 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) - https://doi.org/10.46298/dmtcs.3082
Combinatorial specification of permutation classes

Authors: Frédérique Bassino ; Mathilde Bouvel ; Adeline Pierrot ; Carine Pivoteau ; Dominique Rossin

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.

Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: generating functions,simple permutations,substitution decomposition,excluded patterns,permutation classes,combinatorial specification,random generation,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

## Consultation statistics

This page has been seen 94 times.
This article's PDF has been downloaded 180 times.