Christian Bean ; Émile Nadeau ; Henning Ulfarsson - Enumeration of Permutation Classes and Weighted Labelled Independent Sets

dmtcs:5995 - Discrete Mathematics & Theoretical Computer Science, March 29, 2021, vol. 22 no. 2, Permutation Patterns 2019 - https://doi.org/10.46298/dmtcs.5995
Enumeration of Permutation Classes and Weighted Labelled Independent SetsArticle

Authors: Christian Bean ; Émile Nadeau ; Henning Ulfarsson ORCID

    In this paper, we study the staircase encoding of permutations, which maps a permutation to a staircase grid with cells filled with permutations. We consider many cases, where restricted to a permutation class, the staircase encoding becomes a bijection to its image. We describe the image of those restrictions using independent sets of graphs weighted with permutations. We derive the generating function for the independent sets and then for their weighted counterparts. The bijections we establish provide the enumeration of permutation classes. We use our results to uncover some unbalanced Wilf-equivalences of permutation classes and outline how to do random sampling in the permutation classes. In particular, we cover the classes $\mathrm{Av}(2314,3124)$, $\mathrm{Av}(2413,3142)$, $\mathrm{Av}(2413,3124)$, $\mathrm{Av}(2413,2134)$ and $\mathrm{Av}(2314,2143)$, as well as many subclasses.


    Volume: vol. 22 no. 2, Permutation Patterns 2019
    Section: Special issues
    Published on: March 29, 2021
    Accepted on: March 13, 2021
    Submitted on: December 20, 2019
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 546 times.
    This article's PDF has been downloaded 246 times.