Enumeration of Permutation Classes and Weighted Labelled Independent Sets

Bean, Christian; Nadeau, Émile; Ulfarsson, Henning

Abstract

n 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 Av(2314,3124) , Av(2413,3142) , Av(2413,3124) , Av(2413,2134) and Av(2314,2143) , as well as many subclasses.

• Journal Article Type: Article
• Acceptance Date: Mar 13, 2021
• Online Publication Date: Mar 29, 2021
• Publication Date: Mar 29, 2021
• Deposit Date: Jun 2, 2023
• Journal: Discrete Mathematics & Theoretical Computer Science
• Print ISSN: 1462-7264
• Publisher: Episciences.org
• Peer Reviewed: Peer Reviewed
• Volume: vol. 22 no. 2, Permutation Patterns 2019
• Issue: Special issues
• DOI: https://doi.org/10.46298/dmtcs.5995
• Keywords: Discrete Mathematics and Combinatorics; General Computer Science; Theoretical Computer Science