Simple permutations and algebraic generating functions

DOI10.1016/j.jcta.2007.06.007zbMath1139.05002arXivmath/0608391OpenAlexW2059924808MaRDI QIDQ2426423

Sophie Huczynska, Robert Brignall, Vincent R. Vatter

Publication date: 22 April 2008

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0608391

zbMATH Keywords

modular decompositionrestricted permutationpermutation classalgebraic generating functionsubstitution decompositionsimple permutation

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05)

Related Items

Nine classes of permutations enumerated by binomial transform of Fine's sequence ⋮ Decomposing simple permutations, with enumerative consequences ⋮ On two-sided gamma-positivity for simple permutations ⋮ Scaling limits of permutation classes with a finite specification: a dichotomy ⋮ Substitution-closed pattern classes ⋮ Splittings and Ramsey properties of permutation classes ⋮ Simple permutations: Decidability and unavoidable substructures ⋮ An algorithm computing combinatorial specifications of permutation classes ⋮ An algorithm for deciding the finiteness of the number of simple permutations in permutation classes ⋮ Small configurations in simple permutations ⋮ On the effective and automatic enumeration of polynomial permutation classes ⋮ Combinatorial specifications for juxtapositions of permutation classes ⋮ Inflations of geometric grid classes of permutations

Uses Software

• AARON

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting twice through a stack
• Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials
• Complement reducible graphs
• Interpretations combinatoires des nombres de Genocchi
• A \(k\)-structure generalization of the theory of 2-structures
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• On the closure of graphs under substitution
• Some statistics on restricted 132 involutions
• Refined restricted permutations
• Restricted 132-alternating permutations and Chebyshev polynomials
• Prefix exchanging and pattern avoidance by involutions
• Generalized permutation patterns and a classification of the Mahonian statistics
• Enumeration of vexillary involutions which are equal to their mirror/complement
• Vexillary involutions are enumerated by Motzkin numbers
• Restricted 1-3-2 permutations and generalized patterns
• 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Forest-like permutations
• Restricted symmetric permutations
• Simple permutations: Decidability and unavoidable substructures
• A finiteness theorem for primal extensions
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Restricted even permutations and Chebyshev polynomials
• Simple permutations and pattern restricted permutations
• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polyno\-mials
• Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
• Ordering by Divisibility in Abstract Algebras
• Restricted 132-avoiding permutations