Geodesic
Enumeration of Permutation Classes and Weighted Labelled Independent Sets
Discrete mathematics & theoretical computer science, Permutation Patterns 2019, Tome 22 (2020-2021) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2021_22_2_a0,
     author = {Bean, Christian and Nadeau, \'Emile and Ulfarsson, Henning},
     title = {Enumeration of {Permutation} {Classes} and {Weighted} {Labelled} {Independent} {Sets}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2020-2021},
     doi = {10.46298/dmtcs.5995},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5995/}
}
TY  - JOUR
AU  - Bean, Christian
AU  - Nadeau, Émile
AU  - Ulfarsson, Henning
TI  - Enumeration of Permutation Classes and Weighted Labelled Independent Sets
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5995/
DO  - 10.46298/dmtcs.5995
LA  - en
ID  - DMTCS_2021_22_2_a0
ER  - 
%0 Journal Article
%A Bean, Christian
%A Nadeau, Émile
%A Ulfarsson, Henning
%T Enumeration of Permutation Classes and Weighted Labelled Independent Sets
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5995/
%R 10.46298/dmtcs.5995
%G en
%F DMTCS_2021_22_2_a0
Bean, Christian; Nadeau, Émile; Ulfarsson, Henning. Enumeration of Permutation Classes and Weighted Labelled Independent Sets. Discrete mathematics & theoretical computer science, Permutation Patterns 2019, Tome 22 (2020-2021) no. 2. doi : 10.46298/dmtcs.5995. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5995/

Cité par Sources :