Titill: | Enumeration of Permutation Classes and Weighted Labelled Independent Sets |
Höfundur: |
|
Útgáfa: | 2021-03 |
Tungumál: | Enska |
Umfang: | 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 |
Háskóli/Stofnun: | Háskólinn í Reykjavík Reykjavik University |
Svið: | Tæknisvið (HR) School of Technology (RU) |
Deild: | Tölvunarfræðideild (HR) Department of Computer Science (RU) |
Birtist í: | DIiscrete Mathematics and Theoretical Computer Science;22 |
ISSN: | 1462-7264 1365-8050 (eISSN) |
Efnisorð: | 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 |
Útdráttur: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.
|
|
Athugasemdir:Publisher's version (útgefin grein)
|
|
Leyfi:Distributed under a Creative Commons Attribution 4.0 International License
|