Enumeration of Permutation Classes and Weighted Labelled Independent
Sets
Authors: Christian Bean ; Émile Nadeau ; Henning Ulfarsson
NULL##NULL##0000-0001-6428-7117
Christian Bean;Émile Nadeau;Henning Ulfarsson
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.