Simple permutations and algebraic generating functions

Robert Brignall, Sophie Huczynska, Vincent Vatter

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

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 bar-red) 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. (C) 2007 Elsevier Inc. All rights reserved.

Original languageEnglish
Pages (from-to)423-441
Number of pages19
JournalJournal of Combinatorial Theory, Series A
Volume115
Issue number3
DOIs
Publication statusPublished - Apr 2008

Keywords

  • algebraic generating function
  • modular decomposition
  • permutation class
  • restricted permutation
  • simple permutation
  • substitution decomposition
  • CHEBYSHEV POLYNOMIALS
  • CONTINUED FRACTIONS
  • INVOLUTIONS
  • NUMBERS
  • GRAPHS
  • ENUMERATION

Fingerprint

Dive into the research topics of 'Simple permutations and algebraic generating functions'. Together they form a unique fingerprint.

Cite this