Equivalence classes of permutations avoiding a pattern - Mathematics > CombinatoricsReport as inadecuate

Equivalence classes of permutations avoiding a pattern - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

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

Author: Henning Ulfarsson

Source: https://arxiv.org/


Related documents