Simple permutations and algebraic generating functions

Abstract

A simple permutation is one that does not map a nontrivial interval onto an interval. It was recently proved by Albert and Atkinson that a permutation class with only finitely simple permutations has an algebraic generating function. We extend this result to enumerate permutations in such a class satisfying additional properties, e.g., the even permutations, the involutions, the permutations avoiding generalised permutations, and so on.

References in corpus (2)

• 231-Avoiding Involutions and Fibonacci Numbers
• Simple permutations: decidability and unavoidable substructures

Cited by in corpus (2)

• Longest Common Separable Pattern between Permutations
• Wreath Products of Permutation Classes