The Open UniversitySkip to content
 

Simple permutations and algebraic generating functions

Brignall, Robert; Huczynska, Sophie and Vatter, Vincent (2008). Simple permutations and algebraic generating functions. Journal of Combinatorial Theory, Series A, 115(3) pp. 423–441.

DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/j.jcta.2007.06.007
Google Scholar: Look up in Google Scholar

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.

Item Type: Journal Article
Copyright Holders: 2007 Elsevier Inc.
ISSN: 0097-3165
Keywords: algebraic generating function; modular decomposition; permutation class; restricted permutation; simple permutation; substitution decomposition
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 23472
Depositing User: Robert Brignall
Date Deposited: 13 Oct 2010 16:17
Last Modified: 02 Dec 2010 21:07
URI: http://oro.open.ac.uk/id/eprint/23472
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk