Combinatorial specification of permutation classes

Abstract

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.

Keywords

• generating functions
• simple permutations
• substitution decomposition
• excluded patterns
• permutation classes
• combinatorial specification
• random generation
• [math.math-co] mathematics [math]/combinatorics [math.co]