On the effective and automatic enumeration of polynomial permutation classes

DOI10.1016/J.JSC.2015.11.019MaRDI QIDQ5963395zbMATHOpenAlexFDO

Authors Cheyne Homberger, Vincent Vatter

Publication date 19 February 2016

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

permutation patternsrational generating functionpolynomial class

Mathematics Subject Classification ID

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

Abstract: We describe an algorithm, implemented in Python, which can enumerate any permutation class with polynomial enumeration from a structural description of the class. In particular, this allows us to find formulas for the number of permutations of length n which can be obtained by a finite number of block sorting operations (e.g., reversals, block transpositions, cut-and-paste moves).

Recommendations

• Automatic discovery of structural rules of permutation classes
• An algorithm computing combinatorial specifications of permutation classes
• Enumeration Schemes for Restricted Permutations
• Combinatorial specification of permutation classes
• Finding regular insertion encodings for permutation classes

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Combinatorial specification of permutation classes
• Combinatorics of genome rearrangements.
• Finding regular insertion encodings for permutation classes
• Geometric grid classes of permutations
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Hereditary and monotone properties of combinatorial structure
• Hereditary properties of ordered graphs
• On growth rates of closed permutation classes
• Ordering by Divisibility in Abstract Algebras
• Overview of some general results in combinatorial enumeration
• Permutation classes
• Permutation classes of polynomial growth
• Short proofs for cut-and-paste sorting of permutations
• Simple permutations and algebraic generating functions
• Simple permutations and pattern restricted permutations
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• The insertion encoding of permutations

Cited in

(8)

• Letter graphs and geometric grid classes of permutations
• Permutation patterns in genome rearrangement problems: the reversal model
• An Algorithm to Enumerate Grid Signed Permutation Classes
• Prolific permutations
• Automatic discovery of structural rules of permutation classes
• An algorithm computing combinatorial specifications of permutation classes
• Wilf-collapse in permutation classes having two basis elements of size three
• Generating permutations with restricted containers

Describes a project that uses

Uses Software

• InsEnc
• OEIS
• Python

This page was built for publication: On the effective and automatic enumeration of polynomial permutation classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963395)