Simple permutations and algebraic generating functions |
| |
Authors: | Robert Brignall Vincent Vatter |
| |
Institution: | University of St Andrews, School of Mathematics and Statistics, St Andrews, Fife, KY16 9SS, UK |
| |
Abstract: | A simple permutation is one that never maps a nontrivial contiguous set of indices contiguously. Given a set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, we provide a framework for enumerating subsets that are restricted by properties belonging to a finite “query-complete set.” Such properties include being even, being an alternating permutation, and avoiding a given generalised (blocked or barred) pattern. We show that the generating functions for these subsets are always algebraic, thereby generalising recent results of Albert and Atkinson. We also apply these techniques to the enumeration of involutions and cyclic closures. |
| |
Keywords: | Algebraic generating function Modular decomposition Permutation class Restricted permutation Simple permutation Substitution decomposition |
本文献已被 ScienceDirect 等数据库收录! |
|