Simple permutations and algebraic generating functions
From MaRDI portal
Publication:2426423
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.
This paper deals with simple permutations, that is with permutations that never map a nontrivial contiguous set of indices contiguously. For an arbitrary set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, there is given 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 generalized (blocked or barred) pattern. The authors prove that the generating functions of these subsets are always algebraic, generalizing some recent results of Albert and Atkinson. These techniques are also applied to enumerate the involutions and cyclic closures.
Recommendations
- Generating functions for permutation representations.
- Permutation and complete permutation polynomials
- Simple permutations and pattern restricted permutations
- Alternating permutations and symmetric functions
- scientific article; zbMATH DE number 1195713
- scientific article; zbMATH DE number 2186865
- Generating functions of permutations with respect to their alternating runs
- On the generalized permutations
- On permutation polynomials
- Decomposing simple permutations, with enumerative consequences
Cites work
- 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
- A k-structure generalization of the theory of 2-structures
- A finiteness theorem for primal extensions
- Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
- Complement reducible graphs
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Decreasing subsequences in permutations and Wilf equivalence for involutions
- Enumeration of vexillary involutions which are equal to their mirror/complement
- Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
- Forest-like permutations
- Generalized permutation patterns and a classification of the Mahonian statistics
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 3722110 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- scientific article; zbMATH DE number 2104721 (Why is no real title available?)
- scientific article; zbMATH DE number 2108134 (Why is no real title available?)
- scientific article; zbMATH DE number 5238983 (Why is no real title available?)
- Interpretations combinatoires des nombres de Genocchi
- On the closure of graphs under substitution
- Ordering by Divisibility in Abstract Algebras
- Prefix exchanging and pattern avoidance by involutions
- Refined restricted permutations
- Restricted 1-3-2 permutations and generalized patterns
- Restricted 132-alternating permutations and Chebyshev polynomials
- Restricted 132-avoiding permutations
- Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials
- Restricted even permutations and Chebyshev polynomials
- Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polyno\-mials
- Restricted symmetric permutations
- Simple permutations and pattern restricted permutations
- Simple permutations: Decidability and unavoidable substructures
- Some statistics on restricted 132 involutions
- Sorting twice through a stack
- Vexillary involutions are enumerated by Motzkin numbers
Cited in
(17)- On two-sided gamma-positivity for simple permutations
- Scaling limits of permutation classes with a finite specification: a dichotomy
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
- Combinatorial specifications for juxtapositions of permutation classes
- Inflations of geometric grid classes of permutations
- Nine classes of permutations enumerated by binomial transform of Fine's sequence
- Decomposing simple permutations, with enumerative consequences
- Simple permutations: Decidability and unavoidable substructures
- Permutations with few internal points
- scientific article; zbMATH DE number 2186865 (Why is no real title available?)
- A survey of simple permutations
- Splittings and Ramsey properties of permutation classes
- An algorithm computing combinatorial specifications of permutation classes
- On the effective and automatic enumeration of polynomial permutation classes
- Substitution-closed pattern classes
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Small configurations in simple permutations
This page was built for publication: Simple permutations and algebraic generating functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2426423)
