On the effective and automatic enumeration of polynomial permutation classes

DOI10.1016/J.JSC.2015.11.019zbMATH Open1331.05016arXiv1308.4946OpenAlexW2167190263MaRDI QIDQ5963395FDOQ5963395

Vincent Vatter, Cheyne Homberger

Publication date: 19 February 2016

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

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).

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

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

zbMATH Keywords

permutation patternsrational generating functionpolynomial class

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Finding regular insertion encodings for permutation classes
• Title not available (Why is that?)
• Permutation classes
• Sorting by Transpositions
• Ordering by Divisibility in Abstract Algebras
• Simple permutations and pattern restricted permutations
• Overview of some general results in combinatorial enumeration
• The insertion encoding of permutations
• Short proofs for cut-and-paste sorting of permutations
• On growth rates of closed permutation classes
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Geometric grid classes of permutations
• Simple permutations and algebraic generating functions
• Sorting permutations by block-interchanges
• Hereditary properties of ordered graphs
• Hereditary and monotone properties of combinatorial structure
• Permutation classes of polynomial growth
• Combinatorial specification of permutation classes

Cited In (7)

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

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)