Equivalence classes of permutations avoiding a pattern - Mathematics > CombinatoricsReportar como inadecuado

Equivalence classes of permutations avoiding a pattern - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Given a permutation pattern p and an equivalence relation on permutations, westudy the corresponding equivalence classes all of whose members avoid p. Fourrelations are studied: Conjugacy, order isomorphism, Knuth-equivalence andtoric equivalence. Each of these produces a known class of permutations or aknown counting sequence. For example, involutions correspond to conjugacy, andpermutations whose insertion tableau is hook-shaped with 2 in the first rowcorrespond to Knuth-equivalence. These permutations are equinumerous withcertain congruence classes of graph endomorphisms. In the case of toricequivalence we find a class of permutations that are counted by the Eulertotient function, with a subclass counted by the number-of-divisors function.We also provide a new symmetry for bivincular patterns that produces some newnon-trivial Wilf-equivalences

Autor: Henning Ulfarsson

Fuente: https://arxiv.org/

Documentos relacionados