Combinatorial specification of permutation classes

MaRDI QIDQ5377427zbMATH OpenFDO

Authors Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Carine Pivoteau, Dominique Rossin

Publication date 24 May 2019

Full work available at URL https://arxiv.org/abs/1204.0797, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAR0169

zbMATH Keywords

combinatorial specificationexcluded patternsgenerating functionspermutation classesrandom generationsimple permutationssubstitution decomposition

Mathematics Subject Classification ID

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

Abstract: This article presents a methodology that automatically derives a combinatorial specification for the permutation class C = Av(B), given its basis B of excluded patterns and the set of simple permutations in C, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations.The obtained specification yields a system of equations satisfied by the generating function of C, this system being always positiveand algebraic. It also yields a uniform random sampler of permutations in C. The method presentedis fully algorithmic.

Recommendations

• Combinatorial specifications for juxtapositions of permutation classes
• An algorithm computing combinatorial specifications of permutation classes
• Composability of permutation classes
• Permutation classes
• Combinatorics of permutations
• Combinatorics of permutations
• scientific article; zbMATH DE number 2107707
• Subclasses of the separable permutations
• Characterization and enumeration of some classes of permutominoes

Cited in

(12)

• Composability of permutation classes
• A class of recursive permutations which is primitive recursive complete
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
• Combinatory classes of compositions with higher order conjugation
• Combinatorial specifications for juxtapositions of permutation classes
• Permutation classes
• Right-justified characterization for generating regular pattern avoiding permutations
• Automatic discovery of structural rules of permutation classes
• Using large random permutations to partition permutation classes
• Enumeration of permutation classes and weighted labelled independent sets
• An algorithm computing combinatorial specifications of permutation classes
• On the effective and automatic enumeration of polynomial permutation classes

This page was built for publication: Combinatorial specification of permutation classes

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