A code for square permutations and convex permutominoes
In this article we consider square permutations, a natural subclass of permutations defined in terms of geometric conditions, that can also be described in terms of pattern avoiding permutations, and convex permutoninoes, a related subclass of polyominoes. While these two classes of objects arised i...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5354/pdf |
| _version_ | 1797269993433333760 |
|---|---|
| author | Enrica Duchi |
| author_facet | Enrica Duchi |
| author_sort | Enrica Duchi |
| collection | DOAJ |
| description | In this article we consider square permutations, a natural subclass of
permutations defined in terms of geometric conditions, that can also be
described in terms of pattern avoiding permutations, and convex permutoninoes,
a related subclass of polyominoes. While these two classes of objects arised
independently in various contexts, they play a natural role in the description
of certain random horizontally and vertically convex grid configurations.
We propose a common approach to the enumeration of these two classes of
objets that allows us to explain the known common form of their generating
functions, and to derive new refined formulas and linear time random generation
algorithms for these objects and the associated grid configurations. |
| first_indexed | 2024-04-25T01:57:12Z |
| format | Article |
| id | doaj.art-2e5aa26bc6b7474db5b28dcf743454b2 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:12Z |
| publishDate | 2019-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-2e5aa26bc6b7474db5b28dcf743454b22024-03-07T15:38:27ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-12-01Vol. 21 no. 2, Permutation...10.23638/DMTCS-21-2-25354A code for square permutations and convex permutominoesEnrica DuchiIn this article we consider square permutations, a natural subclass of permutations defined in terms of geometric conditions, that can also be described in terms of pattern avoiding permutations, and convex permutoninoes, a related subclass of polyominoes. While these two classes of objects arised independently in various contexts, they play a natural role in the description of certain random horizontally and vertically convex grid configurations. We propose a common approach to the enumeration of these two classes of objets that allows us to explain the known common form of their generating functions, and to derive new refined formulas and linear time random generation algorithms for these objects and the associated grid configurations.https://dmtcs.episciences.org/5354/pdfmathematics - combinatorics |
| spellingShingle | Enrica Duchi A code for square permutations and convex permutominoes Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | A code for square permutations and convex permutominoes |
| title_full | A code for square permutations and convex permutominoes |
| title_fullStr | A code for square permutations and convex permutominoes |
| title_full_unstemmed | A code for square permutations and convex permutominoes |
| title_short | A code for square permutations and convex permutominoes |
| title_sort | code for square permutations and convex permutominoes |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/5354/pdf |
| work_keys_str_mv | AT enricaduchi acodeforsquarepermutationsandconvexpermutominoes AT enricaduchi codeforsquarepermutationsandconvexpermutominoes |