Combinatorial specification of permutation classes
This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{C}$, when these sets are both finite. This is achieved considering bo...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2012-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3082/pdf |
| _version_ | 1797270320691806208 |
|---|---|
| author | Frédérique Bassino Mathilde Bouvel Adeline Pierrot Carine Pivoteau Dominique Rossin |
| author_facet | Frédérique Bassino Mathilde Bouvel Adeline Pierrot Carine Pivoteau Dominique Rossin |
| author_sort | Frédérique Bassino |
| collection | DOAJ |
| description | This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{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 $\mathcal{C}$, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in $\mathcal{C}$. The method presented is fully algorithmic. |
| first_indexed | 2024-04-25T02:02:24Z |
| format | Article |
| id | doaj.art-f55a8695f92643b89063831a02fda893 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:24Z |
| publishDate | 2012-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f55a8695f92643b89063831a02fda8932024-03-07T14:51:45ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502012-01-01DMTCS Proceedings vol. AR,...Proceedings10.46298/dmtcs.30823082Combinatorial specification of permutation classesFrédérique Bassino0https://orcid.org/0000-0002-0127-9352Mathilde Bouvel1Adeline Pierrot2Carine Pivoteau3Dominique Rossin4Laboratoire d'Informatique de Paris-NordLaboratoire Bordelais de Recherche en InformatiqueLaboratoire d'informatique Algorithmique : Fondements et ApplicationsLaboratoire d'Informatique Gaspard-MongeLaboratoire d'informatique de l'École polytechnique [Palaiseau]This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{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 $\mathcal{C}$, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in $\mathcal{C}$. The method presented is fully algorithmic.https://dmtcs.episciences.org/3082/pdfgenerating functionssimple permutationssubstitution decompositionexcluded patternspermutation classescombinatorial specificationrandom generation[math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Frédérique Bassino Mathilde Bouvel Adeline Pierrot Carine Pivoteau Dominique Rossin Combinatorial specification of permutation classes Discrete Mathematics & Theoretical Computer Science generating functions simple permutations substitution decomposition excluded patterns permutation classes combinatorial specification random generation [math.math-co] mathematics [math]/combinatorics [math.co] |
| title | Combinatorial specification of permutation classes |
| title_full | Combinatorial specification of permutation classes |
| title_fullStr | Combinatorial specification of permutation classes |
| title_full_unstemmed | Combinatorial specification of permutation classes |
| title_short | Combinatorial specification of permutation classes |
| title_sort | combinatorial specification of permutation classes |
| topic | generating functions simple permutations substitution decomposition excluded patterns permutation classes combinatorial specification random generation [math.math-co] mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/3082/pdf |
| work_keys_str_mv | AT frederiquebassino combinatorialspecificationofpermutationclasses AT mathildebouvel combinatorialspecificationofpermutationclasses AT adelinepierrot combinatorialspecificationofpermutationclasses AT carinepivoteau combinatorialspecificationofpermutationclasses AT dominiquerossin combinatorialspecificationofpermutationclasses |