dc.contributor |
Háskólinn í Reykjavík |
dc.contributor |
Reykjavik University |
dc.contributor.author |
Bean, Christian |
dc.contributor.author |
Nadeau, Emile |
dc.contributor.author |
Úlfarsson, Henning Arnór |
dc.date.accessioned |
2021-06-25T14:33:56Z |
dc.date.available |
2021-06-25T14:33:56Z |
dc.date.issued |
2021-03 |
dc.identifier.issn |
1462-7264 |
dc.identifier.issn |
1365-8050 (eISSN) |
dc.identifier.uri |
https://hdl.handle.net/20.500.11815/2629 |
dc.description |
Publisher's version (útgefin grein) |
dc.description.abstract |
In this paper, we study the staircase encoding of permutations, which maps a permutation to a staircase grid with cellsfilled with permutations. We consider many cases, where restricted to a permutation class, the staircase encoding be-comes a bijection to its image. We describe the image of thoserestrictions using independent sets of graphs weightedwith permutations. We derive the generating function for the independent sets and then for their weighted coun-terparts. The bijections we establish provide the enumeration of permutation classes. We use our results to uncoversome unbalanced Wilf-equivalences of permutation classesand outline how to do random sampling in the permutationclasses. In particular, we cover the classes Av (2314,3124), Av (2413,3142), Av(2413,3124), Av(2413,2134) and Av (2314,2143), as well as many subclasses. |
dc.format.extent |
C. Bean, E. Nadeau, and H. Ulfarsson, “Enumeration of Permutation Classes and Weighted Labelled Independent Sets,” Discret. Math. Theor. Comput. Sci., vol. 22, no. 2, p. 2, 2021 |
dc.language.iso |
en |
dc.publisher |
DIiscrete Mathematics Theoretical Computer Science |
dc.relation.ispartofseries |
DIiscrete Mathematics and Theoretical Computer Science;22 |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Software Engineering |
dc.subject |
Permutation Patterns |
dc.subject |
Independent sets |
dc.subject |
Wilf-equivalence |
dc.subject |
Random sampling |
dc.subject |
Enumeration |
dc.subject |
Hugbúnaðarverkfræði |
dc.subject |
Slembiúrtak |
dc.subject |
Stærðfræði |
dc.title |
Enumeration of Permutation Classes and Weighted Labelled Independent Sets |
dc.type |
info:eu-repo/semantics/article |
dcterms.license |
Distributed under a Creative Commons Attribution 4.0 International License |
dc.description.version |
Peer reviewed |
dc.identifier.journal |
DIiscrete Mathematics and Theoretical Computer Science |
dc.contributor.department |
Tölvunarfræðideild (HR) |
dc.contributor.department |
Department of Computer Science (RU) |
dc.contributor.school |
Tæknisvið (HR) |
dc.contributor.school |
School of Technology (RU) |