Opin vísindi

Enumeration of Permutation Classes andWeighted Labelled Independent Sets

Enumeration of Permutation Classes andWeighted Labelled Independent Sets

Title: Enumeration of Permutation Classes andWeighted Labelled Independent Sets
Author: Bean, Christian
Nadeau, Emile
Úlfarsson, Henning Arnór
Date: 2021-03
Language: English
Scope: 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
University/Institute: Háskólinn í Reykjavík
Reykjavik University
School: Tæknisvið (HR)
School of Technology (RU)
Department: Tölvunarfræðideild (HR)
Department of Computer Science (RU)
Series: DIiscrete Mathematics and Theoretical Computer Science;22
ISSN: 1462-7264
1365-8050 (eISSN)
Subject: Software Engineering; Permutation Patterns; Independent sets; Wilf-equivalence; Random sampling; Enumeration; Hugbúnaðarverkfræði; Slembiúrtak; Stærðfræði
URI: https://hdl.handle.net/20.500.11815/2629

Show full item record


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.


Publisher's version (útgefin grein)


Distributed under a Creative Commons Attribution 4.0 International License

Files in this item

This item appears in the following Collection(s)