Simple permutations and algebraic generating functions

2006/08/15 by Robert Brignall, Brignall, Robert, Sophie Huczynska +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0608391

openalex publication_date 2006/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Interprétations combinatoires des nombres de Genocchi
• Simple permutations and pattern restricted permutations
• Complement reducible graphs
• 231-Avoiding Involutions and Fibonacci Numbers
• Simple permutations: decidability and unavoidable substructures

Related

• The enumeration of simple permutations
• A Survey of Simple Permutations
• What Could Be a Simple Permutation?
• Decomposing simple permutations, with enumerative consequences
• Permutations with a fixed number of occurrences of a monotone pattern