Opin vísindi

Enumeration of Permutation Classes and Weighted Labelled Independent Sets

Show simple item record

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)

Files in this item

This item appears in the following Collection(s)

Show simple item record