Bassino, Frédérique and Bouvel, Mathilde and Pierrot, Adeline and Pivoteau, Carine and Rossin, Dominique - 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)
Combinatorial specification of permutation classes

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

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
Submitted 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]


Share

Consultation statistics

This page has been seen 59 times.
This article's PDF has been downloaded 144 times.